RomaWhite's blog

Codeforces Round #210
By RomaWhite, 11 years ago, translation, In English

Hello!

Codeforces Round #210 will take place on November 10 at 21.00 MSK and I am the author of the problems.

This is my first round on Codeforces and I hope everything will be well. I would like to thank Gerald Agapov(Gerald) and Vitalii Aksenov(Aksenov239) for helping me to prepare the round.

Good luck!

UPD.

Score distribution in first division: 500-1000-1500-1500-2000.

Score distribution in second division: 500-1000-1500-2000-2500.

UPD.

Congratulations to the winners!

First division:

  1. Egor

  2. PavelKunyavskiy

  3. scott_wu

  4. Dmitry_Egorov

  5. mmaxio

  6. enot110

  7. sevenkplus

Second division:

  1. _ZigZig_

  2. budalnik

  3. Ilya_Yakovlev

  4. Neodym

UPD.

Editorial

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

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

Comments with a lot of positive votes requires a creativity that I don't have. :) So I just wish good luck for you with your first contest! :)

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

Glad to see a very full list of contests after a long time!!
4 contests in 9 days! That's the best thing everyone wants!

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

New author — new type of problems!

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

why so many only div2 contests?? Being in div1 seems to be a negative thing nowadays.

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

    You can still participate in Div 2 contests, they just won't affect your rating. It's still good practice though.

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

      u are 100% right that Div-2 contests are good practice, but the thrill that comes with doing a rated contest will not be there, which IMO is the most important thing during the round.

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

Wow, two continuous Div-2 rounds !!! Hip-Hip Hurrey :D best of Luck :)

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

after more than a week, finally a contest! not just one, but this is the first of 4 rounds in 9 days! :)

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

Wow! +180, 30 minutes before the contest! That's awesome!

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

MikeMirzayanov happy birthday to your daughter Tatyana. Hope see had a wonderful day today :)

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

    funny to see lots of people misunderstood that sentence. :D

    "Oh, St. Dijkstra, Tatyana is 2 years old!" ... ;-)

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

    Why almost all of you think that her name is St. Dijkstra?? Dijkstra is a famous researcher in computer science, and his name was mentioned in the sense that he is a 'saint' in our programming world. How couldn't you understand such a simple thing?

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

      Ambiguous sentences invite ambiguous interpretations. In many parts of the world, it makes perfect sense to name one's child in honor of some intellectual hero like Dijkstra. Also, check out this guy named Aristotle Socrates.

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

Offtopic — I wonder what is (p1) at the bottom of the pages of Codeforces... :S

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

This contest is too late for Chinese coder...

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

problem d was dp right?

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

    does the votes mean that problm d from Div 2 was dp?!! cant some one just reply? is it that hard?!!

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

      Can anyone explain the solution ?

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

Why the standings are frozen during system test?

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

    That's because during the contest the solutions are tested using only the pretests (which are simpler than the final tests). At the end of the contest, the results are frozen and all the solutions are reevaluated using the final tests.

    It means that you can get accepted during the contest and at the end, if your submission fails on one of the final tests, your points for that problem are taken back.

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

How to solve Div1 E? The idea is Dijkstra in a layered graph with (k+1)*n nodes?

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

how to optimize dp in problem C?

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

In C(div2) example 1 input : 4 5

1 2 3 1

2 1 2 8

2 3 4 7

1 1 3 3

2 3 4 8

output: 4 7 4 7

why is a[1] equal to 4? when we know : line 2, a[1] is max 8 line 4, added 3 to a[1] so answer is a[1] = 8 cos we don't know any other change..

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

    That example had multiple solutions, including yours. Even if a[1] = 4, a[2] will meet the max requirements.

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

    both are correct, you have to output atleast one correct array.

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

    in that case, a[1] can be any number, less or equal than 7

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

    "4 7 4 7" is one of answers ! ( take care about multi answers ) ...

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

    Thanks, I had misunderstanding of a task.

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

What are the strings for the first and the second example of Div1 C?

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

    in first example zT where T >= 'a' && T <= 'z'.

    in the second example zy and zz

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

      zz has beauty 0, since there is no i,j such that s[i..j] is strictly larger than t[i..j], because y<z.

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

        Please check the change in the problem statement. It is written in bold.

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

          Well, when this change in the statement has been done? I had no idea about this change until just NOW!

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

How to prove gcd(i, i+1) =1?

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

    There are 2 cases : 1)if i is even, the i + 1 is odd, 2) if i is odd , then i + 1 is even gcd(even,odd) = 1

    incorrect,sorry)

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

    пусть i делится на какое-то простое p, тогда i+1 имеет остаток 1 по модулю p, и так для всех простых для обоих чисел => взаимно просты

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

    because of 1*(i+1) — 1*i = 1

    Note: a and b are co-prime if there exists x and y such as a*x+b*y = 1

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

    According to property of GCD: gcd(a+mb,b)=gcd(a,b)

    Let a=1, b=i, m=1, you can get: gcd(1+i,i)=gcd(1,i)=1

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

    Each second number is divisible by 2 Each third number is divisible by 3 ...

    So the two consecutive numbers can not be the same divisor Sorry for my english

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

I don't understand test cases in problem C. With input:

2 2 yz

We need strings t with beauty 2. These are ya,yb,...,yy (25 in total) plus az,bz,...,xz (24 in total). Thus, the answer should be 49 but the expected answer is 26. ???

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

    in first example zT where T >= 'a' && T <= 'z'.

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

    notice that only za...zz has beauty 2 lexicographical larger: the first compared char must be strictly larger than the other.

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

    t is larger than s. See the change in the problem statement in bold.

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

      Well, when this change in the statement has been done? I had no idea about this change until just NOW!

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

Can anyone give me a hint about how to approach problem C in Div2 please?

I would like to attempt to upsolve it, but, I'm totally out of ideas...

Best,

Bruno

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

Ahhh, Loved it !! #Needed some out-of-box thinking, throughout. #looking Forward.

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

really fast system testing..:)

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

Really interesting problems. I expect more contests from you RomaWhite :)

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

Never Do this mistake! Never do! NeveR! [A div 1, segment tree instead of FORs]

P.S: i'm so Idiot!

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

Can someone tell me how they solved Div2, A?

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

How to solve problem DIV2 D / DIV1 B ??

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

    Plz anyone explain the process how can i solve it with binary search and the logic behind it.

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

      Imagine we have a function f (returning true/false) that tells us whether it's possible to reach some c by changing at most k numbers (that means that after this change, the difference between every two consecutive elements is less than or equal to c). Obviously, when f is true for some c, it's also true for every c2>=c. That means, that we can use binary search to find the "cut-off", the first c for which f is true (which is what we are asked for).

      So the last remaining step is to program such function f. We can use dynamic programming — denote dp[i] as the minimal number of changes in elements 0..i so that the difference of every two consecutive elements in range 0..i is at most c AND the last element remains unchanged.

      We can calculate dp[i] as a minimum of i (that means we change every value before the currently considered element to the same value) and dp[j]+(i-j-1) for each j smaller than i with the condition that abs(a[j]-a[i]) <= c*(i-j) — that corresponds to remaining the j-th element unchanged and changing every single element in between of i, j.

      Then we can determine the minimal number of elements that we need to change as min(dp[i]+(n-i-1)) for each i (we take i-th element as the last that remains unchanged, so we need to change the rest).

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

Please, could anyone write a brief editorial of the contest, I could only solve problem A div1, I am trying to upsolve the other problems and I think many other coders too. thanks in advance.

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

With a little bit of delay — screencast

→ Reply