Nickolas's blog

Codeforces Round #455 (Div. 2)
By Nickolas, 7 years ago, translation, In English

Codeforces Round #455 for Div 2 competitors will be held on December 27 at 19:35 MSK. As usual, Div 1 competitors can join out of competition.

The round will be rated.

This round is based on tasks for summer contest for interns algO(1). If you have seen the problems from that contest before, please don't participate in the round. The problems were prepared by Maxim Kalinin (slycelote), Alexander Milanin (Milanin), Ibragim Ismailov (ibra) and me (Nickolas).

The competitors will be given six problems and two hours to solve them. The scoring distribution will be 500-1000-1500-1750-2000-2500.

We hope you'll like the problems. Good luck!

UPD: thanks to HellKitsune, vintage_Vlad_Makeev, 300iq, Arpa and Livace for testing the problems!

UPD: The contest is over. Editorial can be found here.

Congratulations to winners!

Div. 2:

  1. MegaOwIer
  2. skuecrk
  3. Vergara
  4. Luqman
  5. UoA_Kaori

Div. 1:

  1. Benq
  2. dotorya
  3. uwi
  4. I_love_Tanya_Romanova
  5. ksun48
  • Vote: I like it
  • +334
  • Vote: I do not like it

Comments Comments (133)
| Write comment?
»
7 years ago, # |
  Vote: I like it +17 Vote: I do not like it

May I know how many people participated in summer contest for interns algO(1)?

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

3 consecutive contests? I think this is a perfect end of year.

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

is it the boxing day of problem solving ?

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

"summer contest for interns algO(1).....". It seems to me some problems will be solvable in O(1).

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

Why always scoring distribution is announced later ?

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

She sets only contests like April Fools Contest 2017, Surprise Language Round #7 etc,

Seeing this one is already based on previous contest,

Get ready for Boxing Day.

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

a girl announces the round, hope it's a nice contest :D

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

    Don't be sexist in 2018?

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

      I don't see how this is sexist. He said he hoped it would be a nice contest. The fact that he mentioned a girl announcing a round might as well just be because he is surprised because of the low ratio of females in competitive programming.

      What if I said "a guy announces the round, hope it's a nice contest :D?"

      How many comments of yours would I see? (Hint: Zero)

      I don't see how people can get along if every little thing is scrutinized as some type subversive sexism, when it really isn't.

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

        If a guy had announced no one would have commented that in the first place.

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

Glad to see the scoring distribution one day before contest...:)

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

I_LOVE_EVERY_GIRL Nickolas

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

Three contests at the end of the year. A great gift by Codeforces! :)

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

The scoring distribution will be 500-1000-1500-1750-2000-2500.

thinking if I could solve 5 problems for the first time

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

Why don't you thank Mike?

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

It will be fun :)

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

Mike say "Two consecutive contests without thanking me, and this one even not say 'hi codeforces'."

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

Again no one thanked to mike. ..it means :( Your text to link here...

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

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

Thanks Mike Mirzayanov for the platform and for awesome contests!!!

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

Dreaming of purple after these 3 contests!! Good luck everyone!

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

Why does the tourist not attend?

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

    Because he is busy traveling and contests for div 2 nine for div 1.

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

    Did you assume he was not attending? He might even be attending on a fake account, kinda like how you are posting on a fake account.

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

    because it's a div.2 contest...

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
  • So the problems are known to many people?
  • *I don't know the "summer contest for interns algO(1)"
  • Is it very popular??
  • Or just few people can participate in it?
→ Reply
»
7 years ago, # |
  Vote: I like it +13 Vote: I do not like it

The contest is hidden because no one thanked Mike, click here to view it.

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

It will be a good match because all of its designers are for Microsoft.

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

Can we enter the cobtest as a team ?

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

    As you can see, there is no such button on

    the registration page.

    But after the end of the round, as usual, you will be able to start virtual participation as a team.

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

Can we hope for short problem statements?

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

there is something missing...

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

So happy adamant is finally not in the list of problemsetters! Just kidding though, the last two contests were pretty cool.

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

My New Year Resolution : I WILL WRITE CLEAN CODES

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

I forgot to register. Can someone register me for this contest (out of competition)?

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

    The quote about extra registration:

    If you are late to register in 5 minutes before the start, you can register later during the extra registration. Extra registration opens 10 minutes after the contest starts and lasts 20 minutes.

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

      Thanks Mike. It has been 10 mins, but dont see the extra registration icon.

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

slightly long queue right now!

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

Didn't like contest, statements were very hard to understand.

By the way, how to understand statement of B? I just wrote magical formula with samples and it got AC :P

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

    Think of "layer" as in Photoshop.

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

      Still don't get it. Looking picture for explanation, but it just don't give a sh*t.

      Am I silly :(

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

        Alternatively, you can think of "layer" as "set". A set of segments must contain pairwise disjoint segments. Find the minimum number of sets that contain all the segments.

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

          Emm, I understood now. Thanks!

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

What was pretest 3 on problem C?

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

    6 f s f s f s ANS : 5

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

    Integer overflow I think

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

    I think it is something like this

    7
f
f
f
f
f
s
s

    Answer: 6

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

      how is the answer 6. i think it should be 2

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

        Indentation of the first 6 statements (5 loops and first simple statement) is defined uniquely. The 7th statement can have any indent from 0 to 5 (be part of any loop's body or just follow the first loop).

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

How to solve D?

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

    I think simulating with std set is fine.

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

      I was thinkin about it but 10^6 constraint drove such thoughts away from me.

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

        Well, time limit is 2s and it should pass if implemented correctly.

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

        you can use vector

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

      How so? Thought it would TLE

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

      Can you please explain the solution?

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

      You can think of like maintaining two sets. One 'to_be_deleted' and other is 'candidate_for_deletion' (whose adjacent is to be deleted from first set). Now each item can be deleted from first set at most once and each item can be inserted into second set at most once. So, maintaining amortized complexity O(nlogn). Log(n) part for set insertion or find.

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

    Simulate with std::list merging adjacent blocks, if of same color.

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

    You can solve it in complexity O(n).

    Group consecutive same elements and make one array of integers. Than all elements in new array will decrease in one operation by two except first one and last ( they will decrease for one). You can go over all groups and see minimum amount of operation to make one element of array lower than 0. Decrease all elements for that amount of operations ( first and last will decrease for that value and other will become smaller for 2 x amount of operations ). After this move remove all groups smaller than 1 and merge some groups if they have same letters.

    At first view this looks as brute force, but actually this is O(n). In each iteration you will decrease each viewed element at least for one and total sum of that array will be exaxtly n.

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

What was the hack for problem A?

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

    maybe ab bb types where answer should be ab and not abb.. so you have to check s1[i]<s2[0] and not less than equal to

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

      Oh so that means that in my room, everyone was sharp and clever enough to avoid this mistake. :(

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

how to solve C?

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

    dp[i][j] -> examining the ith prefix how many ways we can ident so that the ith statement is idented j times.

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

      can you please explain a bit more?

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

        Denote the ith statement with ai, we wish to calculate dp[i][j]. Then there are two cases. If ai - 1 = f then we just started an identation so dp[i][j] = dp[i - 1][j - 1]. Else (so we can delete some identations from the previous statement). To reduce time complexity we have to use suffix sums and use iterative dp to fit in memory.

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

          thanks a lot :)

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

          Or one can implement with recursive approach (who finds it easier) and pre call dp function in proper direction to avoid stack growth.

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

how to solve D? greedy strategy or some smart simulation?!

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

Is using Dilworths theorem and then finding max antichain using DP overkill for B?

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

    NO.

    Another alternative: If you can't understand statement like me, just search samples in OEIS and try every pattern. Works after some WA.

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

    Probably :) The series which I got(pretests passed) were, if n is even, the series is 1+2+3...n/2 + n/2 +...1 and if n is odd, 2*(1+2+3...n//2)+n//2+1

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

    @rajat1603 that is the precise definition of overkill.

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

When will the editorials be published? And how to solve C? Seemed like something to do with catalan numbers.

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

How to solve F?

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

Ideas for C?

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

    I solved it using dp

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

      how did you use dp?

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

      please give the recursion formula.

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

      My English isn't very good but i'll try

      let dp[i][j] be number of ways if you use first i commands and end up at nesting level j

      if a[i] == f

      then just dp[i + 1][j + 1] += dp[i][j]

      else

      from dp[i][j] we can get to any state of dp[i + 1][0..j]

      you can calculate this if you use auxiliary array of prefix sums

      ans will be dp[n][0]

      and if you are currently at i == n — 1 you just do dp[i + 1][0] += dp[i][j]

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

    dp(i, j) = number of ways to indent the first i lines such that the last line has indentation j.

    Runs in O(n^2)

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

    it seems like dp, but i didn't implemented due to time..

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

    Used dp with cumulative sum to avoid TLE

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

Is the solution for B this:

floor(((n+1) * (n+1)) / 4)

It passed the pretests but I don't know about systests.

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

I had idea for C. First every consecutive f and one s we call a block, for example fffs. So you find number of blocks and also size of every block, where size is number of f. Then dp[ i ] [ j ] = dp [ i + 1 ] [ j ] + dp[ i + 1 ] [ j + 1] + ... + dp[ i + 1 ] [ j + block_i_size ]. Anyone solved this way? If u didnt, u probably wont understand me :P

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

Div 2B Solution :P

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

Is it just me or is E easier than B, C and D?

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

    i didin't know about C and D, but i'm sure that B is easier than E.

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

    Don't know about B but it's definitely easier than C and D

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

    Don't know about E but B is harder than F.

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

    A<E<D<C<B<=worthy div1.A<F IMHO :D

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

    don't know anything but everything was hard :P

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

Does anybody know some counter tests for my solution at C. I saw many people got WA at pretest 3. Why? My solution.Your text to link here...

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

Recursive solution for problem B

At first think of all the segments that have left point at 0. There are total N segments that have this property. We can match every one of this segment [0, x] with a segment [x, N] and draw it in one layer. Thus, we need total N layers to draw all segments that start with 0 or ends with N. All of the remaining segments are defined by the points between 1 and N-1.

So, we can write, f(N) = N + f(N-2) where, f(0) = 0, f(1) = 1

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

Is C solvable using top-down dp ?

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

Div2C

What makes this solution fail?!

33689625

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

    Try this testcase:

    5

    f

    f

    f

    s

    s

    Its answer should be = 4

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

Did anyone solve D by another method : making a right arrays which stores the logical next element and making a left array which stores the logical previous element in array and then performing logical deletion by changing the left and right array values. Eg. _ a a b b_ _ left[i] {-1 , 0 , 1 , 2} ........._ _ right[i]{ 1, 2, 3, 4}_ .................... after one operation , left[i] becomes {-1,X,X,0} and right[i] becomes {3,X,X,4} and so on (by proper implementation procedure taking case of indices etc) and then count total number of steps(again proper implementation required). If anyone solved like this , please provide your code .

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

Isn't system testing too slow?

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

Good fight between problem D and E today

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

B had 102 test cases!!

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

It's a fantastic round :)

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

Will the user ratings change according to this contest? If yes, when?

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

shit contest made me gren

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

D and E were easier than C lol

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

    E was easier than C and D, but D was harder than C, idea is very tedious in my opinion

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

      D is pretty strightforward solution from early lessons of data structures (linked list, nostalgia). But in C you need to think a bit.

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

it was really a great round with really great problems and a fast editorial thank you for your efforts

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

Always have some submit Fail System Test make me a little bit annoyed,whatever that's the charm of codeforces i think :)

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

how to solve division 2 C problem?

→ Reply