Hello everybody,
So two-three weeks ago I started learning C#. I decided to code some problems in C# after doing that in C++ in order to practice it and of course learn some things I don't know to do in that language.
Today I came across this problem — http://mirror.codeforces.com/problemset/problem/220/B and I coded Mo's algorithm in C++. It easily got accepted with time about 2 seconds (the time limit is 4 seconds) — http://mirror.codeforces.com/contest/220/submission/15191708. Then I moved to C# and after more than an hour spent in looking for 'how to write a comparator for Array.Sort for custom class in C#', I finally submitted a code in C# — http://mirror.codeforces.com/contest/220/submission/15192611. As it can be seen, it gave TLE on the fifth test.
Then I read that for large arrays, Array.Sort uses quick sort, so I added a random shuffle before the actual sorting — http://mirror.codeforces.com/contest/220/submission/15192841, still TLE #5. I started looking for a faster input method and I read that BufferedStream may help — http://mirror.codeforces.com/contest/220/submission/15193006 — unfortunately, it didn't. At the end, I tried to store the whole output in a StringBuilder and then output it but I got TLE once again — http://mirror.codeforces.com/contest/220/submission/15193128.
Can anyone please suggest a way to speed the program up? I am quite new to C#, I tried using google but I found no more than what I described in the post.
Thanks in advance! :)
If you want to hammer a nail and have a hammer (C++) available, why would you do it with your hand (C#)?
C# is not a language designed to be fast or usable in competitive programming. What you should practice in it is not writing contest problems that have to handle large data in minimum time, but... well, whatever you think it could be used for.
I just tried that for fun, I know it is much slower than C++. Just thought that I may be using something slow (like cin without "magic lines" instead of scanf in C++). So I simply wondered if there is some way to optimize something so that it runs faster :) Also it is know that using getchar or fread is faster than scanf in C++, so maybe there are some optimizations that can be made in C# too, I just wanted to know :)
I suppose you can always optimise. That's the problem — as long as you use it for contest problems, you'll have to waste time (no, I don't think what you learn that way is worth the effort) with optimisations over optimisations. If you like that, why not try computing outputs by pen and paper?
Well, I don't think it's the same as "computing outputs by pen and paper" :) I don't plan to use C# in contests, the case is different — I just wanted to practice it in a problem from past contest and perhaps learn something new :)
Then don't try to get stuff accepted in time. Assume that you got it right when there was no WA. Avoiding TLEs will help you with exactly nothing.
The problem besides IO could be caused by boxing (In Java there is a similar problem when sorting Longs), but since you are using a struct it's seems unlikely. Other nefarious issue is the use of Console.WriteLine that flushes every single time. Use Console.Write or a StringBuffer/Builder to build the output and write it all once at the end.
Yes, I did that in my last submission as I wrote, but it seems that it wasn't enough. Thanks for your opinion! :)
You are not doing the sorting properly, you must divide by the square root of N ... check your slightly changed passing solution.
Ah, thanks and sorry for the effort! :) The same code (N instead of sqrt(N)) got AC in C++ btw :P
530ms and a bit cleaner code — 15194142
Thank you very much! :)