witua's blog

Codeforces Round #136
By witua, 12 years ago, translation, In English

Tomorrow, in 4 and half hours before the end of the summer (check your zone), Codeforces Round #136 will take place. I am the author of this round, it's my 6th contest on CF.

Gerlad Agapov (Gerald) is helping me in preparing the problems. Translations will be done by Maria Belova (Delinur). Thanks to them.

I hope you will like this round. The points distribution will be standart.

Thanks!

7 user in the first division solved all 5 problems, here they are:

  1. peter50216
  2. yeputons
  3. winger
  4. rng_58
  5. RAD
  6. al13n
  7. KADR

Meanwhile, in second division, Top-4 looks like this:

  1. blue.boy
  2. de_troit
  3. lxyxynt
  4. ilona

You can find the editorial of the contest here.

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

Comments Comments (94)
| Write comment?
»
12 years ago, # |
  Vote: I like it +28 Vote: I do not like it

And again your contest at the very end of august(round #84, 29 aug 2011).
47 to all.

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

Will the problems be sorted by difficulty or not?

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

What a pity that I cannot attend this match because it is 1st,Sep in my timezone and I must back to school. But I wish everybody will enjoy this match and do your best!

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

    We should back to school the day after tomorrow, so we can do.

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

    I must back to school too.For I haven't finished my homework,I have to stay up to finish them.So I can sttend this match.How happy!

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

      My teacher told me that we'll have an exam on 3rd and it realy shocked me...I wish my test scores will be as many as my rating on CF...700 is enough in fact...

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

    Back to school on Saturday, poor you guy. Anyway, virtual participation is still available for you later :)

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

      It's the last year for me in middle school,so no matter Monday or Saturday is busy for me...

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

Wow! Mr. witua always your problemset is great! ;) Thanks for preparing another contest!

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

The cute faces are nice!

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

Let's hope for a * lucky * round to all :)

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

    Unfortunately, it can't be lucky for all of us — someone has to be a looser..:)

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

      It depends on what you expect for the match.

      If I solve 3 or 4 problems, I learn something new (a good idea, algorithm, etc) from one of the problems I solve and I feel happy with my solutions, but many people are lucky so I lose rating, I consider myself lucky in the contest.

      Besides rating is not everything, you can lose rating and then increase your rating in another match, but a good idea or solution that makes you learn something interesting, is never lost.

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

I was expecting it to be on the 29th. Was you n th birthday too great to find a time for contest this year?

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

    Unfortunately, it was scheduled before I was setted as an author. Sorry for disappointing you.

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

I 've Been Missing Normal Score Distribution ! Thank You ! I Wish Luck for Everyone :)

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

Hope all the best from this contest!!!! ........Good luck and Have fun everyone ......:)

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

Can somebody explain the solution for Div2-D ? It drove me nuts.

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

    I used sqrt — decomposition.

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

    let's find all possible values of x for interval [1..n]. there will be no more than 2 * sqrt(n) such values. iterate over values of constructed set, and solve problem for all intervals. O((n + m) * sqrt(n))

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

    I use segment tree :d

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

      Me too, a offline 2d segment tree's painful code :-|

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

        Actually he used 1d segment tree

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

can somebody tell me how to solve problem D in div 2?it drives me crazy...

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

In my opinion, Div2C is the easiest problem.

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

    No. The easiest problem is A, of course :)

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

      A is easy too :) but I had to implement 'f(x)' to solve it :D

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

    Agree,but I made a little mistake and spent all time in it.

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

Lot of TLE's in div2 problem B :)

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

    In div2_B I hacked 4 contestant with one test — max test.

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

      I hacked 5 contestants with max test.

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

        how i can hack solution?

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

          First, you need to block your solution (you can do it on tab "Problems" by clicking on lock icon). Then you'll be able to view and hack solutions of blocked problem by double-clicking into cells in your room.

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

I failed DIV I — C 4 times. Two of them were because the examples were symetric so I misunderstood the way of rotating (I was shifting to the right instead of shifting to the left), and in all the submissions I failed pretest 5. I cannot find where to get the pretests, but it seems a lot of people failed that test case. Can anyone who failed that case, and then fixed it, tell me what was the mistake on your code? Does anyone know where can I find the test case?

Also for problem B the problem statement was wrong. Even if the examples clarified it, you can choose x = 0 and it also works (it doesn't say x > 0 or x is a positive integer, it just says "number x" and 0 is a number.

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

    I misunderstood the way of rotating too!

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

    Yes, that was a mistake causing WA on test 5.

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

      I tried with both ways of rotating and still got WA.

      I looked at the test case I failed and my bug was considering the permutations as cyclical. I can't believe I looked for the bug for almost an hour and couldn't find it!

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

        Same with me. Fortunately, I decided to skip it after a bunch of submissions and had enough time to solve another problem.

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

      So I WA for 6 times!

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

    where can I find the test case? -> It looks like pretest #5 during the contest is called test #5 afterwards.

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

Seems like there is a test case in problem A that is designed to stuck java's Arrays.sort

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

    Java can't sort the array with 100 000 integers. How unfortunate.

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

      That's why my solution failed. Is it the problem of java library or the server problem?

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

        It's a problem of java library

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

    This is not happened the first time here :(

    Thats why I intentionally used merge sort and got passed :) Soln

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

    winger's solution passed it with Arrays.sort — 1980 ms :|

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

    my submission for Div2 — C got TL using Arrays.sort , Is Arrays.sort poorly implemented?

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

      Remember , Arrays.sort in java is implemented using quick sort which has a worst case complexity of O(n^2) .Read this
      So you can do
      - shuffle the array randomly before using Arrays.sort()
      - use mergesort, heap sort ;)

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

      No, it's because someone is design the data intended to let java solution TLE

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

    I submitted the same solution in practice, in the contest it failed test case 80 with TLE, in practice it passed test case 80 in 90 ms. (it failed with TLE on test case 91 anyway) what's the reason behind this? thanks

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

System tests are still testing submissions for the first 10 minutes of contest (in DIV I) and it already tested 26% of the submissions. That means that the goal of this match was being very fast to solve problem A, that's not very nice. In my opinion the difference of dificulty between problems A and B was very big.

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

Am I the only one to have solved div2 A recursively as in the description? :D

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

I didn't do well,but I still like this round very much.It is my first time to do Div1.Thank you!

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

Somebody used an anti-quicksort challenge again. So stupid of me!

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

This problemset is interesting~~ enjoy a lot... Although I have made a silly mistake in Problem B >_<. One of my friends' Java solution fail because of Arrays.sort's issue...Actually I don't think it is good to put such a case >_<...

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

    lose one point in rating and drop to #7 T_T...... Sigh...It seems I'm always making silly mistakes>_<... How can I get rid of it ?

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

    Problems with Arrays.sort and HashSet/HashMap were discussed a lot, but in Russian. These tests should be in system testset because they are used for hacks.

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

It Was a Very Nice problemset and I myself really enjoyed it ! Thank You All for preparing contest (and ofcourse participating The Contest :) ) . But I had a Problem With Task E Div1 in Place where The problem Described the pair l,r many people didn't notice that its a1,,,,al,ar,....,an :D i had 4 WA because of it and Didn't manage to read the rest of the problems (after A I jumbed to E :D)

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

witua's rounds have always been good for me, and ratings is always increasing..

Round # Rating diff
77 DNP
84 -47
91 +57
104 +87
129 +96
136 +226
Thank you witua and hope this relation continues ;)

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

I'm 256. in final stadings. And I have 2560 points :D. Interesting numbers :)

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

I did a little mistake in problem C div 2. I counted the number of changes and then, I divided it by two. When I saw that 3 — 2 — 1 gave me only 1, it was late, I was blocked this solution. I got it, it not the same return (cant <= 2) that return (cant / 2 <= 1). Thanks for this great contest.

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

    I was able to solve A-D correctly. After contest... :( But I enjoyed the problems, they are really interesting.

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

my code is giving correct output(=91) on test case 9 but here it is giving wrong answer on test case 9 2084000

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

    i did submit your solution and it got AC. i just changed, the size of s1,s2,s3 and i submitted it with GNU C++ 4.6, instead of GNU C++0x .

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

      sorry, i forgot the link

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

        @fab But what can be the reason of increasing array size?? on my system it is giving correct answer for test case 9.(=91), for even an array of size 10??

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

          i really don't know. it did give the right answer in my computer too, i just increased the array size to be sure ( it almost never hurts to let it have some air to breath ) i asked some of my friend, one of them, said, it might be the C++0x, and it still might not be completely perfect. but again, i don't know. sorry.

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

          actually 10^9 is 10 digits, so your arrays are too small.

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

            thanx actually i use bloodshed dev c++ compiler which gives correct output even when array size is exceeded by 1 or 2 i think.....

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

              Stop using it, it is old and unmaintained. Try MinGW+Code::Blocks or MS VC++ Express.

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

Can someone please explain in detail how to solve problem D in Division II?

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

    number x must appear more than x times,add them together,so the numbers that are useful are no more than sqrt(n).You can use the prefix sum and calc all the number'time by brute force.Notice the time limit is 4 seconds.(sorry,my English is poor.)

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

    By the way,who is the person in your photo? It seems to come from Star Wars.

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

      It is Luke Skywalker in his pilot costume. :)

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

        I am a fan of Star Wars,so glad to see him here.:)

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

thanks for preparing the contest and the problemset. i had a little problem with task C ( div.1 ) and i thought it might be someone elses' problem, too: i saw that a lot of people ( including myself ), got wrong answer on test 5 and i think, they made the same mistake that i did, and it could easily be prevented, just by making better thought, sample cases. the problem was that, i ( and i think some other contestants ) did make a little mistake in understanding how the shift works, so, the solution we outputed, was just bacwards. but if the test case 5 ( which is a reasonable case with n = 10 ) was a sample case, we could easily have realized this and get it right.

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

    I WA on test5 too,and I realized the reason after my brute force program get Wa too.I think it is important to understand the problem more carefully.I just hope that we won't make the same mistake in the future contests;

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

      i do think it's important to be careful and try not to make mistakes, like this. but it's not an implementation problem, and in this problems, finding the algorithm is the most important part, not little things like this. and second of all, i think the idea behind sample cases, is to prevent this kind of mistakes ( and/or for understanding the problem, better ) and it seems to be a common mistake, because at least more than half of the contestants ( the ones that i checked ) who got WA in this problem, did get WA at least once on 5. i don't think it's that important.

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

        Maybe you are right.

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

It was my first CF round where I was to rank up, after 3 contests losing rating...

I found the problemset very interesting and I was able to get accepted for 2 problems, A and C!!!

I wish that we can have more rounds like this in a near future and wish good luck to everyone in the upcoming school year as well!!

Bruno

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

Hi,

Can anyone help me in knowing what can be done in https://codeforces.net/contest/220/submission/63940597 whose complexity is O(nlogn + m sqrt(n)logn) to get AC.

(Problem:https://codeforces.net/contest/220/problem/B)]

Thanks,

→ Reply