vovuh's blog

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

<almost-copy-pasted-part>

Hello! Codeforces Round 579 (Div. 3) will start at Aug/13/2019 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. 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.

</almost-copy-pasted-part>

UPD: Editorial is published!

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

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

Auto comment: topic has been translated by vovuh (original revision, translated revision, compare)

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

I hope it will be a good contest!

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

I hope this round will rebuild our shattered hope on easy rounds.

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

    This is QUALITY comment how could anyone dislike it?

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

      Teacher: What is most available free stuff in the world?

      Student: CF downvote, Sir!

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

Vovuh's rounds are always good!

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

After this contest my final exam will be started....But I will keep doing contest

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

Best ways to increase your contribution :)

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

    That means It's also a tricky part... You guys makes me disappinted..

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

    The comment is hidden because of too negative feedback, click here to view it

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

    and make a memes for contribution guys XD

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

Thanks MikeMirzayanov for adding Diagnostics Hint feature on RE.

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

    Sorry to disappoint you but the diagnostic hint is disabled in contests.

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

Slide2.PNG

This is participants attending this contest at night 24:00.

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

Will the downtime of polygon affect us? Will there be testing in the contest?

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

I didn't do much with my youtube channel recently because I was busy with summer schools and stuff, and this is bad for publicity :)
So I guess I will do screencast with English commentary for this round and I'll try to go more in depth about solutions. That is, if Mike and team will fix Polygon. Hope to see you on the channel!

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

    deleted

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

      After the contest, of course. This round is rated for many people.

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

        it seems that Polygon is fixed, at least temporarily.

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

Is there any negative point for the unsuccessful hacking attempt during the 12 hours of hacking period?

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

    No. And no positive point for successful hacking attempt either.

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

Unfortunately there is an issue with CF-Predictor and it will not be available during coding phase of this contest. CF-Predictor is going to be back after 22:00 UTC today.

I'm very sorry for the inconvenience.

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

Me before Contest : second thing don't tell what you think I will be I'm the one at the sail I'm the master of my seeeeooh oooh
After Contest : Paaaaaain you made a you made a believer

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

No stress Happy round

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

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

Long queue times anyone? Sorry posted previous comment in russian :C

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

Oh my god! Queueueueueueforces

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

The system is not allowing me to submit even a single solution. It is always showing "You have submitted exactly the same code before". please help!!

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

    It means that the the solution has been submitted. You don't have to submit again.

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

      It was showing that for different code. I only was able to submit on m2 then.

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

Thanks for the round. It sucks. Can u fix your servers pls, the submission was in queue for about 7 minutes. Make it unrated or increase the time. Thanks

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

    Please be patient, they said they are fixing it, besides it's happening with all of us.

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

    To solve problems or for learning from this platform, we don't need to pay anything. It's totally opensource. This community help us with many things. Imagine the number of submissions per moment. It's pretty obvious that there will be problems sometime. Just be patient.

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

contest should be unrated i submited my solution 12 mins ago

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

Queueforces Div3

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

I use gmail for codeforces. How can i enter in codeforces2?

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

    Yes I also need to know something about this ; If anyone can help...?

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

      use "Forgot your password?" option in login window to create a password on codeforces.com. You could then use this to login to m2.codeforces.

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

MY CUR PING : 600000 ms and it keeps on increasing :/

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

MY CUR PING : 600000 ms and it keeps on increasing :/

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

pls make it unrated!!!

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

Contest extended by 20 minutes, but the situation that has already happened cannot be reversed. It's not good for successful contest. :(

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

make this round unrated

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

Wondering what happens if you hack a solution, and it gets compilation error.

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

Me waiting for the verdicts.

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

deleted

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

Is there a solution in python that runs in time for D2? If not, then why support it at all! frustrated ^^ The problem was very nice to think about, thank you — I am curious what I did wrong...

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

What is TC 37 in F1 ?

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

Sorry for slow website and judge queue. I think it was the first major queue during the last months. Actually, I do not understand the reason for now: is it because of too heavy tests + easy problems or there is another reason. I'll investigate it. I'm doubly upset because I was thinking about ideas for these problems for several days (it seems that all ideas belong to me). I hope you enjoyed the problems!

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

    Even though it queued a bit in between, it turned out to be a good contest. At least for me, I enjoyed it.

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

    Really enjoyed the problems, Thanks a lot

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

    Hello... I login into codeforces using the gmail account ; but it was not there on the alternate version of the website ( The light version ) ...

    Is there someway of login on that light version for people who login there accounts using gmail...? Please suggest ; thanks in advance...!

    Edit : Got it...! Thanks...!

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

    Are you feeding the hamster properly?

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

Upd: now I got what is the problem with C. Can you tell me what is wrong with other ones?

Can someone please tell me why I got WA on all of my submissions in this contest? (except A)

https://codeforces.com/contest/1203/submission/58755675

https://codeforces.com/contest/1203/submission/58763681

https://codeforces.com/contest/1203/submission/58744361

https://codeforces.com/contest/1203/submission/58770060

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

What is testcase 33 in D2?

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

Failed to solve a QUEUE question in interview this morning, and now CF is showing me QUEUEEEEEEEEE. God's pun game is strong :(

Could have made WA to AC if it wasn't QUEUEEEE, this is frustrating..

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

I think the order should have been C-A-E-B-D-F, but I suppose it doesn't really matter in Div 3 contests.

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

how to solve F2? I spent 2 hours thinking :( . Is there some standard algorithm?

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

    First do the ones with positive reward, then most possible ones with negative reward by knapsack.

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

in queue:)

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

R.I.P QUEUEFORCES

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

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

36 hours hacking phase?

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

F2 is similar to Problem I in NWERC2017.

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

why is the open hacking phase of 36 hrs??

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

this contest — queue = PERFECT!!

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

Why the duration of open hack is 36 hours, not 12?

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

Why does the timer for open hacking (https://codeforces.com/contest/1203/standings) say that the open hacking phase lasts over 35 hours?

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

still 36 hours open hacking?

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

Contest was nice.

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

This contest should get unrated. I had to wait for a long time to see the whether the test cases passed or not. This wasted a lot of time of mine.

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

    Fully agree with you

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

    I think, you should solve further tasks instead of waiting verdicts

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

    Next time you should work on other problems while it is testing, so you are not wasting any time.

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

it seems Dsiv.3 always have a huge number of participations this round have a 13216 participations, which I think is one of the most participations in contests. maybe it should increase the number of Div.3?

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

    Increasing the number may cause the quality goes a little bad. Plus, there is once-a-week Educational rounds.

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

How to use m2.codeforce?

I only use the auto?(one click?) login of Gmail.

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

    You need to set new password with "Recover password" link.

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

Please help with the solution of F2

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

I'm getting WA on test case 18 in problem D2. Could someone help me to figure out what is going wrong. This is my submission 58778018. Thanks in advance.

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

    Replace else in last for with if (i < n - 1), because there is a case, where removing substring is between $$$pre[0]$$$ and $$$suff[1]$$$.

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

how to solve f1 ??

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

Does the hacking in hacking phase gives points?

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

How to sort the input in optimal order in F2 ?

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

In question C I got TLE in this submission 58730683 and pretest passed in this 58757237 can anyone explain why ??????

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

    Maybe it's because of the time it takes your gcd function to go from one step to the other

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

      I also got TLE in test 5 during the constest. I used faster input methods and got AC. As you can see your solution ran in 850 ms, which is just a bit below TLE.

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

I think the problems are really great, if it not were for the technical issues it might be an excellent contest.

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

Best ways to get downvotes in a div.3 post:

Lv.1 wish a good contest!

Lv.2 No broken div.3 again!

Lv.5 WTF, this is a div.2 or even div 1.5!

Lv.10 See this is good examples of div 3...........

Lv.100 This comment is hidden because of too negative feedback, click here to view it

Lv.999 Please give me upvotes.

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

The common divisor of 2 integers $$$a, b$$$ is the divisor of $$$gcd(a,b)$$$. I tried to prove in the way.
Every integer $$$x$$$ can be rewrite under the form of multiple of prime factors:

$$$x = p_1^{m_1} . p_2^{m_2} ... p_k^{m_k}$$$

$. &

$$$ y = p_1^{n_1} . p_2^{n_2} ... p_l^{n_l} $$$

We construct $$$gcd(a, b)$$$ by choosing all common prime factors p with the lowest exponent each factor.

And, we construct a arbitrary common divisor by choosing some common prime factors with the exponent each factor always less or equal to the lowest (i choosed in gcd).
Following this manner, the common divisor of $$$a, b$$$ is always divisor of $$$gcd(a, b)$$$.

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

I think this Codeforces round is a bit easy, but it's still very good, too. A good writer with a good round.

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

thank to the extend 20 minutes, I can solve the D2 in the last minute. however, waiting for 3 problems' judge is not a good feeling. hope nobody hack me so that i can be an expert this time.

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

How to solve D2 Remove the Substring (hard version)(https://codeforces.com/contest/1203/problem/D2) ?

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

    There are 2 cases: 1)Answer — prefix or suffix of string s 2)Consider 2 subsequences: leftmost and rightmost.Assume that we take first i letters from leftmost subs. and the rest we take from rightmost.So you have to check all values such as : rightmost[i + 1] — leftmost[i], and maximize it.

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

is this contest rated??

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

Can F1/F2 be solved by some Greedy approach? Many solved it by Dynamic Programming. I tried Greedy during the contest but it failed.

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

    if bi is bigger than 0 then use greedy, add them all if ai is smaller than r. and for left bi which is smaller than 0 use dynamic programming

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

Can someone explain the idea behind problem D?

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

    find the rightmost place and the leftmost place in s for each letter in t, then (leftmost[i] — rightmost[i + 1]) for every letter in t, get the max one, that is the answer

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

Problem F is a cleverly disguised "regular bracket sequence" problem. See 1745 on timus.

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

Editorial by me incase anyone still needs it:

A. Circle of Students

explanation
soln

B. Equal Rectangles

explanation
soln

C. Common Divisors

explanation
soln

D. Remove the Substring

explanation
soln

E. Boxers

explanation
soln

F. Complete the Projects

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

    How can we prove that projects should be considered in decreasing order of a+b?

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

      By exchange argument (Um_nik's video has pretty good explanation)

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

        You actually watched this... I don't understand why, but ok, looks like it worth doing :)

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

          I came up with knapsack idea but then could not figure out sorting order (I still don't get intuition behind it) and I wrote some really strange thing with bitmasks which worked somehow but I was sure there is simpler solution and there was no editorials so I checked the video. I did enjoy parts I have seen tho, if you're seeking for some feedback :)

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

            Intuitive intuition: Let's look on the process from the end, working backwards in time. We have to have at least $$$a_{i} + b_{i}$$$ rating, and now these projects are good (we are going back in time so our rating will increase), and it is obvious that we should do the projects in order of increasing necessary rating (which is $$$a_{i} + b_{i}$$$ now).

            Professional intuition: I'm sure that I should sort the projects according to some rule, so I will write inequalities for exchange argument and see what I get. You can see in screencast that at first I guessed wrong, and even with correct comparator I was unsure until I wrote the inequalities and everything worked out.

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

      Lets say you have at the moment rating r. And you have (a1, b1), (a2, b2)... (an, bn). Assume we already have ordered set of problems we take (No matter what this order is). Then for each taken project: ai >= r + b1 + b2 + ... + b(i — 1). So you can add to both parts bi and get (ai + bi) >= r + b1 + b2 + ... + bi. So for each i you need ai + bi just not less than some const. That gives us right to assume that if we have correct order then you can take problems in decreasing order of (ai + bi).

      P.S. There are some flaws I think, but common logic is the same.

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

        Your inequality is wrong: instead of ai >= r + ... , it should be ai <= r + ... Since we require the current rating to be >= the project requirement.

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

          Oh thanks. So final inequality is ai + bi <= const. And there is more logic to sort in decrease order.

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

      Let say we have 2 "negative" projects (a1, -b1), (a2,-b2) with b1, b2 > 0 and a1-b1<=a2-b2 and we can successfully complete project (a1, -b1) first follow by project (a2,-b2). Then we can always change the order and successfully do (a2, -b2) first follow by (a1, -b1): + complete (a1, -b1) equivalent to r>=a1 and r-b1>=0. Then do (a2,-b2) equivalent to r-b1>=a2 and r-b1-b2>=0. + complete (a2,-b2) first equivalent to r>=a2 and r-b2>=0. Then do (a1, -b1) equivalent to r-b2>=a1 and r-b1-b2>=0. All these conditions can be followed from above (where r-b2>=a1 because we have r-b1>=a2 and a1-b1<=a2-b2)

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

Can anyone please help me to understand the problem E? I dont understand the problem for a while. It would be really helpfull. Thanks in advance. :)