300iq's blog

Codeforces Round #562
By 300iq, 6 years ago, translation, In English

Hi!

I'm glad to invite you to take part in Codeforces Round 562 (Div. 1) and Codeforces Round 562 (Div. 2), they will be held in May/26/2019 18:35 (Moscow time). The round will be rated for both divisions (^人^).

Participants in each division will be offered five problems and two hours to solve them.

The problems were written and prepared by me. Thanks to KAN for his help with the round, to sunset, TLE, Sulfox, isaf27, Lewin, Aleks5d and wrg0ababd for testing and task discussing! Also, thanks to MikeMirzayanov for amazing systems Codeforces and Polygon!

Congratulations the winners!

Div1:

1) DearMargaret

2) OnionPringles

3) Errichto

4) maroonrk

5) Um_nik

Div2:

1) Szoboszlai10

2) lelolas

3) ndmitrovic

4) prick

5) Stardust

Editorial

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

Comments Comments (126)
| Write comment?
»
6 years ago, # |
← Rev. 2   Vote: I like it -47 Vote: I do not like it

1

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

How many problems are shared between Div1 and Div2?

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

    Why do you ask?

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

      why he should have reason?

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

      Sometimes it helps to understand the difficulty of the problems.Nothing else.

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

    Usually,the problems "C""D""E" in div2 are the same as the problems "A""B""C" in div1,respectively. As a result,there are three problems shared between div1 and div2.

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

I wish problem statements are short like this announcement!

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

Why are the links for both divisions duplicated in the attachments section of the annoucement ?

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

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

300iq's problems be like:

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

Long time no see!!!

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

Lets have a great contest Guys . Enjoy everyone and best of luck for it

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

300iq is return back with awesome contest :)

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

I hpe the problem statements are as short as the announcement :)

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

Which is Harder Red in Codeforces or Grandmaster in chess?

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

How many problems will be in contest?

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

    Just wait for another 30 mins. And you will have the answer to your question.

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

    5 problems

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

    Participants in each division will be offered five problems and two hours to solve them.

    Dude, please read the announcement.

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

I like weekend competitions, thank you 300iq

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

Anyone else facing problem in hacking? I get 403 when I try to open code even though I locked.

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

How to solve C? I could easily write O(nm) DP solution, but how to optimize it?

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

    I used binary search from 0 to m for O(nlog(m))

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

      I tried to go for this approach too, but couldn't figure out how to simulate given an answer.

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

        have some int prev = array[0]

        i = the max number of moves a number can increase.

        for every int a, if a > prev, check if it is possible to increase a to prev in i moves. If not, prev = a.

        if a < prev and you cant even get to prev by increasing a i times, return false,

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

      how to check for some M if its possible?

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

        Go from left to right through all the numbers. Attempt to turn the input array into a non-decreasing array. Say when you're at a given number, the biggest value yet has been X. The current number has value Y. You'll be either able to transform that number into X, or increasing the value of that number will be worthless; so if (Y+M)%M > X, the maximum of the array remains unchanged; else, if Y is also < X, then that M isn't valid.

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

    Yeah me too

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

    Use something like a binary search...

    Say we can use k operations to make it non-decreasing. We can obviously do it in k+1. So search for value where it will be impossible to do in lesser steps.

    See this Solution

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

    what about a binary search for the answer?

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

    The way I did it was using binary search because the answer is in [0, M]. Checking if a value is a valid solution means doing a greedy: attempt to turn the input array into a non-decreasing array with a set of operations, lesser than value X. If value X is valid, then you might find another answer lesser than X; otherwise, the answer is surely bigger than X.

    That greedy verification implies going from left to right through all the numbers, and at a given number, you try to approach the maximum of the array as much as possible; that means either not doing anything with the number, or otherwise, you can always set it to that maximum of the array.

    Well, I hope this logic works, still waiting for hacks

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

That moment when I realized problem B can be done by sole bruteforce...
I need better observation tho :D

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

    Which bruteforce?

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

      Every substring of length 9 contains a triple such that $$$x_s = x_{s + k} = x_{s + 2k}$$$. This allows for a brute force solution to pass.

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

        How did you get that?

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

          I couldn't figure out a way to prove it during the contest. So I just wrote a brute force code which checks for every length N string, whether it contains a triple or not. It only took about 10 minutes in total.

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

          It felt like because there are only two characters, avoiding those triples seems pretty hard. If you want to avoid triples, the number of restrictions on the string grows faster than the length of the string. So I wrote a script to verify all cases. Maybe there is a nicer way to prove it, though.

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

            I just assumed it cannot be longer than 20, with a huge reserve, since if fits in TL easily anyway.

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

            I don't know if there's a particularly nice proof for this case, but the general version of this problem has been studied and some values are well-known: https://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem

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

              Yeah, the 9 on top left of this table is actually the same 9.

              Ramsey theory did seem like a thing to think about, the problem is that Ramsey theory tends to give absurdly huge upper bounds.

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

            deleted. :\

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

    I did that in the end,but how to prove it fits in TL?

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

      I'm not sure about proving, but by generating all possible cases, the longest "shortest pair $$$(l, r)$$$ with fixed $$$l$$$" would never exceed $$$10$$$.

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

Good tasks, thanks)

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

How to solve C? Tried some mo's algorithm, then realized that I forgot it has to be in order.

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

    For each i and bit position b compute the smallest index minReachable(i)(b) >= i such that a(minReachable(i)(b)) has bit b set and minReachable(i)(b) is reachable from i.

    Processing the query: reachable if there exists bit b set in a(y) such that minReachable(x)(b) <= y.

    54686628

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

Congratulations to amnesiac_dusk for becoming red.

I hope so.

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

Was anyone able to hack anyone?

If so, what was the hack

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

A, C and E are cool, B quite standard, D tedious but still not so bad (because it requires some ideas and observations). So the round was nice but WTF is up with those Shi/Fou instead of YES/NO? I had to look back into the statement every time I run my code. This should happen only if problems are translated from a local contest to CF mirror. Don't do it in the future.

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

    I feel the same every time I see TAK/NIE in polish tasks.

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

      At least "NIE" has some resemblance to "NO" (same first letter) so it isn't that bad. Same if it's in some other random language like Nein/Nyet.

      Ofc. using TAK/NIE would still be stupid in a CF round that doesn't come from a local contest.

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

        That comment made me looking up all CF contests your did and surprisingly I haven't found a single TAK/NIE

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

          Maybe I don't take problems from local contests? :D

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

            No, I just've thought you might've changed your opinion in the past (I personally don't see anything bad in TAK/Nie and Fou/Shi) and it would've been amusing to look that up now :)

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

    It's because 300iq is learning Chinese recently.

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

    C is cool and B is standard? Didn't you swap the problems?

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

      I like dynamic programming, but indeed C was standard (still cool for me).

      I got the idea for B in 1 minute that long strings have such triple, after failing to construct a big string that doesn't. Something like this appeared in many problems.

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

    const string yes =..., no =...;

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

      I had to look back into the statement every time I run my code.

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

    Oh, i thought that it won't be a problem..

    I'm sorry if it spoiled the fun of the contest for you :(

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

      It doesn't ruin on the contest, but it's something very easy to avoid for other setters, and I hope my comment will prevent any future occurrence of something like this.

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

    Btw, why is D tedious? The intended solution has a very short implementation in ~100 short lines.

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

      Ok, I change my mind. My implementation is much longer because I did more (unnecessary) things.

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

Hi! Can someone please tell me why greedy approach does not work for div2 C? (C. Increasing by Modulo). This is the approach I am talking about: for all arr[i] where i>1,<=n if(arr[i]<arr[i-1]) either increase arr[i] or decrease arr[i-1](increase to m, then to arr[i-2]). store number of operations needed for each arr[i], and answer is the maximum among stored values. Thanks

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

    Sorry I missed this part, either increase arr[i] or decrease arr[i-1]

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

how to solve div. 2 E ?

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

Please who can explain the solution to div2 B

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

    Each valid solution should contain a number that occurs in at least half of all the given pairs. There can't be more than 2 numbers with this property. Attempt to use each one and then you can check if that is possible going in any order through the array; the first time you find a mismatch with another pair, try to take one value from it.

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

    choose a[0] and check that the remaining pairs whom values aren't equal to a[0] share a commun number, if not check for b[0].

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

Why was there so many wrong submissions for d?! Is there any corner case?

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

    My solution is for every pair of leaves check if you can change question marks accordingly. But actually it's the other way around, first change ?s then every pair should satisfy the condition. I got WA and it's not a proper solution(found a testcase afterwards) Maybe also other people tried this?

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

Hmm! Is this E: https://community.topcoder.com/stat?c=problem_statement&pm=14159&rd=16690.

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

    The statement looked some simple that I immediately started googling some keywords but couldn't find it :/

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

      Yup, and with the same reason we didn't find it before the contest! ;(

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

      I googled and found this. Started by searching "two permutation xor" something, I found this at some reference in a recent paper. However I'm too sleepy to read this...

      OnionPringles also told me that same problem was in IMO 2005 Shortlist.

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

      https://community.topcoder.com/tc?module=ProblemDetail&rd=16690&pm=14159 This page says that you have tested that problem.. Am I missing something?

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

        XD

        That's perfectly possible. I have a very bad memory for problems and my friends sometimes laugh at me for that. I wouldn't ever be surprised if that was my problem, to be honest.

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

    I am so sorry! I thought that my problem is original :(

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

      Will this round be unrated?

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

        Nope

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

        No, problems that are not new for some participants is not a reason for unrated.

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

          But I think phoenix__jpn should be unrated. He just submitted problem E in 15 minutes and get rank 88. In his code you can even see 'SRM686'.

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

            As per rules, what he did is within rules

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

How to solve C ??

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

There is no scoring distribution in the blog.

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

Problem E: & and &.

Maybe sunset and TLE are not familiar with well-known problems in China.

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

How to solve div 2 B?

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

    Not in Division 2, but I think this works. We do casework. Obviously, one of the two numbers in the first pair must be x or y. WLOG, let the first pair contain x, and split into two cases based on which number is x.

    For each possible x, iterate through the remaining pairs. One of the two numbers in the first pair that does not contain x must be y. Iterate through both of these possible values for y to check whether they work.

    As we have four cases and can check each case in O(N) time, this will easily work within the time limit.

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

    Check which pairs of numbers contain a[0] and then check if there is some number contained in all the other pairs (you can use map for that). Then do the same for b[0]. My solution

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

    My approach :

    • take an array temp and push 1st pair

    • push another pair which does not have any elements same as 1st pair

    • if there is no other pair then 1st pair is our answer else

    • now pair(x,y) must be one of the pairs of this 4 elements

    • take every pair and check

    • if we find at least one pair then return YES else NO

    solution : https://codeforces.net/contest/1169/submission/54683336

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

weak test case in problem B(div 2)

this is my ac code https://codeforces.net/contest/1169/submission/54686525

but for the following test case i am getting wrong answer

6 8 1 4 1 4 1 4 2 3 2 3 1 5 3 5 4 5

the answer should be "NO" but my code output is "YES"

although this is ac code

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

Hah, there are only four failed solutions in the entire Div1. A bit too strong pretests maybe?

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

    Pretests can't be too strong :)

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

    There's no such thing as pretests that are too strong! (There are sometimes pretests that take too long to run though)

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

Am I the only one who solved overcomplicated D1B with four bitsets?..

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

Why did my submission 54684486 fail at test 4?

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

A relatively difficult Div. 2 than usual with $$$<1800$$$ official submissions for B and $$$<600$$$ official submissions for C. But questions were interesting!

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

    It's normal because people with rating from 1900 to 2099 participated in div 1

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

MikeMirzayanov, I submitted solution for Div1 B, then again after around 20 minutes I submitted solution for Div1 B with some modifications, but my earlier solution is skipped, which must be considered as per rules. What was the reason?

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

    According to the rules your last submitted solution will be considered even if your previous gave AC and the last solution gave WA.

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

    Only the last correct submission is considered for testing. The rest are skipped.

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

How Solve B.pairs problem??

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

Concise problem statement, quick systems test, quick rating update, quick editorial. Good contest!

→ Reply