KaiZeR's blog

Codeforces Round #266 (Div. 2)
By KaiZeR, 10 years ago, translation, In English

Hi Codeforces!

We would like to invite you to participate in Codeforces Round #266 Div2, which will be held this Friday, September 12th at 19:30 MSK. As usual, Div1 participants can take part out of the competition.

Problems have been prepared by Antoniuk and me. It's the second round prepared by us, and we still hope it won't be the last.

We want to thank Gerald for helping to prepare this round, Delinur for translating the statements, and also MikeMirzayanov for Codeforces and Polygon.

It will be used a standart scoring: 500-1000-1500-2000-2500.

Gl & hf!

UPD. Round has finished. Thanks for participating.
UPD2 Congratulations to top-5 participants:

1) dominator_hza
2) Final_Battle
3) free_pascal
4) vanhanh.pham
5) NUOUN

UPD3. Editorial .

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

Comments Comments (87)
| Write comment?
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I really liked k-tree! Hope to see some more problems like that!

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

Brazil's ACM/ICPC First Phase will be held this Saturday, this contest came in a good time for a last preparation. Thank you.

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

it won't be 500-1000-1500-2000-2500?

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

i really shocked when see only 4 comments :D usualy it's in order of 50-100

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

    how will be destiny of worse ?

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

      He discovered a white color under the grey wow :D

      but i don't think there is a negative rating he will just stop at zero :D

      [UPD] He got negative rating now i'm surprised :D

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

        No!! He has broken all the barriers!

        Even before tourist could reach 3300, he has splurged to -37 ! Unbelievable!

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

        [Rating graph of worse... ]Image Hosted At MyspaceGens

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

      He/She has registered
      In the last contest his/her rating changes was -48. tourist missed rating 3300 for a single point in his last contest. Will worse touch the 0 rating ???

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

      I don't think he uses Russian version

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

        But he does speak Russian, you can see this from his comments

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

    I think users didn't find any specific problem in the text of the blog entry or ... to talk! Everything was ok :)

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

Wow! tourist just finished in 22 minutes!

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

    Where is scoreboard for out of competition participants?

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

      There should be a check box to toggle on/off for unofficial.

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

Is there any problem in java compiler? Runtime error for me even in custom invocation, working fine in my computer. UPD- BigInteger function nextProbablePrime() giving runtime error on codeforces.

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

.

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

hard math contest !!!

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

sometimes easy math is very hard , how to solve B?

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

    If you'll increase both numbers by more than 1e5, then product will increase by more than 1e10. But it is clear that you can get better answer, so you may check only all possibilities of increasing one of numbers by 0..1e5, and for every such possibility calculate required increasing of second number.

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

how to solve D??

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

    DP[i][j] — how many ways to solve first i points while having j open segments.

    You have following moves at position i:

    • close some of previous segments, don't open new (j+1 ways to choose segment to close)
    • close some of previous segments, open new (j ways to choose segment to close)
    • open segment and close it in same cell (1 way)
    • open segment and don't close anything here (1 way)
    • neither open nor close segment here (1 way)

    And for every possibility you should check that number of segments covering position i after such move is h-a[i];

    Answer will be in DP[n][0] (you solved all points, all segments were closed).

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

      Also there is an O(n) solution 7772910

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

        Yes, and you can also improve naive DP[i][j] to something similar to your solution, that will also work in O(N), noticing that we should care about only few values of j for some fixed i (if j<h-ar[i]-1 or j>h-ar[i] then it makes no sense).

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

      Thanks very clear explanation

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

    A simple linear solution. Consider the sequence bi = h - ai. If some two bi, bi + 1 differ by more than one, the answer is 0, since some two blocks begin or end in the same position.

    Otherwise the answer is the product of values val(i, i + 1):

    1. if bi - 1 = bi + 1, then we must end one of the bi - 1 blocks. This can be chosen in bi - 1, so val(i, i + 1) = bi;
    2. if bi - 1 = bi, then we can end any of bi - 1 blocks that still continue at position i - 1, and start a new block at position i. Or we can continue all of the blocks. So val(i, i + 1) = bi + 1;
    3. if bi - 1 = bi - 1, we should begin a new block, so val(i, i + 1) = 1;
    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What does Val mean?

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

      What is the meaning of val(i,i+1) here?

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

        Imagine that ending a segment and starting a new segment is the same as putting a red border between two cells: see this picture:

        The white cells must be covered by the segments [l;r]. Thus if $$$b_i \neq b_{i+1}$$$, we must either end a segment (if $$$b_i > b_{i+1}$$$), or start a new segment (if $$$b_i < b_{i+1}$$$). If $$$b_i = b_{i+1}$$$, we can either end a segment and start a new one, or do nothing.

        $$$val_{(i,i+1)}$$$ is the number of ways to do that in each case. In the picture, $$$val_{(i,i+1)}$$$ corresponds to the number of ways you can put a red border between the $$$i$$$-th and the $$$(i+1)$$$-th columns. Note that you cannot put more than two red borders between the same two columns $$$i$$$, $$$i+1$$$.

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

I think this time problem B was one of the hardest problem B's I have ever solved...

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

    Yeah, I was confused about how to solve (a + x)(b + y) ≥ 6n where x and y are the number by which a and b are incremented. I tried to solve this for most of the time and I couldn't concentrate on problem C because I couldn't solve B!

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

      Either x or y is small: just check all values up to million

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

    A lot of us tried a greedy approach or maths, making it seem tough, but a brute force approach would have solved this.

    As pointed out by I_love_Tanya_Romanova and aaaaaaaaaaaaaaaaaaaaaaab in the comments, both numbers cannot exceed 1e5 (LeBron's idea) or sqrt(6*n) (AvadaKedavra's idea). You just check a or b for all possibilities from 0 to 1e5 or sqrt(6*n) and calculate the required increase of the second number.

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

    I think this time problem B was one of the hardest problem B's I have ever not solved...

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

Ironically, though there were few solves, the tests for B seem to be pretty weak — my submission 7762305 was accepted despite failing on many many tests (any of the lines in http://pastebin.com/rP0u5f4t would result in WA) due to having > rather than >=.

The actual problem was pretty nice itself though — proving that the solution will run in time is not too simple or obvious.

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

Seems like there was some miscalculation of the problems' complexities :D

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

    Thanks for this. I should not be happy for solving the C question for the first time. :(

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

Hard but nice problems!

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

Rank: 235 , best performance so far. :)

Biggest mistake that I made was locking all solutions when I did not have any intention of spending much time on hacking.

Solution B got hacked. Could not resubmit. :(

Probably will remain EXPERT for some time.

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

    Congrats, I too had my best performance so far today! Solved E for first time! :)

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

can anyone tell me why this solution gives WA while it works for that case on my pc http://codeforces.net/contest/466/submission/7772471

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

    Not sure if that's the cause but a thing I notice is you do not return 0 in the end of the function, so I suppose the returned value is undefined, therefore it may return true at some moment?

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

      i donot get it can u plz explain more how can it return true?

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

        Well you don't return 0 if the function doesn't find an answer? You know, a function must always return a value. Since you don't tell it to return 0 (false) it may return whatever it likes in theory :D

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

          yes right but in that case i donot call the function

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

            but that was the bug weired

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

              That bug was the difference between me and div 1

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

            You do call it. 6*11=66, while 7*7=49, so n>a*b, therefore you do call the function.

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

Finally worse did it.

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

Congrats to worse for becoming the first ever white coder on codeforces !

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

Even though ratings have been updated, colors have not. I am a specialist with rating 1553. :P

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

What happened to my account rating ? http://screencast.com/t/pdEJQN5CZu

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

I solved nothing but A this contest.

I've actually solved E(for the first time in my life) but made a simple mistake. In one of the lines, I used the variable which I use to count the number of tasks received till now instead of the variable that holds the number of task that is in question... Passed pretests but got WA in system tests :( I suspected that I'd get TLE in system tests but when I corrected that line I got AC...

Anyways... Let's look at the bright side.. I've solved my first E even though it's not official.

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

This is first time I solved problem E! :D And became candidate master! :D :D

At first I got many WA 3 times on problem 1, I thought that for sure I will become Specialist again (got Expert only in previous contest).

After A passed pretests, I tried C and again got WA 2 times... tried E and got TLE. Finally I tried different method and E worked, then turned out I had to use long long int in C and that passed pretests as well.

Edit: I previously asked about other solutions to E, but I found a very simple one now.

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

I am unable to guess why my code gives WA plz can someone help me find the bug .Here's my submission http://codeforces.net/contest/466/submission/7774444

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

So, apparently E had weak testdata. Or else, How did this solution pass? http://codeforces.net/contest/466/submission/7765318 I can break this solution with very easy testcase.

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

    there are many question like this with weak tests... anyway after this time if i cant solve a problem efficent i will send a naive solution :|

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

    Can you give one?

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

      I think an input of the following type would work:

      50001 100000
1 2 1
1 3 2
1 4 3
1 5 4
...
1 50001 50000
2 50001
3 1 1
2 50001
3 1 2
2 50001
3 1 3
...
2 50001
3 1 25000

      Basically, the idea is that we have a chain of bosses 50,000 employees long, with 500001=>50000=>...=>1, so 1 is the boss of everyone. Then, we have 25,000 documents. Each document we give to employee 50,001 and we ask if it reached employee 1. It seems like you're doing a linear search for each document. So your running time will be on the order of 50,000*25,000 = 1.25 billion operations.

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

        Ah, you are correct. For some reason I assumed maximum height of tree as log(N + M).

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

I jumped to exactly 1700 in this contest. Now it appears that I am in some sort of bizarre limbo...

[UPD: Fixed now, as add1ctus said.]

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

    You are a candidate master, but it seems that worse broke the rating system by getting negative rating (thus not fitting into the 0 — 1199 gray rank, but in a new color — white). Hopefully once it gets fixed you will be promoted to candidate master.

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

It seems, there is a bug in standings table: purple participant is impossible for Div.2.

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

    There is a bug with the rating/rank system. He had 1472 rating before Round #266 and got promoted to purple after the competition. Check his profile.

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

What happened to phantom11's country-wise standings?

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

I couldnt understand the concept to B. Anyone?

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

    If a >= sqrt(6n) and b >= sqrt(6n), then a*b >= 6n; in this case, do nothing. Let a be the smaller of the two input numbers, and b be the larger of the two.

    One trivial solution is to increase b until the room is big enough. E.g. if a = 10, b = 11, 6n = 1001 (somehow): then the trivial solution is 10*101 = 1010. Then your "overflow" is at most a, which as we said was <= sqrt(6n). Let TRIVIAL be the value of this trivial solution, i.e. in this case, 1010.

    Therefore, the optimal solution has "overflow" at most a. Suppose that the optimal solution is x*y, with x <= y (WLOG). Then x <= sqrt(6n) + 1, because otherwise, x*y > (sqrt(6n)+1)*(sqrt(6n)+1) >= 6n + 2sqrt(6n) > 6n + a >= TRIVIAL, therefore the solution was non-optimal.

    What we have shown is: you are guaranteed that an optimal solution exists with at least the smaller number being less than sqrt(6n). It is possible that one of the two is larger, though, e.g. 1*6n = 6n. However, your goal is only to find the smaller number, through the following method.

    Fix w between 1 and sqrt(6n). For every w, let h be the smallest integer s.t. w*h >= 6n, i.e. h = ceil(6n/w). Keep track of the best value you've found so far. Then, you iterate through sqrt(6n) < 10^5 possible values of w, and for every such w, your computation is constant time, so your algorithm is linear in sqrt(6n).

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

Here is my code : http://codeforces.net/contest/466/submission/7796449 In my computer and ideone.com http://ideone.com/6lt8wR it runned test 1 and give me 4 but on codeforces it give me 0 ??? Who can explain me ??

→ Reply