Блог пользователя Nickolas

Автор Nickolas, 6 лет назад, По-русски

27 декабря 2017 года в 19:35 MSK состоится очередной раунд Codeforces #455 для участников из второго дивизиона. Традиционно, участники из первого дивизиона приглашаются поучаствовать в соревновании вне конкурса.

Раунд будет рейтинговым.

Этот раунд проводится по задачам летнего соревнования для интернов algO(1). Если вы видели задачи этого соревнования, пожалуйста, не принимайте участия в раунде. Задачи готовили Максим Калинин (slycelote), Александр Миланин (Milanin), Ибрагим Исмаилов (ibra) и я (Nickolas).

Участникам будет предложено шесть задач и два часа на их решение. Разбалловка 500-1000-1500-1750-2000-2500.

Мы надеемся, что задачи вам понравятся. Удачи!

UPD: спасибо HellKitsune, vintage_Vlad_Makeev, 300iq, Arpa и Livace за тестирование задач!

UPD: Контест окончен. Разбор задач можно найти здесь.

Поздравляем победителей!

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
  • Проголосовать: нравится
  • +334
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

is it the boxing day of problem solving ?

»
6 лет назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Why always scoring distribution is announced later ?

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

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.

»
6 лет назад, # |
  Проголосовать: нравится -47 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +56 Проголосовать: не нравится

    Don't be sexist in 2018?

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +39 Проголосовать: не нравится

      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.

»
6 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +38 Проголосовать: не нравится
»
6 лет назад, # |
  Проголосовать: нравится +40 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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

thinking if I could solve 5 problems for the first time

»
6 лет назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

Why don't you thank Mike?

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится -20 Проголосовать: не нравится

It will be fun :)

»
6 лет назад, # |
  Проголосовать: нравится +61 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

 Oh yeah...

»
6 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится +13 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится -33 Проголосовать: не нравится

Why does the tourist not attend?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
  • 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?
»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Не благодарили MikeMirzayanov, значит к неудаче.

»
6 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Когда уже можно будет поменять хэндл?

»
6 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Эщкере

»
6 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

Can we enter the cobtest as a team ?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    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.

»
6 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Can we hope for short problem statements?

»
6 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

there is something missing...

»
6 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

My New Year Resolution : I WILL WRITE CLEAN CODES

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
6 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

slightly long queue right now!

»
6 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Я, к сожалению, не пишу раунд, но задачи классные! Это реально то, чего не хватало раундам за последнее время!

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Think of "layer" as in Photoshop.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      Am I silly :(

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What was pretest 3 on problem C?

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve D?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I think simulating with std set is fine.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How so? Thought it would TLE

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you please explain the solution?

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

    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.

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

What was the hack for problem A?

»
6 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

how to solve C?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      can you please explain a bit more?

      • »
        »
        »
        »
        6 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

        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.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    NO.

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

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    @rajat1603 that is the precise definition of overkill.

»
6 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

How to solve F?

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Ideas for C?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I solved it using dp

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      how did you use dp?

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      please give the recursion formula.

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

      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]

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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)

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Used dp with cumulative sum to avoid TLE

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Is the solution for B this:

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

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

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
»
6 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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...

»
6 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Is C solvable using top-down dp ?

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Div2C

What makes this solution fail?!

33689625

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 .

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Isn't system testing too slow?

»
6 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Good fight between problem D and E today

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

B had 102 test cases!!

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Если бы я давал мастер-классы, я назвал бы их "как ничего особо не решить и вернуться в первый дивизион" :(

»
6 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

It's a fantastic round :)

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

shit contest made me gren

»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

D and E were easier than C lol

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve division 2 C problem?