When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

vovuh's blog

By vovuh, history, 5 years ago, translation, In English

Miss Div. 3 rounds? :)

<copy-pasted-part>

Hello!

Codeforces Round 540 (Div. 3) will start at Feb/19/2019 17:35 (Moscow time). You will be offered 6 or 7 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. Probably, participants from the first division will not be at all interested by this problems. And for 1600-1899 the problems will be too easy. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

  • take part in at least two rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</copy-pasted-part>

UPD0: I also would like to thank zimpha and Arpa for help with the round testing and finding some bugs!

UPD: Due to the problems being really interesting the round will last 2 hours 15 minutes.

UPD2:

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Ghajini 7 259
2 ACtest 7 271
3 chrome 7 274
4 AuSquare 7 341
5 bonchinche 7 343

Congratulations to the best hackers:

Rank Competitor Hack Count
1 limstash 73:-9
2 MarcosK 59:-6
3 TheRoot 28:-1
4 yqdjl6 23:-6
5 2014CAIS01 24:-9
497 successful hacks and 574 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A 1021869 0:00
B 15Y 0:05
C oldpreisnerboy 0:11
D1 omeravci372742 0:17
D2 Ghajini 0:17
E __1900__ 0:12
F1 Seidukan 0:10
F2 1021869 1:33

UPD3: Editorial is published!

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

| Write comment?
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Hoping to become expert with this contest.

GoodLuck and High Rating to everyone!

»
5 years ago, # |
  Vote: I like it +68 Vote: I do not like it

I wish all rated(<1600) users in this DIV-3 will be Unrated in the next coming div-3 rounds!

:-)

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

    the only way it's happening is if next Div-3 will be unrated because of some problems. Is that what you wish?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -19 Vote: I do not like it

      I'm pretty sure they wish those who are Div3 now soon to get over the 1600 threshold. They wish everyone a good performance, that is.

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

    Hugdiya

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain to me please, how the hacking session works? I would like to try it for this round. Thanks

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

    Iirc you get 12 hours after the contest to hack any solutions you want, but not for credit like the normal rounds. The only reward is to named as top 5 hackers (though the top spot is almost always halyavin!

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

I love vovuh's Codeforces Round!! I wish I would go to expert..

»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

I noticed that "(or 8)" was added next to the problem count in the copy-pasted part. On the last div3 round that part wasn't included. Does this mean that this round will have 8 problems?

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

    Yes, I suppose :^) But one spoiler: two of them will be in two (easy-hard) versions.

»
5 years ago, # |
  Vote: I like it -6 Vote: I do not like it

We need more div.3!!!

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

    we also need div.4 !!!

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it -17 Vote: I do not like it

      Sorry i have changed it due my wrong opinion.

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

        This problem is too hard for Div.4, the sum overflows int.

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

        do you mean, now we need less div 3?

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

          yes so that will be better for the beginners

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

            I don't know how having less contests is better for beginners. The more the better!

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

              yaaa... more contests are not necessary. Because we can participate in virtual contest. But division 4 will be helpful for the participant whose have rating below the 1200. and it will also encourage the rating below the 1200 and beginners. Because it not possible for everyone to cross rating 1600.

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

                if this comment gets more than 100 votes, I'll create a div4 contest in gym

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

      His dream come true.

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

Is there going to be a problem with an Easy and a Hard edition ?

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I love cf

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Best of luck to all.

»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

That "(or 8)" smells like an easy-hard version

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

An uncertain-problem number contest :D.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I wish everyone high increase in ratings today. Happy Coding!

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Happy New year all...

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I hoped that there will be 7 or 8 problems,because a new problem can provide you a new skill.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please make Div 3 rounds as frequent as Div 2. It is really good from the competition point of view. Otherwise Div 2 rounds include upto 2100 rated competitors on the ranklist which push coders like me to the bottom of the ranklist. Its really hard to even get to the top 1000.

»
5 years ago, # |
  Vote: I like it -6 Vote: I do not like it

All the way to Expert. :D

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good Luck and Have Fun all!!

»
5 years ago, # |
  Vote: I like it -31 Vote: I do not like it

Broken Div.3 again? Why not to use this problemset for Div.2, when its difficulty is even about Div. 1.5... Or division is adjusted only by problem A? Look at good examples of problemsets of Div.3 contests: Codeforces Round 479 (Div. 3), Codeforces Round 481 (Div. 3).

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

    I know when you're this low rating you shouldn't really complain, and I am not. I am genuinely interested who should be able to solve these problems ? Is it aimed for people with rating around 1600? first ones were.

    Anyways, liked the round and thanks for doing this to help beginners.

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

      This image was taken with "show unofficial" disabled, so it seems like many under 1600 rating were able to solve the problems (with the exception of F2).

»
5 years ago, # |
  Vote: I like it +30 Vote: I do not like it

After reading the problem C I hated the problem and quit solving :)

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

    Me too :v :v :v

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

    C was very interesting, there are several different ways to implement it (I think so), and you are to choose (find) one which is easiest to implement.

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

    The only thing which came to my head(after reading C) was to jump out of the window

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -23 Vote: I do not like it

    I think quality of rounds must be more important than quantity of them, seen many implementation and brute-force recently...

»
5 years ago, # |
Rev. 2   Vote: I like it +67 Vote: I do not like it

"Probably, participants from the first division will not be at all interested by this problems. And for 1600-1899 the problems will be too easy."

Sees reds failing to solve F2... O_O

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

    Div3 Problem Setters these days —

    If (We have Div1F problem)
    __ Print "Let's announce a Div3 round."
    else
    __ Print "Let's Wait for a Div1F problem."

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

      I don't think F2 is that hard. It is just a smart extension and careful implementation of F1 (provided I did this things correctly :p). Maybe a Div 2 F though.

»
5 years ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

I think E is similar to Your text to link here...

I am sorry that it just have chinese description.

You can see the solution of this from Your text to link here...

And I think that it can swap C and E

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

What's pretest 6 of problem C ?

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

    me too ! i got WA at pretest 6 :((

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

      It may well be a matrix with odd n and quantities of several numbers not divisible by 4, but divisible by 2. For instance, consider:

      input:
      3
      1 1 1 1 1 1 4 4 7
      
      output:
      YES
      1 4 1
      1 7 1
      1 4 1
      
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    maybe try: 3 1 1 1 1 2 2 3 3 4

    answer

    YES

    1 2 1 3 4 3 1 2 1

    my code accepted after handling this test case

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

    try this

    5 1 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 8 8 9 9 7 7 6 6

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

    My code works well for all the above cases.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Maybe a case when N is odd and not equal to 3. I rectified that case and got AC on C.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve D1 and F1

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

    For F1:

    You need to count total number of red vertices and blue vertices in all the tree, then you can use simple dp to calculate for every vertex i the number of red children and blue children, let this value is pair<int,int> dp[i], now let's root the tree at node 1 and traverse using dfs, for each edge joining vertex "u" and vertex "v" you can remove it and check the number of red & blue vertices in each new tree in O(1) using (total number of red & blue vertices, number of red & blue vertices of the child), and count good edges

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

    D1: binary search to check if we can get m pages in range [1, n] days

    optimal strategy to finish m pages in x days is to use largest value in 1st days, 2nd largest in 2nd days, ..., x largest in 1st days again (cyclic)

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

    D2 : Binary search on number of days. To find maximum number of pages he can write in d days, Greedily pick largest a[i]'s and distribute them over d-days. This will work because in optimal solution, difference between number of elements in any two days is less than or equal to 1.

    F1 : First store the red and blue vertices in subtree rooted at v for all v, using dfs.

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    D1 or D2 : Let's apply binary search on the number of days required. For the current mid, let us greedily write pages restricting ourselves to at most "mid" number of days. We take the maximum value of a and write a[n] pages on day1, a[n-2] pages on day2 and so on. If at any point we exhaust the number of days, we continue by reading 1 less page from the current book. If at any point we are able to read m pages then mid is a candidate for the answer. submission

    F1 : let's root our tree at vertex 1 for simplicity. For every vertex, let's calculate the number of blue and red vertices in its subtree. We can do this using dfs. After this we can check for every vertex by removing an edge to one of its children. The number of red and blue vertices left in each of the new trees is blue[v], red[v], red[1] — red[v] and blue[1] — blue[v]. Here we are at vertex u and v is one of its children. We can calculate answer easily then. submission

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

    For D1:

    I dont know if my solution will pass, but i used dp.

    First, i noticed that if we will drink k cups in some day, then we need to drink the lower first, keeping the higher amount of caffeine to the end, so i sorted the array of inputs in the beginning.

    Then, the dp state is dp[i][rem] is the number of days we need to write rem pages, using cups with indices from i to n, the recurrence is simple as we try to drink k number of cups in each day such that k is in this range [0,n-i+1].

    solve( idx , rem ) = min( solve( idx+1 , rem ) , solve( idx + k , max( 0 , rem-k ) ) + 1 )

    This solution is O(n*n*m) which is not bad. That's why i didn't manage to solve D2 as this solution will not pass the time or the memory limit.

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      for D1, 1. sort them in decreasing order. 2. apply binary search on ans. for F1, do a dfs to know ho many reds and blues for each subtree

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

very good problems for DIV3 , enjoyed very much . Hope all my problems gets accepted after hacking phase.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Author should stop setting problem C.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what is testcase # 9 in D1?...T^T

»
5 years ago, # |
  Vote: I like it +35 Vote: I do not like it

I think, I should change the first sentence in the announcement to "Miss Div. 1 rounds? :)"

But surely, this was expected that F2 is a pretty hard problem ¯_(ツ)_/¯

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
5 years ago, # |
  Vote: I like it -30 Vote: I do not like it

The problem setter of C should be banned for some time for creating such bad problem

»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

I hate filling numbers in matrix...it's so time-costing and brain-f***ing to consider about symmetry and indices...my poor little brain...

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it possible to optimize the dp solution for D1 to solve D2?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

WTF Why B test 1 1 Answer 1 ?!?!??!?!?!??!

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

    Because giving away 1 candy would mean even and odd sum are equal to 0 because no element remains. So the answer should be 1.

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    The amount of candies you eat in odd days is the same as the amount you eat in even days, which is 0 because you don't eat in any.

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

    0 = 0

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Bonus:

Solve E with additional constraint:

first and last pairs are also considered adjacent for the 4th constraint (formally b1 ≠ bn and g1 ≠ gn)

Fun fact: seems like this problem can be solved with this limitation in all the cases when the original problem can be solved.

Who can prove it or find a counter-test (or bug) in my solution 50193010, that solves problem with this additional constraint?

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

    i solved the problem with a simple pattern that also satisfy this constraint

    first use all pairs i(from 1 to k) and i + 1 mod k

    then all pairs i and i + 2 mod k

    after that pairs i and i + 3 mod k

    and so on,you can easily see that this patern satisfies all the constraints

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

    I don't see how your solution solves this problem. It fails on the first testcase itself, I think (b1=b4).

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

      For the test case 4 3 my solution prints

      YES
      1 2
      2 1
      1 3
      3 1
      

      I see no problem there.

»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Really enjoyed the problemset. Best Div.3 round so far.

»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

How to solve F2?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The contest would have been great if E and C were swapped.

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

    What purpose swapping them will serve. Afaik both of them carries equal points??

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

      Yes all carry equal points. Your point seems good, these things actually remind us to pick easy questions first (until you reach that level when C's implementation is a 8-10 min. cakewalk for you)

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    Problem E is rated 2000. If E and C were swapped,it would be rated no more than 1600.

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

Can someone explain D2. I can't understand why we used a binary search in this.

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

    Forget about the binary search for now, the idea is that for every number of days we know the optimal cups to drink, and their optimal order too, so we can get for every number of days the maximum number of pages we can write (we will talk about this optimal order later).

    So if we know this kind of information, we can simply check all numbers of days between 1 to n, and select the least one that allows us to write at least m pages, and that's will be our answer.

    Here's where binary search helps, as if we can write x pages in k days, then we can write x or more using more than k days.

    The optimal cups to drink for a given number of days k is:

    The largest cup in the first day, then the second largest one in the second day, and so on until we take k cups in the k-th day. Of course we can take more than one cup in a day, then we extend for the first day by drinking the k+1-th cup (don't forget to subtract the number of cups that are already drank as in the first day we actually will drink the k-1-th cup first then drink the largest cup, so we need to subtract it, same goes for all days), and for the second day we also extend it with the k+2-th cup, and so on.

    submission

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

These two participants have same source code in problem A, B, C, D1, D2, F1

tim25871014 Fantasyice
pA 50167147 50183932
pB 50185024 50186012
pC 50179384 50186141
pD1 50192694 50193272
pD2 50194759 50195089
pF1 50191152 50191524

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a way for which test case my code failed for B ques. It was hacked. I implemented this logic — store prefix sum of elements in odd and even indices in an array, and store the total sun. Then loop through given array once again , and check if sum to left of it the odd(/even) and right tO it the even(odd) prefix sun if equal to (totalSum-arr[I])/2. My submission is this: https://codeforces.com/contest/1118/submission/50179395[prob. B](https://codeforces.com/contest/1118/submission/50179395)

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

    Hack Test:
    1
    6575

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

      yeah found (in submission history). Thanks.

      My code is giving output as 0 for n=1. It should have been 1 instead.

»
5 years ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

When does my brand-new rating reflects? I have to show off my [ LEGENDARY SHINING BLUE ] to my friends

»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

"I forgot to fix participant types (official <-> unofficial) if you registered before rating changes of the yesterday contest. It will be fixed after the contest. Thus, you will be a rated (official) participant if and only if your current rating is strictly less than 1600. Mike." **** Some people above 1600 had their ratings increased

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

    Oh, sorry. I'll fix it soon. So don't be surprised with temporary disappeared ratings. I'll fix the issue and return ratings back.

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

    Also, "Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

    take part in at least two rated rounds (and solve at least one problem in each of them),
    do not have a point of 1900 or higher in the rating."

    Check https://codeforces.com/contest/1118/ratings, in top 10 you can see 7 are giving the contest first time

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell why my solution for D2 fails for test 49?
In my machine its output is 1 as expected?
The problem is solved when is decrease the upper bound for binary search to n + 1.
¯_(ツ)_/¯

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

    Because in the test 49 n=1 , but in the fuction check ,

    for(ll i = 0; i < mid; i++) pgs += arr[i];

    the i is too large , and then the arr[i] is unexpected

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Why the updated rating has gone? Any particular reason?

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

vovuh, Editorials please.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

the user ereased rating who has been skipped

»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

It looks like codeforces have a new way to tackle plagiarism. The one whose solutions are skipped have been given a score of 0, and their rating changes have been calculated by keeping that score in mind !!!!

»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve F2? I don't have any idea about it. Waiting for Tutorial.

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

This submission 50181596 got AC on D2 and WA on D1.

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

can anyone plz provide me the link to editorial