huzecong's blog

Codeforces Round #248
By huzecong, 11 years ago, In English

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:

  1. YuukaKazami
  2. KADR
  3. RAVEman
  4. Seyaua
  5. ikatanic

Top 5 of Div. 2:

  1. jason_yu
  2. Kann
  3. tomsyp
  4. keavil
  5. Kazakh_Alga

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

  • Vote: I like it
  • +230
  • Vote: I do not like it

Comments Comments (131)
| Write comment?
»
11 years ago, # |
  Vote: I like it +61 Vote: I do not like it

Actually, it takes place on Saturday, not Sunday :D

Pity 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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

    Sorry, the time's now fixed.

    And nice doge :)

    → Reply
»
11 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks

      → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
11 years ago, # |
  Vote: I like it +29 Vote: I do not like it

nice time for me:))

→ Reply
»
11 years ago, # |
  Vote: I like it +37 Vote: I do not like it

Are huzecong and wyx528 a pair of lovers?>_<

→ Reply
»
11 years ago, # |
  Vote: I like it +30 Vote: I do not like it

orzzz... Hoping to see problems without too hard data structures

→ Reply
»
11 years ago, # |
← Rev. 4   Vote: I like it +10 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +39 Vote: I do not like it

Contest kicks off at 8.00 am in my country. Coding is always a good activity to begin your day.

→ Reply
»
11 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Chinese round again~

orzzzzz

→ Reply
»
11 years ago, # |
  Vote: I like it +4 Vote: I do not like it

marriage!

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

Nice time for me, Happy to see the problem setter from my hometown :)

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    happy to see div1.E from your pic!

    though maybe no one can solve it ……

    → Reply
»
11 years ago, # |
  Vote: I like it +19 Vote: I do not like it

This Score distribution not standard :)

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    At least it's more standard than dynamic distribution :D

    → Reply
»
11 years ago, # |
  Vote: I like it +31 Vote: I do not like it

3000.. How difficult div1-E will be..

And in my memory, almost all of Chinese round, nobody can solve E during the contest >_<

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

No 1000-score problem [again]?! Is this a new method of scoring?!

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Hope,I can give better look to my rating graph today :D btw,Best of luck ... !!! :)

→ Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it +14 Vote: I do not like it

Kill la Kill, Clannad, Kami-sama hajimemashita, angel beats, kyoukai no kanata, white album :D

→ Reply
»
11 years ago, # |
  Vote: I like it -34 Vote: I do not like it

Chinese again! :(

→ Reply
»
11 years ago, # |
  Vote: I like it +32 Vote: I do not like it

omg the problem set is harder than Bruce Lee's punch X_X

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    On the bright side, the system testing should be fast :)

    → Reply
»
11 years ago, # |
  Vote: I like it +7 Vote: I do not like it

How interesting...

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve A div 1 / C div 2?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I submitted a ternary search.

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you prove that we should merge it to the median?

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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.

        → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

What is the approach to solve Div2 Problem C?

→ Reply
»
11 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Tricky Div1 A is tricky :'(

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Yup. I think a lot of sources at A will not pass...

    → Reply
»
11 years ago, # |
  Vote: I like it +23 Vote: I do not like it

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 !

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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 :).

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +55 Vote: I do not like it

    Especially if they are Japanese

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    I simply replaced them with either 'Jackie Chan' or 'Bruce Lee' in my mind, for simplicity :D

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    actually they are all characters in Japanese anime or games……

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    All names in the statements are from Japanese animes... So they're not Chinese names :)

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Why my solution got Wrong answer on pretest 2? 6700945 UPD: found error x.x

→ Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Tricky contest...

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

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!

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain a bit about the two solutions?

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.)

      → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Click Zan!

      → Reply
»
11 years ago, # |
  Vote: I like it +16 Vote: I do not like it

How to solve D?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    network flow

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      I'd appreciate some more detailed explanation.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Wait for the Editorial, we will write it there

        → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +13 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      These two problems share a common idea, but I think yours is much harder and more challenging :)

      → Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

pending system testing ................

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Great questions! But super tough! I, for one, am looking forward to the editorial ;)

→ Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

For the first time, I have to write a test generator for B to make sure that it won't get TLE.

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm sure I'm one of the people with 12 hacks. Not sure whether that's the highest.

    → Reply
»
11 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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 ... :)

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

awesome set of questions... if possible anyone plz explain the approach of Div2-C

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +28 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it +16 Vote: I do not like it

      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.

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    You can practice hacking while participating out of competition in a Div2 contest.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hi, just a friendly reminder that Testing Round will be held today for you to practice hacking solutions. Hope you get notifications for comments :-)

        → Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

What is up with Time limit exceeded on test 46 for Java solutions on Div2-B ?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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).

    → Reply
»
11 years ago, # |
← Rev. 4   Vote: I like it +9 Vote: I do not like it

Why does Div 2 Problem C have the same point with Problem B? The successful submission rate is 80 to 1066. 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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

      → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
»
11 years ago, # |
  Vote: I like it -6 Vote: I do not like it

loved this contest!! I have now many things to learn in this contest's tutorial.
But "wow!!" for the character names. :D

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +44 Vote: I do not like it

#define int long long is evil

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anybode explain me this pretest on C div2 (A div1)? Why the answer is 7?

5 10

2 5 2 2 3 5 3 2 1 3

Thanks.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    change 5 on 2: 2 2 2 2 3 2 3 2 1 3

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks. I lost, that ALL marks will be rewritten.

      → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

Java is evil , during contest same solution of problem B(Div2) got TLE in java 6692351 but in c++ , 326ms 6701333

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yes. Java Arrays.sort() is O(N^2).

    EDIT : Only for primitive type array

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      Arrays.sort() uses a merge sort, so it is O(n log n).

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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)

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it +4 Vote: I do not like it

          But that requires a very evil problemsetter that targets Java specifically...

          → Reply
          • »
            »
            »
            »
            »
            »
            11 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            It's just coincidence may be

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              11 years ago, # ^ |
              ← Rev. 3   Vote: I like it 0 Vote: I do not like it

              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 bug

              Correction: 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

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                11 years ago, # ^ |
                  Vote: I like it +8 Vote: I do not like it

                > Such things are so disgusted, trying to attack a certain language's bug

                And 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 .

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 years ago, # ^ |
                    Vote: I like it +8 Vote: I do not like it

                  Hi Grand Master :D

                  Do 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.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 years ago, # ^ |
                    Vote: I like it +8 Vote: I do not like it

                  ====================================================================

                  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.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 years ago, # ^ |
                    Vote: I like it +8 Vote: I do not like it

                  Thanks for the explanation and the links.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 years ago, # ^ |
                    Vote: I like it -8 Vote: I do not like it

                  That hack brought down over 80% of Java solutions, do you think it is a good thing or not? Personally I never support it

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 years ago, # ^ |
                    Vote: I like it +8 Vote: I do not like it

                  =============================================================

                  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.

                  → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                11 years ago, # ^ |
                  Vote: I like it +21 Vote: I do not like it

                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.

                → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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 before

    http://mirror.codeforces.com/blog/entry/4827 http://mirror.codeforces.com/blog/entry/7108

    The 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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thanks , I will take care of this from next time.

      → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What? Doesn't the quicksort use a median selection algorithm that makes it pretty difficult to find an O(n^2) sequence?

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Well there are already some generators that were posted on codeforces. Check the links in my comment.

        → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        No

        And it is not only difficult to find array on which quick sort with median will work square time, it us outright impossible

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Right, I guess I meant "median approximation algorithm" such as "median of three".

          → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    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 ;)

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

My position is 79 on the final standing & I need 114 more to be purple...

Please update it quickly... :(

UPD: I can't... :(

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    looks like you missed by some margin , so close.

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Anyway, keeping answers on both x and y will make the question more interesting and its solvable with a similar approach.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        How do you solve your version of the problem? I'm quite interested :)

        → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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!

      → Reply
»
11 years ago, # |
  Vote: I like it +8 Vote: I do not like it

May be I tell you some not very popular thought, but

Why did email invitation come in the very deep night between Friday and Saturday?

Shame on me not to visit codeforces frequently, but ...

→ Reply
»
11 years ago, # |
  Vote: I like it +89 Vote: I do not like it

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 :)

→ Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

thanks, i was happy with contest

→ Reply
»
11 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Round Stats

→ Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

What means Let_us_play_CF?

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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 >_<

http://mirror.codeforces.com/contest/434/submission/6710299

http://mirror.codeforces.com/contest/434/submission/6710309

As I remember, in some problems, MSC++ is faster than GNUC++, some others, GNUC++ is faster than MSC++.

Luckily, I couldn't solve this problem while competeting ^_^, if not, the contest would end with many regrets ^^.

Anw, thanks for nice problems : D

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi all. Could you please describe why I'm getting TLE on this? (Problem B Div 2) It's confusing for me because the code passes the 5th test with n = m = 10^5 but it gives TLE on test 46 whose parameters are : n = 88888, m = 1; Here's my submission Thank you.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply