### huzecong's blog

By huzecong, 8 years ago,

Hello everybody!

We invite you to participate in Codeforces Round #248, which will take place at 11:00AM MSK on Saturday, May 24th. This round will be held in both divisions. Note that the starting time of this round is quite unusual.

The problems were prepared by zhonghaoxi, wyx528 and me. This is our first Codeforces round and we hope it will be a good one.

Many thanks to Gerald, who gave us enormous help during the preparations for this round; to colin and MSTyoda, who are the testers of this round; and to MikeMirzayanov, who created such a wonderful platform.

In Div. 1, scores for each problem will be 500-1000-1500-2000-3000. In Div. 2, scores for each problem will be 500-1500-1500-2000-2500.

Hope you enjoy the problems! Good luck and have fun~

UPD: Contest has finished! Editorial for the round can be found here: Editorial

UPD2: System test has finished! Congratulations to the following winners!

Top 5 of Div. 1:

Top 5 of Div. 2:

YuukaKazami is the only contestant to solve problem D! Sadly no one solved problem E during the contest.

UPD3: Statistics of the round by DmitriyH is here: Statistics

• +230

 » 8 years ago, # |   +61 Actually, it takes place on Saturday, not Sunday :DPity that I won't be able to participate, I have another competition going on at that time. An onsite one... nothing I can do.Besides that: wow such early much announcement very Chinese
•  » » 8 years ago, # ^ |   +37 Sorry, the time's now fixed.And nice doge :)
 » 8 years ago, # |   +8 First thanks for preparing this round I know it take a lot of efforts to do problem set for both Divisions Second why this statement is always written on all the rounds Score distribution will be published before the contest or sentences with the same meaning It seems that the first person wrote this sentence and all follow him without given reason :) I think while you preparing the problem set you know the position of each problem. but anyway when you announce the Score distribution a little bit time before the contest it create a something of a curiosity all the time starting from announcing the round till announcing the Score distribution and when we see score distribution we can Rest In Peace.
•  » » 8 years ago, # ^ |   +31 There is actually a reason... We still have to confirm the difficulty of the problems, to make sure we weren't wrong.And in my opinion score distribution is only a subjective and relative measurement of difficulty, so it doesn't say much about the actual difficulty of the problems.But anyway, we apologize for any inconvenience caused, and will try to put up the score distribution ASAP.
•  » » » 8 years ago, # ^ |   0 Thanks
•  » » » 8 years ago, # ^ |   0 But score distribution for DIV 2 is not correct. Problem B and C have same points but are solved by approx. 1000 and 60 people.
 » 8 years ago, # |   +29 nice time for me:))
 » 8 years ago, # |   +37 Are huzecong and wyx528 a pair of lovers?>_<
•  » » 8 years ago, # ^ |   +14 Of course
•  » » 8 years ago, # ^ |   0 How do you know that? Are there any differences in these accounts? LOL
•  » » 8 years ago, # ^ |   -10 you know too much ~
•  » » 8 years ago, # ^ |   +19 Do Chinese Coders like jokes of this kind?(I've seen several instances). Or they really love each other ?
•  » » » 8 years ago, # ^ |   +3 of course NOT joke
•  » » » 8 years ago, # ^ |   +11 It's a joke... I dunno why though...
•  » » » » 8 years ago, # ^ |   -8 233333 >.< ps orzzz
•  » » 8 years ago, # ^ |   +6 no wonder they are both blushing (in their profile pics)! :D
 » 8 years ago, # |   +30 orzzz... Hoping to see problems without too hard data structures
 » 8 years ago, # | ← Rev. 4 →   +10 This post should appear in the home page so everybody can find it easily.[update] the post is in the home page now, thanks :) I love contests in that time of day , I wish that this contest will be interesting
 » 8 years ago, # | ← Rev. 2 →   +39 Contest kicks off at 8.00 am in my country. Coding is always a good activity to begin your day.
•  » » 8 years ago, # ^ |   +45 Contest kicks off at 3.00 am in my country. Coding is always a good activity to end your day too ;)
•  » » » 8 years ago, # ^ |   0 You mean your night :D
 » 8 years ago, # |   +16 Chinese round again~orzzzzz
 » 8 years ago, # |   +4 marriage!
 » 8 years ago, # | ← Rev. 2 →   +12 Nice time for me, Happy to see the problem setter from my hometown :)
•  » » 8 years ago, # ^ |   +11 happy to see div1.E from your pic!though maybe no one can solve it ……
 » 8 years ago, # |   +19 This Score distribution not standard :)
•  » » 8 years ago, # ^ |   +14 At least it's more standard than dynamic distribution :D
 » 8 years ago, # |   +31 3000.. How difficult div1-E will be..And in my memory, almost all of Chinese round, nobody can solve E during the contest >_<
 » 8 years ago, # | ← Rev. 2 →   +11 No 1000-score problem [again]?! Is this a new method of scoring?!
 » 8 years ago, # | ← Rev. 2 →   0 Hope,I can give better look to my rating graph today :D btw,Best of luck ... !!! :)
 » 8 years ago, # | ← Rev. 3 →   +14 Kill la Kill, Clannad, Kami-sama hajimemashita, angel beats, kyoukai no kanata, white album :D
•  » » 8 years ago, # ^ |   +6 You've got 4 out of 6 right :D
•  » » » 8 years ago, # ^ |   +4 there's not me……T_Tnanami & Hajime are from http://zh.moegirl.org/%E5%BC%B9%E4%B8%B8%E8%AE%BA%E7%A0%B42 right?the last one i really don't know…… maybe Yakushiji Ryouko？
•  » » » » 8 years ago, # ^ |   +3 You're right... Ryouko is also from the Danganronpa series, her full name is Otonashi Ryouko.
 » 8 years ago, # |   -34 Chinese again! :(
•  » » 8 years ago, # ^ |   +9 Why the sad face :)
 » 8 years ago, # |   +32 omg the problem set is harder than Bruce Lee's punch X_X
•  » » 8 years ago, # ^ |   +14 On the bright side, the system testing should be fast :)
 » 8 years ago, # |   +7 How interesting...
 » 8 years ago, # |   0 How to solve A div 1 / C div 2?
•  » » 8 years ago, # ^ |   0 I submitted a ternary search.
•  » » 8 years ago, # ^ |   +3 Consider every page: the best strategy is to merge it to the median of all the page next(in the operation sequence) to it. Choose the best answer. I pass the pretest but I am not sure it can pass all the test.
•  » » » 8 years ago, # ^ |   0 Can you prove that we should merge it to the median?
•  » » » » 8 years ago, # ^ |   +3 The median is the solution to finding a 'center point' when the distance metric is abs. This also counts in multiple dimensions, e.g. if the 2d metric is abs(x0-x1)+abs(y0-y1) etc.You can prove it by assuming another solution is better and then noticing that moving a bit closer to the median improves the answer. Hence only the median can be optimal.
•  » » » » » 8 years ago, # ^ |   0 Thanks!
•  » » 8 years ago, # ^ |   +3 Consider each of the m numbers in your sequence, what will you safe by changing it to something else?If the sequence is "1 2 3 3 1 3", 3 is in |2-3|,|3-3|,|3-1|,|1-3| = 5. Hence if we change it to x, we safe 5-(|2-x|+|x-x|+|x-1|+|1-x|). To get the maximum value of the amount saved, just pick x to be the median of 2,1,1.Now how expensive is this? There are m numbers, each of which could have nearly m neighbours, so is it m^2? No, because we only consider each pair of neighbours twice, so the total running time is O(m) or O(mlogm) if we pick the medians by sorting.
 » 8 years ago, # | ← Rev. 2 →   +1 What is the approach to solve Div2 Problem C?
 » 8 years ago, # |   +15 Tricky Div1 A is tricky :'(
•  » » 8 years ago, # ^ |   +11 Yup. I think a lot of sources at A will not pass...
•  » » » 8 years ago, # ^ |   +7 In DIV1: Passed 232; Failed Systest 75
 » 8 years ago, # |   +23 This was way harder than usual ( at least for me ). Although , very nice problems. Big plus for the authors and waiting for your next contest !
 » 8 years ago, # | ← Rev. 2 →   0 I would say that while reading names in the problem statement, It was feeling like playing a tongue twister game. Chinese names are too difficult to pronounce in mind :).
•  » » 8 years ago, # ^ |   +55 Especially if they are Japanese
•  » » 8 years ago, # ^ |   +23 I simply replaced them with either 'Jackie Chan' or 'Bruce Lee' in my mind, for simplicity :D
•  » » » 8 years ago, # ^ |   +9 Why not Alice and Bob ? :)
•  » » 8 years ago, # ^ |   +19 actually they are all characters in Japanese anime or games……
•  » » 8 years ago, # ^ |   +12 All names in the statements are from Japanese animes... So they're not Chinese names :)
 » 8 years ago, # | ← Rev. 2 →   +3 Why my solution got Wrong answer on pretest 2? 6700945 UPD: found error x.x
 » 8 years ago, # |   +3 Tricky contest...
 » 8 years ago, # | ← Rev. 2 →   +4 Oh, sometimes you're clever enough to be very stupid :(I used BITs instead of simple partial sums in B and so I've no idea if my code will pass TL. UPD: And it passed! I LOVE CF!!! Anyway, great problems, thank you!
•  » » 8 years ago, # ^ |   0 Can you explain a bit about the two solutions?
•  » » 8 years ago, # ^ |   +9 There's popular Chinese Internet slang that goes "no do no die", which means if you look for trouble then you're definitely in trouble.This is especially true in competitive programming. It's best to keep solutions simple.
•  » » » 8 years ago, # ^ |   +8 Yeah, I try to do it. Unfortunately, I don't succeed always and that's one of the reasons I fail contests sometimes.But when it's needed to change elements of an array and calculate sums of its segments the last thing you think about is naive partial sums.)
•  » » » 8 years ago, # ^ |   +3 Click Zan!
 » 8 years ago, # |   +16 How to solve D?
•  » » 8 years ago, # ^ |   +5 network flow
•  » » » 8 years ago, # ^ |   +6 I'd appreciate some more detailed explanation.
•  » » » » 8 years ago, # ^ |   +8 Wait for the Editorial, we will write it there
•  » » 8 years ago, # ^ | ← Rev. 2 →   +13 OMG, I haven't read D during the contest, but now I find it is nearly same with FoxAndCity(DIV1-Hard in SRM590), which was created by me.You can read the editorial of that task here to find how the graph looks like.
•  » » » 8 years ago, # ^ |   +9 These two problems share a common idea, but I think yours is much harder and more challenging :)
 » 8 years ago, # |   +3 pending system testing ................
 » 8 years ago, # |   0 Great questions! But super tough! I, for one, am looking forward to the editorial ;)
 » 8 years ago, # |   +3 For the first time, I have to write a test generator for B to make sure that it won't get TLE.
 » 8 years ago, # |   0 Locked my problem too late, only to find 12 hacked solutions on Div 2 Problem A. What is the highest number of hacks for that problem? Any idea?
•  » » 8 years ago, # ^ |   0 I'm sure I'm one of the people with 12 hacks. Not sure whether that's the highest.
 » 8 years ago, # |   +10 At the end of the contest I felt that this contest must not be a usual contest.When I see the home page I see Chinese writers.I get the reason ... :)
 » 8 years ago, # |   0 awesome set of questions... if possible anyone plz explain the approach of Div2-C
 » 8 years ago, # | ← Rev. 2 →   +28 Towards the end of the contest I tried to hack sas4eka's solution for problem A (Div1) by trying to make it get TLE (it seems that for each pair of consecutive positions it iterated through all the occurrences of the first number in the pair, so a test case like N=M=100000 and 1 2 1 2 ...... 1 2 should make his solution get TLE). Since the test case was large, I wrote a generator and wanted to upload the generator (after selecting generated input in the Hacking interface). I selected my generator's source file and then I pressed "Hack". Instead, I got some error that either a test case or the generator must be specified (or something similar). I tries setting some generator parameters and pressed Hack again — nothing happened this time either. Then the contest ended and my hack was not submitted. Perhaps I did something wrong, because I usually do not try to hack other's solutions during the contest and I am not familiar with the Hacking interface. My question then is : can I try to hack other people's solutions outside of a contest ? (just for practice) If not, then how can I become familiar with the Hacking interface so that next time I know what to do? (because it seems that the interface is not as straight-forward as I was expecting it to be). And I would rather not waste time from a real contest for this. Note that in TopCoder it is possible to challenge solutions even in the Practice room, so maybe something similar should also be possible in Codeforces? (in case this is already possible, then please just ignore my question)Later edit: The solution I was trying to hack did get TLE in the end, so I guess my hack would have been successful... had I known how to properly submit it.
•  » » 8 years ago, # ^ |   +8 As far as I remember there are two tabs, one for submitting usual test (in text form or by specifying a path to file with a test) and another one for submitting generator (path to generator [and some parameters to pass to generator]). Perhaps, you wrote something in the first form (or had selected file there) before to switch to the generator form.
•  » » » 8 years ago, # ^ | ← Rev. 2 →   +16 Hm.. yes, I actually did :) At first I didn't notice the 2 tabs and I selected the generator code where the upload of a test file was. Then I noticed the tab was called "manual tests" (or something similar) and I selected the other tab (for generated input), where I did what I said in my post. I wouldn't have imagined that whatever actions I did in the first tab would still be considered when I switched to the other tab. This is non-intuitive to me and only enhances the idea that one needs to first be sufficiently familiar with the Hacking interface in order to use it properly — which is bad, given that we seem to only be able to access that interface during contests.Thank you for your answer.
•  » » 8 years ago, # ^ |   +13 You can practice hacking while participating out of competition in a Div2 contest.
•  » » » 8 years ago, # ^ |   +13 Thank you for your answer. I thought about that myself, too. I think I will do just that in one of the future Div2-only contests. However, if I were a Div2 contestant, that would leave me with no way to practice hacking outside of competition.
•  » » » » 8 years ago, # ^ |   0 Hi, just a friendly reminder that Testing Round will be held today for you to practice hacking solutions. Hope you get notifications for comments :-)
 » 8 years ago, # |   +3 What is up with Time limit exceeded on test 46 for Java solutions on Div2-B ?
•  » » 8 years ago, # ^ |   +2 If i'm not mistaken, Arrays.sort(a) in Java 7 for primitive types runs in O(N^2) on worst case (quicksort with selecting median as pivot).
 » 8 years ago, # | ← Rev. 4 →   +9 Why does Div 2 Problem C have the same point with Problem B? The successful submission rate is 80 to Unable to parse markup [type=CF_TEX]. I once believed points are distributed using the complexity of the problems, I guess not.Another ironic part is that Problem A with just as many correct submission with Problem B has 500 points.
•  » » 8 years ago, # ^ |   0 My opinion is that C has rather difficult algorithm to think of, while B tests you whether you know the proper sorting algorithm for the problem or not. (Note that I didn't solve either and I'm not sure I have the correct algorithm for B; handling the sorted query needs to sort by counting sort?) Both are relatively obscure for an average Div2-er.
•  » » » 8 years ago, # ^ |   +1 Problem B doesn't require any special technique other than understanding cumulative sum. What I did was compute the cumulative sum of the unsorted array, then sort the array and compute its cumulative sum. The rest was just input and output.
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 For problem C (DIV 2) Only 59 got accepted after system test and for B it is around 1000. Still both have same points. Is there any chance of change in points distribution now?
 » 8 years ago, # |   -6 loved this contest!! I have now many things to learn in this contest's tutorial.But "wow!!" for the character names. :D
 » 8 years ago, # | ← Rev. 2 →   +44 #define int long long is evil
 » 8 years ago, # | ← Rev. 2 →   0 Can anybode explain me this pretest on C div2 (A div1)? Why the answer is 7?5 102 5 2 2 3 5 3 2 1 3Thanks.
•  » » 8 years ago, # ^ |   0 change 5 on 2: 2 2 2 2 3 2 3 2 1 3
•  » » 8 years ago, # ^ |   0 Let's change all 5's in 2's, we get |2-2| + |2-2| + |2-2| + |2-3| + |3-2| + |2-3| + |3-2| + |2-1| + |1-3| = 7.
•  » » » 8 years ago, # ^ |   0 Thanks. I lost, that ALL marks will be rewritten.
 » 8 years ago, # | ← Rev. 2 →   +2 Java is evil , during contest same solution of problem B(Div2) got TLE in java 6692351 but in c++ , 326ms 6701333
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 Yes. Java Arrays.sort() is O(N^2).EDIT : Only for primitive type array
•  » » » 8 years ago, # ^ |   -8 Arrays.sort() uses a merge sort, so it is O(n log n).
•  » » » » 8 years ago, # ^ |   0 See the documentation of Arrays class Implementation note: The sorting algorithm is a Dual-Pivot Quicksort * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm * offers O(n log(n)) performance on many data sets that cause other * quicksorts to degrade to quadratic performance, and is typically * faster than traditional (one-pivot) Quicksort implementations.So in some set it can be O(n^2)
•  » » » » » 8 years ago, # ^ |   +4 But that requires a very evil problemsetter that targets Java specifically...
•  » » » » » » 8 years ago, # ^ |   0 It's just coincidence may be
•  » » » » » » » 8 years ago, # ^ | ← Rev. 3 →   0 It cannot be coincidence. Quick sort is guaranteed to be O(n log n) with high probability , which means the chance of running O(n^2) time converges very quickly to 0 as N increases (even faster than inverse exponential growth[1/2^N]). It must have been a designed input. I really hate such behavior ...Exactly the same thing happened for pascal programmers who copied sample quick sort procedure in FPC compiler: See This post (in a Chinese forum) . However zhonghaoxi said they were using random generator. UPD User 2333333 is the one who submitted that input instance, though it looks quite normal, there is a previous one got generator compile error and I opened the protocol and it says: The hack uses generator hack.java:464: error: cannot find symbol new Thread(null, new Java7QuicksortKiller(), "", 128*1024*1024).start(); ^ symbol: class Java7QuicksortKiller location: class hack 1 error And that's why this is happening... Such things are so disgusted, trying to attack a certain language's bugCorrection: test 45 is target to median pivot sort algorithm. (Many pascal solution fails on test #45) This is a well-known input to hack "standard" quick sort. But Java7QuicksortKiller ... so evil WTF
•  » » » » » » » » 8 years ago, # ^ |   +8 > Such things are so disgusted, trying to attack a certain language's bugAnd why exactly is that bad? The problem statement does not seem to exclude hard cases. You have one problem statement and plenty of tools (programming languages) to choose from. There is no one perfect tool. Learning the weaknesses of your tools, and how to circumvent them, is essential if you want to use the tools efficiently.Specifically in Java, not only you can use a double-pivot Quicksort for primitive types, you can also box them and utilize Timsort for objects which is guaranteed to be .
•  » » » » » » » » » 8 years ago, # ^ |   +8 Hi Grand Master :DDo you have any idea on why the quicksort in the java library is not randomized?And why it is not possible to utilize Timsort on primitive types?And why it is possible to shuffle a list of objects but not and array of primitve types?Thanks in advance.
•  » » » » » » » » » 8 years ago, # ^ |   +8 ====================================================================Disclaimer: Note that I'm not anywhere close to a Java expert.As I understand it, library quicksort is optimized for the general case (not the corner cases). Using randomness of any sort would slow it down in the general case. Timsort, on the other hand, is stable, which can come in handy for objects but is useless for primitive types. For an additional bit of reasoning, see here and here.To use Timsort on primitive types, you can box them into their respective wrapper classes. The same goes for shuffling. The language inherently does not allow using generics on primitive types.
•  » » » » » » » » » 8 years ago, # ^ |   +8 Thanks for the explanation and the links.
•  » » » » » » » » » 8 years ago, # ^ |   -8 That hack brought down over 80% of Java solutions, do you think it is a good thing or not? Personally I never support it
•  » » » » » » » » » 8 years ago, # ^ |   +8 =============================================================It may be seen as unfair, in the sense that a test targets a particular inefficiency of a particular tool. Indeed, some but not all of the participants expect challenges to be "pure", in the sense that once you think of the right solution, the implementation should not require much tweaking.It may be seen as fair, in the sense that there are no artificial indulgences for users of particular tools. As far as I understand, every other tool does not have a problem with that test. If so, it's a problem with the tool.Personally, I stick with the latter argument, bearing in mind that the particular inefficiency of Java is so easy to circumvent (boxing + Timsort).The important part is that it's a learning opportunity for the authors of these over 80% solutions.
•  » » » » » » » » 8 years ago, # ^ |   +21 Such things are so disgusted, trying to attack a certain language's bug I am not sure if this is your intent, but your comment sounds as if you are accusing someone who just followed the rules to score as much as possible.
•  » » 8 years ago, # ^ |   +8 This is a well known problem with java when you sort a primitive type array it uses quick sort which will result in O(N^2) runtime on some specific cases. This had been discussed on many posts on codeforces beforeThe solution is to make your arrays of the class type not the primitive type, i.e int -> Integer, long -> Long. The JVM will use merge sort instead of quick sort in this case.
•  » » » 8 years ago, # ^ |   +3 Thanks , I will take care of this from next time.
•  » » » 8 years ago, # ^ |   0 What? Doesn't the quicksort use a median selection algorithm that makes it pretty difficult to find an O(n^2) sequence?
•  » » » » 8 years ago, # ^ |   +3 Well there are already some generators that were posted on codeforces. Check the links in my comment.
•  » » » » 8 years ago, # ^ |   +9 NoAnd it is not only difficult to find array on which quick sort with median will work square time, it us outright impossible
•  » » » » » 8 years ago, # ^ |   +1 Right, I guess I meant "median approximation algorithm" such as "median of three".
•  » » 8 years ago, # ^ |   0 same thing happened with me, on same pretest.
•  » » 8 years ago, # ^ | ← Rev. 2 →   +8 Once Again disappointed by the Java standard library :( I had the same problem. It seems The quicksort implemented by Arrays.Sort is not randomized ;(I had a "time limit exceeded" and solved it by adding a single shuffle (using the fonction below) before calling Arrays.sort and now i have 120ms. u_u// Implementing Fisher–Yates shuffle static void shuffleArray(int[] ar) { for (int i = ar.length — 1; i > 0; i--) { int index = rnd.nextInt(i + 1); // Simple swap int a = ar[index]; ar[index] = ar[i]; ar[i] = a; } }RANDOMIZATION IS A MUST AGAINST EVIL PROBLEM SETTERS è_é just kidding ;)
 » 8 years ago, # | ← Rev. 2 →   0 My position is 79 on the final standing & I need 114 more to be purple... Please update it quickly... :( UPD: I can't... :(
•  » » 8 years ago, # ^ |   0 looks like you missed by some margin , so close.
•  » » » 8 years ago, # ^ |   0 I missed Blue by 1 rating point :(
•  » » » 8 years ago, # ^ |   0 how true your speech were !!! :'(
 » 8 years ago, # |   0 In Problem A, DIV 1, when you merge page x to y, so you copy the content of page x to page y also. Thus we will be able to find the answers on page x, also.. untill and unless we remove actually remove that page, then we will have to turn less number of pages and answers will change.. Thus th eline ", all elements in sequence a that was x would become y" in the question statement is ambigous with the description. I coded my solution assuming that if we merge page x to y, the will be able to find answers of page X on both page X and Y and thus failed.
•  » » 8 years ago, # ^ |   0 That sentence stated exactly how a merge affects sequence a. Since the answer depends solely on a, to me this statement can not be ambiguous.
•  » » » 8 years ago, # ^ |   0 Anyway, keeping answers on both x and y will make the question more interesting and its solvable with a similar approach.
•  » » » » 8 years ago, # ^ |   +3 How do you solve your version of the problem? I'm quite interested :)
•  » » » 8 years ago, # ^ |   +8 I agree that it is not ambiguous, but it would have been much better if the problem statement said “she would move” instead of “she would copy.” It confused me first, although I finally assumed that it was just a suboptimal choice of the word and did not ask for clarification.By the way, I enjoyed the contest, thank you for the hard work!
 » 8 years ago, # |   0 Good Contest =D Still have Time limit Exceed in B- Problem :/
• »
»
8 years ago, # ^ |
-22

# mo7n

 » 8 years ago, # |   +8 May be I tell you some not very popular thought, butWhy did email invitation come in the very deep night between Friday and Saturday?Shame on me not to visit codeforces frequently, but ...
 » 8 years ago, # |   +89 very lucky to get #1 :)After those bad days breaking up with girl friend, seems I can finally walk out of it and training for world final :)
 » 8 years ago, # |   +3 thanks, i was happy with contest
 » 8 years ago, # |   +17
 » 8 years ago, # | ← Rev. 2 →   +1 I tried to implement problem Tachibana Kanade's Tofu and got TLE with MSC++ Compiler. I tried to resubmit it with GNUC++, it got AC >_
•  » » 8 years ago, # ^ |   +8 The problem is in Arrays.sort implementation in Java. It is vunerable to anti-quick-sort test. You should random shuffle the array before sorting it.
•  » » » 8 years ago, # ^ |   0 Sorry, I don't get it completely. You mean I should swap some items before using Arrays.sort ? Or not using it is better? Thanks for your answer.