Looks like the output should be sorted. The C++ version does this with the iterator over map implicitly. I don't spot where your haskell version sorts the output.

There could be other problems, that's just what I can notice in 2 minutes of looking.

Good luck! Jason,

I assumed Data.Map was a tree internally and keep elements ordered, so the following would sort the input and print duplicates in O(n log n), as the C++ version does: sbank :: [B.ByteString] -> [(B.ByteString,Int)] sbank = toAscList . fromListWith (+) . flip zip (repeat 1) Is it wrong to assume this? It worked for all tests cases I could think of though. Thanks, -- ~dsouza yahoo!im: paravinicius gpg key fingerprint: 71B8 CE21 3A6E F894 5B1B 9ECE F88E 067F E891 651E

On Sun, Sep 13, 2009 at 11:34:16AM +0200, Max Rabkin wrote:

That is part of the contract of toAscList (the "Asc" stands for "ascending order"), but because of the way Map is implemented, the result of toList is also sorted.

Cool. It is good to know that toAscList and toList would produce the same output. However, I think the question remains open. Is this piece of haskell code any different (in terms of the output it produces) from the C++ version? Thanks, -- ~dsouza yahoo!im: paravinicius gpg key fingerprint: 71B8 CE21 3A6E F894 5B1B 9ECE F88E 067F E891 651E

(argh, sorry about that, I pressed something and gmail sent my unfinished email!) On Sun, Sep 13, 2009 at 9:54 PM, Iavor Diatchki wrote:

Hi, It seems that the problem is the site is using GHC 6.6.1, and something was broken at the time (I have not looked into what that is). Here are the outputs that I get for the little example on the site that you posted:

GHC 6.10.3 and C++:

03 10103538 2222 1233 6160 0141 1 03 10103538 2222 1233 6160 0142 1 30 10103538 2222 1233 6160 0141 2 30 10103538 2222 1233 6160 0142 2 30 10103538 2222 1233 6160 0142 1 30 10103538 2222 1233 6160 0143 1 30 10103538 2222 1233 6160 0144 1 30 10103538 2222 1233 6160 0145 1 30 10103538 2222 1233 6160 0146 1 With GHC 6.6.1: 03 10103538 2222 1233 6160 0141 1 03 10103538 2222 1233 6160 0142 1 30 10103538 2222 1233 6160 0141 2 30 10103538 2222 1233 6160 0142 2 30 10103538 2222 1233 6160 0142 1 30 10103538 2222 1233 6160 0143 1 30 10103538 2222 1233 6160 0145 1 30 10103538 2222 1233 6160 0146 1 Note that in the second test case one line is missing, the one ending in 44. -Iavor

On Sun, Sep 13, 2009 at 10:15 AM, Diego Souza wrote:

...

On Sun, Sep 13, 2009 at 11:34:16AM +0200, Max Rabkin wrote:

...

That is part of the contract of toAscList (the "Asc" stands for "ascending order"), but because of the way Map is implemented, the result of toList is also sorted.

Cool. It is good to know that toAscList and toList would produce the same output.

However, I think the question remains open. Is this piece of haskell code any different (in terms of the output it produces) from the C++ version?

Thanks, -- ~dsouza yahoo!im: paravinicius gpg key fingerprint: 71B8 CE21 3A6E F894 5B1B  9ECE F88E 067F E891 651E _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

On Sat, Sep 12, 2009 at 12:46 PM, Jason Dagit wrote:

On Sat, Sep 12, 2009 at 12:08 PM, Diego Souza wrote:

...

Hi,

I was trying to solve a simple problem in SPOJ, however, after two weeks trying almost everything I could think of, I was still getting WrongAnswer.

Then I decided to do the same thing in C++ and I really got puzzled when I got ACcepted.

I tried to understand what was different without success. I hope someone can tell me why spoj says the Haskell version is wrong:

http://moonpatio.com/fastcgi/hpaste.fcgi/view?id=3583 [Haskell,WA] http://moonpatio.com/fastcgi/hpaste.fcgi/view?id=3582 [C++,AC]

The problem I'm talking about is this one: https://www.spoj.pl/problems/SBANK/

Looks like the output should be sorted. The C++ version does this with the iterator over map implicitly. I don't spot where your haskell version sorts the output.

I take that back. I see how it sorts it now. Jason