HolkinPV's blog

Codeforces Round #171 (Div. 2)
By HolkinPV, 12 years ago, translation, In English

Hello, friends)

Soon is coming regular Codeforces round #171 for Div.2 participants. Traditionally Div.1 participants can take part out of the competition.

Again and again the problems were prepared by the familiar group of authors: Pavel Kholkin (HolkinPV), Igor Kudryashov (Igor_Kudryashov), Nikolay Kuznetsov (NALP) and Gerald Agapov (Gerald). Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for Codeforces and Polygon systems and Mary Belova (Delinur) for translating the problems.

UPD: score distribution will be not standard a little bit: 500, 1000, 1500, 2000, 2000.

We wish everyone good luck, successful hacks, high rating and good mood)

UPD2: the contest is over, we hope you enjoy it)

Congratulations to winners:

1) study_english
2) ipip2005
3) rng_50216
4) bfrcns197
5) csavky103

UPD3: the editorial will be published soon

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

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

I love Russian thinking in preparing contest problems ,Hope short statements & easy English words . GL & HF

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

Starting to prepare includes...

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

    Instead of preparing them before every contest, I advise you to set all things in your default source of whatever compiler you might be using, so that when you create a new file( program ) you will have already the predefined code. It will spare you a lot of time.

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

Hi everyone, I has just viewed dj3500's screencast: CodeForces #169 div2. I saw the "hightail" program and go to https://github.com/dj3500/hightail but I don't know how to install it. Can someone help me?

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

Again and again only div2 contest :( .

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

    I think that they want to increase the number of Div1 users, because Div1 contests make many users become div2 users.

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

Hope me can change the rating color to purple!!Keep Calm and type the code more quickly! the same to everbody! but, it seems that i got fever:(, It's feel terrible Now:(

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

Hey guys, no hope for a late reg? Please! I was just 3 mins late

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

    well i was just a few seconds late, but i guess the show must go on

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

it sounds like 50216 is a popular number. (rng_50216)

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

I was really surprised to see that E was identical with D from a past Div.1 round (132D - Constants in the language of Shakespeare). I just copy & pasted, commented out a single line, and got pretest passed...

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

    Can someone please give me a more simple example than test 10 of why my greedy approach is failing? http://codeforces.net/contest/279/submission/3248428

    I keep 2 counters, number of zeros and number of ones. I look at all groups of consecutive 0's and consecutive 1's. If such a group has size 1 , i increment the corrsponding counter, else, I increase by 2 the corresponding counter. In the end, the result should be min(number 1's , number 0's + 2), representing that either we erase all ones or try to convert all 0's into 1's and do 2 more operations at the end.

    Thanks !

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

      well i guess here is your problems

      for 1counter:

      if you have two blocks of 1 with more than 2 numbers seperated by only a number 0 (11011) you will only need to change the 2nd group into (11100) in 1 steps, so you get another block of number 1. to convert it you need 2 steps. so 3 in total.

      however, based on your solution, cause you have 2 blocks of '1' size 2, you need 4 steps.

      testing pretest 3, you luckily right because the number of '0'. but when they increase 1counter and 0couter by adding '100', your 1counter is far bigger than 0counter, so the ans must be based on 1counter.

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

E was easier than A, what a terrible contest !!! .... :o

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

    Is there any easier way to solve it rather than simulate the spiral per coordinate ? (Problem A)

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

      You can 'push' the given coordinates to the corner. Then handle the corner cases. Then it's just O(1) math stuff per query

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

        I suppose 'easier' meant faster. So calculating all the formulas was time-consuming, while writing simple emulation took 6 minutes only. (:

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

    So we learned the knowledge, and to grow in experience.

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

I wish every rating updates were as fast as the sysTests :)

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

Am i the only one who thinks that final testing on the last few contests run much quickly than earlier ?

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

Am I the only one who couldn't hack? I couldn't even see source codes.

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

    With Chrome I couldn't see either. Had to use IE for hacking.

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

Could someone help me find out why my code for problem C is failing? Here is my code . It got WA in test 21.

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

    It must be a strongly tricky case, lots of submissions got WA in this particular case.

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

    that's a case like,

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

    Try this

    7 3
4 2 2 2 2 2 10
2 7
2 6
5 7

    It must be three "Yes". And i have the same mistake like you have ->My Submission Even the the same line .. ^^

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

      Oh, now I can see what was wrong. Thanx.

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

      thanks bro...i can now see where i failed system testing hopefully now i can use this lesson to do better algorithms in future...

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

        NP guys.I just want to be a nice person in CF but look my contribution ...

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

      Really helpful.... Thanks

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

I think one of the reason behind low solve of Problem D is Poor Description.. I have read it more than 5 times, still i haven't understood what is the problem !!

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

what's the relationship between rng_58 and rng_50216?

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

Lots of solutions for D gave incorrect answer for the following test case:

2 1 1

Edit: My test is wrong. The numbers are distinct

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

I can't see what 's wrong with my solution to problem C Can anyone help me with that? submission : 3245705

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

    Check test: 3 1 2 1 1 1 3

    Strange that it passes all the previous tests.

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

      Very thanks. I found the bug; if we get another array for the size of good sequence which ends with "i", it would be ok!

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

    Input: 6 1 2 1 1 1 1 1 1 6

    My solution prints "Yes" and it seems to be ok, but your solution prints "No".

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

Can anyone explain Problem B (279B — Books)? This is how I understood the problem:

We are given an array A and an integer t. We have to search for a "sub-array" of A whose sum of elements is at most t. The answer should be the maximum length of such a sub-array.

However, I must have misinterpreted the problem. I have looked at some submitted solutions and they involve forming the sum of the first j elements of the array A and then substracting the elements A[k], A[k+1]... A[L]. Somehow two "pointers" j and k are involved which I do not understand.

I'd be grateful if someone could explain this. Thanks.

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

    You interpreted the task properly (if by subarray you mean a substring). You can calculate the solution in a single pass through the array, such that when you are at the j-th position, you also store the minimum i such that [i..j] is the maximum substring that ends in j. What you do is add the j-th value to the current sum, and while the sum is larger than t, subtract the i-th value and shift i one space forward. After each step is done, check whether the current interval size is larger than the maximum recorded so far and you're done.

    Here's my code for that: 3240473

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

      Your explanation is excellent! I first tried to solve it by searching for subarrays (substrings) [i..j] with maximal length and sum<=t by using two loops and got a timelimit exceeded, I guess since it results in O(n^2) runtime.

      Your algorithm is a clever idea with only O(n) runtime. Thank you PetarV!

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

        You also could have done it in O(n*log n) by keeping d[i]=sum{a[1..i]} and for each j=1..n binary search for the largest k>=j such that d[k] <= d[j-1] + t.

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

      I don't get it, why does it works?

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

how can we solve problem D ? I gave a solution with complexity O((n^2)*(2^n)) but definitely it gets TL.

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

    at first my solution was O((n^2)*(2^n)) and than I used that every number is distinct for precompution and got O((n^2)*n) . so think about it...

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

      You mean you got o(n^3) solution ?

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

It's been quite a while since the contest ended. When will the editorial be published?

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

The editorial is late... can some1 please explain E.. I saw many codes.. but i dont understand how they arrived at that solution...

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

    +1 I used the greedy method to solve this problem,but i don't know how to use DP to solve. can some1 explain?

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

It's been quite a while since the contest ended. When will the editorial be published?

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

Please publish the tutorial quickly

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

please publish the editorial as you said.

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

    Comon guys, some of us are still very curious to see how dynamic programming applies to D and E.

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

      This is how I solved the problem, hopefully the reasoning is right For E using dp, Let a single move = addition of 2^k or 2^-k s = the binary string, s[0] being the first digit = the last character in the string

      Let dp[POS][i] = minimum number of moves needed to get a string l such that l[0..i] exactly match s[0..i] and l[i+1 ..] = 0 Let dp[NEG][i] = (same as above) l such that l[0..i] exactly match s[0..i] and l[i+1 ..] = 1

      If s[i] == 0, then dp[POS][i] = dp[POS][i-1], since you don't have to make any additional move. For dp[NEG][i], we can either make our move from a [POS][i-1] state, where we have to turn all bits from l[i+1....] to 1, but leave l[i] =0, so this takes 1+dp[POS][i-1] (just a single move, note that a negative power of 2 turns all bits to the left to 1, but leave the right bits unchanged -> -2^k = 11111... 000..). Or, we can make our move from a [NEG][i-1], which means we have to turn the ith bit to 0. This we can do by adding a single positive power of 2, which means only 1 extra move. Thus. dp[NEG][i-1] = 1+ Min(dp[POS][i-1], dp[NEG][i-1])

      And for s[i]==1 case, similar reasoning. Base case -> dp[POS][0] = 0 if first bit is 0, 1 if first bit is 1, dp[NEG][0] = 1, because you still have to make the bits to your left =11111...

      EDIT: whoops, something is wrong with my reasoning.. Hold on... EDIT EDIT: k nvm, I was confused about something else. Hopefully someone can agree/point out mistakes?

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

When will the editorials of this round come out? The editorials of the next 5 rounds are already published. @admin: please prepare it as soon as possible.

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

Very good

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

tutorial please ?! really need it !

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

Editorial -> when? please. Thnakyou.

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

Can someone tell me the logic behind this problem? 279C - Ladder
I've tried reading other people solutions but I dont understand properly.

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

    Vicennial Did you find it out? If possible, could you explain the solution idea?

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

      As explained in the editorial , for each index you should find

      i) lowest index i where decrement occurs (most people implemented it as array moving right to left and noting index where a[i] > a[i+1])

      ii) largest index j(before that index) where increase occurs , (implemented as array from left to right noting most recent index where a[i] > a[i-1] )

      now for subarray [x,y] ,if most recent decrement for index x is 'i' and most recent increment for index y is 'j' then, if( i <= j ) then segment is a ladder 35071213

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

        Can you explain the logic please? :)

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

          now for subarray [x,y] ,if most recent decrement for index x is 'i' and most recent increment for index y is 'j' then, if( i <= j ) then segment is a ladder.

          Explanation : think of it this way — if the segment is a ladder first all the increments should occur then all the decrements. eg 1 2 3 4 2 1

          Now for 'x' we look at the closest index on its right where decrement occurs . (say A) , Also for 'y' we look closest index to left where increment occurs say(say 'B') . Now A < B will only happen when the segment is a ladder . Try out some cases to verify this

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

Why am I getting WA in 19th test case for problem C ? Is there some extreme tricky case ? Here is my submission — Submission

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

    Consider the case, 4 1 2 1 1 2 1 4

    I also made the same mistake :P

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

You should have posted the editorial as the questions were good. Hope you do it atleast now. @HolkinPV

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

Could anyone explain why my code is wrong. Means could anyone give a possible test case/explanation of why my code is wrong. Link of submission attached-> (https://codeforces.net/contest/279/submission/101634918)

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

    I think this case 1 2 1 1 2 1 might fail your solution. For this case, array brr will always have zero values since if the query is L = 2 and R = 5, the answer should be No while your solution might output Yes

    → Reply