Um_nik's blog

Codeforces Round #576 (div.1 + div.2)
By Um_nik, history, 5 years ago, In English

Hello!

I'm glad to invite you all to Round 576 which will take place on Jul/30/2019 17:35 (Moscow time).

There will be 6 problem in both divisions.

Round is based on Team Olympiad in Computer Science Summer School. It is (yet another) summer school for schoolchildren organized by Higher School of Economics and "Strategy" Center in Lipetsk. Almost all the problems are authored and prepared by teachers and teaching assistants in CSSS: Um_nik, Burunduk1, fake123_loves_me, MakArtKar, Villen3tenmerth, Aphanasiy, Gadget. One of the problems is authored by Merkurev (just because we are friends :) ). One more problem for the round was added by KAN.

I would like to thank KAN for CF round coordination, I_love_Tanya_Romanova, Merkurev, Rox and 74TrAkToR for testing, and Codeforces and Polygon team for these beautiful platforms.

Scoring will be announced.

Upd: We added one more problem to div.1 contest, now both contests have 6 problems (4 in common). The round is not combined, if it were, I would write "combined" in the title.

Scoring distribution:
div2: 500-750-1250-1750-2500-3000
div1: 500-750-1250-1500-1750-2250

Congratulations to our winners!
div.1:
1. Radewoosh
2. tourist
3. mnbvmar
4. Benq
5. pashka
div.2:
1. ChthollyNotaSeniorious
2. Honour_34
3. idxcalcal
4. shogunator
5. yijan

Editorial won't be published.

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

Comments Comments (323)
| Write comment?
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Auto comment: topic has been updated by Um_nik (previous revision, new revision, compare).

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

Wow wide range of writers ( LGM to pupil )

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

Looking for a crazy contest :P

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it -22 Vote: I do not like it

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

    Guess, Mike is a part of "Codeforces and Polygon team".

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

      Sorry, I shouldn't have made such non-sense comment. I won't repeat this again. :)

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

      Well, he is not saying that they didn't thank Mike, he is saying that they didn't specially thank Mike.

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

Will there be stories about Um_nik's teal hair?

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

    I also want to know something about his hair,ha-ha.

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

Why You forgot to thank specially to MikeMirzayanov for Codeforces and polygon platform? He can block your account chinese!

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

Oh~,long time without a div1+2 conbined contest.

I was excited as soon as I saw this contest appear in the list of upcoming contests.

Hope the problem ststements will be as short as the announcement!\XD

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

    The last Div.1 + Div.2 contest was Codeforces Global Round 4 (and the last Codeforces Round was Codeforces Round 513 by Barcelona Bootcamp (rated, Div. 1 + Div. 2), 10 months ago), but is today's contests Div.1 + Div.2? I think only the notice says that way, and these are two separate contests.

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

      No, there have been many Div 1 + 2 combined rounds, just not labelled as such. The Mail.Ru rounds and Global rounds were all Div 1 + 2.

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

        Oh- I missed that. I thought only Codeforces Round #NNN, but you are right. I should edit the part of that. (And anyway, what do you think about my question?)

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

          Yeah, today's round is not Div. 1+2 as per the convention I have seen and they should omit it from the blog post title.

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

      There will be 6 problem in division 2 and 5 problems in division 1.

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

        I was saying this out of strange after seeing it.

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

I wanna get high rating.

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

points or plus ???

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

Anybody knows the difference among div.1+div2 and 2 separate rounds?

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

    Div.1 + Div.2 Round is One contest in which Div.1 participants and Div,2 participants participate altogether and 2 seperate rounds are literally Two contests in which participants participate in his own Division.

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

Why results of div1 and div2 is n

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

I think Um_nik has not much experience to make a good contest, so I will not write this contest.

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

    Oh no, please write our contest!!!!!1!

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

      what happened to your hair ?

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

        I died dyed them

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

          Good to know :)

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

          MWM, for a moment I thought that after solving many problems your hair started changing its colour!

          Btw, I think is better if you dye it one part red and the other black (just like nutella)

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

          You look like a combination of Limmp and Ramzes666.

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

        He want to say he's the king of cyans, since he worth more than 1000 cyans

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

          Um_nik is the new exchange coin, he worths 1024 cyans, 256 blues, 64 purples, 16 yellows, 4 reds, one nutella.

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

Usually when one puts + between "Div. 1" and "Div. 2" it means a combined round, and names for posts for regular separate rounds don't contain a substring Div at all. You explained the separateness of the round in the update and wrote explicitly that each division has 6 problems (4 in common), but anyway I suggest not to use the + sign to denote separateness next time(s), otherwise someone will be confused.

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

    Yes, I understand the confusion. I didn't know that there is a fixed convention, sorry.

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

How long the contests are?

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

"We added one more problem to div.1 contest" <3

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

why start at 17:35, why not at 17:30?

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

    It may be farfetched, but (because) it's usual start time of the contest. So, is there a reason why the competition must start at 17:30?

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

    It's good to think that the contest starts at 17:30, because of the registration.

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

Is it rated?

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

hello :D I have a doubt. What is a hack?

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

    When you are able to prove some submission wrong by providing a clever test case whose output is wrong according to tester code/verification of output by the system. Hope it helps:D

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

    At codeforces , you can see the code written by others. So after you see others code which have passed the pretest, if you think there may be some data that his or her code may give the wrong answer, you can submit a piece of data ,and if his or code give the wrong answer , that means you hacks successfully, and you will get point, otherwise, you will loss point.

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

gl & hf all

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

the number of registration in div.2 must be over than 10k before contest!

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

Scoring doesn't seem to add up for common problems. Interesting...

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

It would be a good contest excited to solve problems.

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

I can see there's nothing strange about the performance of HanwhaEagles in this contest.

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

After a long time you see so many full scores in Div 1 and hacks too, indicating "Author's mind is weak" Um_nik

Spoiler
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -43 Vote: I do not like it

    What is your problem with full scores?

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

      However hard I try, I can't get it right. My mind is weak. But seeing so many full scores makes me feel Author doesn't have hard/interesting questions.

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

      In general, it's not good to break ties between too many contestants at the top just based on time. Doesn't matter much in a CF round compared to World Finals of Serious Competition, though.

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

Where is tag "square round"? (576 = 24*24)

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

How to solve D

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

This contest made me sad

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

How to solve Div2D?

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

    Process queries in offline mode. Hint: we don't care what queries of type "2 x" there were before the last query "1 p x" for every p. We just need to take the maximum of the x in the last "1 p x" query for a certain p and all x's from queries of type "2 x" that occurred later. Suffix maximums may be calculated easily in O(n).

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

      So Range Max segment tree was an overkill. :|

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

How to solve D?

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

    Segment tree.

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

      It can be solved without using Segment Tree

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

        OK,I know.

        But Segment tree is easier to think:D

        I used 10 minutes to solve this problem with it.

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

          I also tried to solve using segment tree but had some bug in my code :(

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

How to solve B :D

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

    l^2 — h^2 = 2hx. Find x. Because length of segment A-top of flower remains same.

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

      how you came up with this equation?

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

        Pythagorean theorem

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

        from the given image, we can see A^2 + L^2 = (H+A)^2

        then by simplifying the above equation A^2 + L^2 = H^2 + 2HA + A^2. then by eliminating A^2 from both sides L^2-H^2 = 2HA then A = (L^2-H^2) / 2H

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

    I think this is an isosceles triangle :3

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

      Which triangle is an isosceles?

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

        If you connect the line from two flowers like a drawing for you to create a triangle. Calling the three vertices of that triangle respectively A, B, C with B and C are respectively flowers. I noticed that triangle ABC is an isosceles triangle

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

          And how did you notice that?

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

    A^2 + L^2 = (H+A)^2

    Use binary search to find A. For me binsearch is simpler than separating A in that formular.

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

      Is it really that difficult in the end it is just ( L^2 — H ^ 2 ) / 2 * H

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

i think E can be solve by blossom algorithm,

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

    but i dont know how to implement in O(V sqrt E). Can you give me some link, please?

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

      There is no way to find the maximum matching in general graph in $$$O(V\sqrt{E})$$$. As far as I know, the complexity of the fastest algorithm for this task is $$$O(VE)$$$.

      This is my solution for E (I cannot implement it in time :( ):

      1. Find a maximal matching $$$M$$$ in the given graph (a matching such that no more edge can be added to $$$M$$$).
      2. If $$$|M| \geq n$$$, then print out $$$M$$$. If $$$M < n$$$, then create a set of vertices $$$S$$$ that has all vertices that are not in $$$M$$$.

      I can prove that $$$S$$$ is an independent set we need to find.

      Suppose that $$$S$$$ is not an independent set. That means there are two vertices $$$u, v \in S$$$ such that there is an edge $$$(u,v)$$$ in the given graph. However, that also means we can add $$$(u,v)$$$ to the matching $$$M$$$ (contradiction). Therefore, $$$S$$$ must be an independent set.

      It is easy to see that $$$|S| > 3n - 2|M| > 3n - 2n = n$$$, therefore $$$S$$$ is an independent set we need to find.

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

        awesome proof.

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

        My solution for 1C/2E is in $$$O(TV)$$$。

        First put all the points into a set.

        When you read an edge, if its 2 endpoints are all in the set, put the edge into a vector and delete the 2 endpoints.

        In the end, if the size of the vector >= n, we can puts "Matching".

        If the number of remaining points >= n, we can puts "IndSet". So it's $$$O(V+E)$$$

        per a query.
        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Very nice. I was trying to figure out something similar but I was too stupid and also there is an Edmonds blossom algorithm, so I ended up coding that...

        On the other hand, when I was not able to clearly see all these things during the contest I could have ended up coding something very similar, yet incorrect, which resulted in some tle's and wa's among submissions. When I checked them, they seemed to do something that you described, so I don't regret.

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

        As far as I know

        just use wiki ;)

        https://en.wikipedia.org/wiki/Matching_(graph_theory)#Maximum_matching

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

is div2 E is a coloring problem(vertice coloring and edge coloring)?

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

DP state for Div2 F?

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

    Yes. It's in $$$O\left(n^5\right)$$$. $$$f(x1,y1,x2,y2)$$$ mean the answer to the range $$$(x1,y1)$$$ to $$$(x2,y2)$$$.Use memorized search to maintain the answer.

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

      Can you please explain how O(n^5) is passing? If we directly calculate then it's 3*10^8 computations. The more complicated calculation would be — (50*(51)/2)^2 (states) * 2 * ~25 (dividing each rectangle into two rectangles, horizontally and vertically.

      This is easily crossing 10^7 computations and almost touching 10^8. Generally, 1 second means less than 10^7 computations, right? (Help me out with that please, could never get a proper idea)

      With reference to my submission — F

      On a side note, hot to make comments look pretty? I know there's bold and italics but for example, how to use superscript?

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

I was in despair until I found that $$$O(n^5)$$$ solution can pass 2F/1D.

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

Div1C: https://codeforces.net/contest/1148/problem/G

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

    How this two problems are connected?

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

      Hi sir may I know if the random solution in Div1 F will fst?

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

        There exist random solutions which will get OK.

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

          OK Thanks.

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

          Do you mean something provable?

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

            No, I mean that we don't know how to create tests against some randoms

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

              Waaaaaaat, even this shit? :/ 58013316

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

                Well, OK, I've just started wondering if it is simply correct... Any ideas anybody?

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

                  I try to use the same way as this guy, But I sometimes Get WrongAnser. So this solution is incorrect.

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

                  Sound reasoning

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

              0.5 to counter some determine but slow and still let random pass!

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

                The problem isn't the TL, you can pass with $$$100$$$ ms (58034608). If you want to avoid this kind of incident, then the best way is to not have F in the contest.

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

            I am wrong.

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

              Imo $$$(20~choose~10)$$$, but I'm not sure.

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

      The only one difference is that in one, you are asking to find matching, and in other, you have to find set with at least one edge from each node. These are quite similar things. In fact, solution of how to find matching is described in the editorial of Gold Experience.

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

        Gold Experience, you say?

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

        Ok, you are totally crazy, don't see a point in continuing this conversation

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

Div1C одна из лучших задач за последнее время, спасибо автору.

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

Will the random solution in Div1 F fst?

58029804

Hope it won't. :D

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

how to solve D, I wrote some stupid n^6 dp and thought it would pass, of course it did not pass

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

    Observation 1: An optimal solution exists by only painting squares

    Observation 2: An optimal solution exists such that no two painting regions intersect, otherwise we can merge them into a bigger square.

    Thus we can do a naive dp using submatrix as states, divide horizontally or vertically for transferring.

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

      Can you explain observation 1 a little bit please?

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

        If I paint a rectangle with size $$$w\times h(w>h)$$$, it costs $$$w$$$, if I paint $$$w\times w$$$ instead, it still costs $$$w$$$ and it won't be worse.

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

        If we paint a rectangle of size $$$n\times m$$$ where $$$n<m$$$, we can expand it to an $$$m\times m$$$ square which only makes the solution better.

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

          can you prove your observation using another argument like for a given construction can you provide a way to convert a rectangle submatrix to some subset of square submatrices while maintaining the same cost . i can't seem to prove both of your observations simultaneously using your argument , suppose i give you an optimal construction then i can choose larger side of a rectangle as a square and the total cost remains same and your observation1 is true but then we may have intersection between two regions and observation2 is not valid (I think we need to prove your observations in some other way ).

          Also you didn't use any of those observations in your code for div1D , main point was that we could divide horizantally or vertically a given submatrix , can you prove why this strategy gives optimal solution ?

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

            otherwise we can merge them into a bigger square.

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

              ohk i understand it now(skipped that part :p).

              can you prove the main part, why dividing horizantally/vertically while transferring is optimal.

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

                An optimal solution exists such that no two painting regions intersect Therefore it must be splittable.

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

                  nice, i was trying to draw some counter example's but seem's i can't avoid both a horizantal cut & vertical cut simultaneously (except the whole rectangle ) inside a rectangle , such a strong statement.

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

                  This conclusion is wrong, consider the following painting regions on a $$$9 \times 9$$$ board:

                  $$$\text{1 3 3 5}\\ \text{3 7 5 9}\\ \text{7 5 9 7}\\ \text{5 1 7 3}$$$

                  What you actually need is that if the optimal solution is not splittable, then the projections of the regions onto the longer side cover the longer side, so the cost is at least its length, which is easily achievable (just take the whole grid as a painting region).

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

    $$$f[x1][y1][x2][y2]$$$ denotes... Well, you know.

    When it is all white, it is $$$0$$$.

    $$$f[x1][y1][x2][y2]=\min(f[x1][y1][x2][i]+f[x1][i+1][x2][y2])$$$ (Split it vertically)

    (Split it horizonally too)

    And paint a square with length $$$\min(x2-x1+1,y2-y1+1)$$$, then split it to two smaller rectangles.

    It is $$$O(n^5)$$$ with small constant.

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

      What does "... Well, you know" mean?

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

        The minimum cost to paint the rectangle with left lower corner $$$(x1,y1)$$$ and right upper corner $$$(x2,y2)$$$ to all white.

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

      I think it should be max(x2-x1+1, y2-y1+1).

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

        Well, actually my solution is a little different to other solutions (including official solution). You mean using a square with length $$$\max(x2-x1+1,y2-y1+1)$$$ to paint all the rectangle white, while I mean using a square with length $$$\min(x2-x1+1,y2-y1+1)$$$ to paint only a part of the rectangle.

        The following picture describes my idea.

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

    got AC with n^6 dp (code). Can someone hack my solution?

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

how to solve div2 C?

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

    You can have at most 2^k distinct elements, where k is (8 * I / n).

    If there are m distinct elements in the sound file, you need to reduce d = m - 2^k elements to fit onto the disk.

    Let cnts be an array that:

    index: nth small element

    value: how many times it appears

    (We can use std::map to obtain such an array: counting with std::map, iterate over the map, collect its value part.)

    For i in [0..d], we change all the smallest i elements and the largest d - i elements, count how many element we changed, and the final answer is the smallest count. (That is, sum(cnts[1..i]) + sum(cnts[(m-(d-i)+1)..m])) (We can use prefix sum array to calculate the sum)

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

      you don't even need to use map to count, you can sort them and count number of elements each value. my_code

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

A is the hardest problem among ABCDE :(

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

    DSDSDASDSDDDS I CAN'T AGREE MORE.

    I wasted 40 minutes in total on A, misread it like two times and had some horrible bugs. On the contrary, I saw the ideas for B-E immediately.

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

    Got hacked on A :(

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

    maybe it's the hardest among ABCDEF :(

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

      My F failed, so I can't say that :( But it seems so.

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

    The task is natural and simple but the instruction is not written "smoothly", so hard to understand.

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -27 Vote: I do not like it

B is totally dump.

Maybe I will never write Um_nik contest anymore.

Now I am upset enough to give some bad words, but I just can't.

The last time: B is dump.

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

    Here you are..

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

      B is actually frustrated because they didn't explain the test cases properly

      not only I experienced this

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

    Maybe it's not the problem but it's you.

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

Wow, another implementationforces round, so cool (no)(2).

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

In Div1E if the grid was small enough, I believe it could be solved by bipartite matching(with the observation that it is always worth to choose an entire line or column). Is there a way to "normalize" the big bipartite graph and transform the task into flow problem or something similar?

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

    You can compress the coordinates to get a grid that is essentially 100 by 100. The observation is that only the boundaries of the rectangles matter.

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

Div1C and Div1E are so super standard, especially E

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

how to solve div2 c??

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

    First you can note that the position of numbers doesn't matter. So think of a set of numbers (multiset) instead of array. It's because when we select $$$[l, r]$$$ it will "influence" all numbers.

    So now we have to make all numbers in our set in range $$$[l, r]$$$. It means that when we select some $$$[l , r]$$$ all numbers that are outside this range will change.

    So our answer for selected $$$[l, r]$$$ is $$$ans = cnt[1] + cnt[2] + ... + cnt[l-1] + cnt[r+1] + cnt[r+2] ...$$$, where $$$cnt[i]$$$ count of number $$$i$$$

    Now let's think what we have to do in our problem :D

    $$$ourTotalMemoryUsed = n*ceil(log2(K))$$$, where $$$K$$$ — number of distinct elements

    $$$maxMemory = 8*I$$$

    $$$overallMemoryUsed \le maxMemory$$$ (overall memory should be less equal then max memory)

    $$$n*ceil(log2(needK)) \le 8*I$$$

    $$$ceil(log2(needK)) \le 8*I/n$$$

    $$$needK \le 2^{(8*I/n)}$$$

    That means that our result set should have less or equal then $$$2^{8*I/n}$$$ distinct elements.

    Now let's select some $$$l$$$. Now we have to select such maximum $$$r$$$ that number of distinct elements in that range will be less or equal then $$$needK$$$ and our answer for selected $$$[l, r]$$$ will be $$$n - (r - l + 1)$$$

    Why? Because elements outside this range will change.

    Now how can we calculate it? Iterate through all elements in our sorted array. It will be our $$$l$$$. Then using 2 pointers we can find max $$$r$$$, that number of distinct in range $$$[l,r]$$$ will be less or equal then $$$needK$$$

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

      Could you take a look into my solution, it is what you said but do not pass 10th test :(

      https://codeforces.net/contest/1199/submission/58049925

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

        Increase R before entering your for loop.

        Otherwise you add cnt[b[R]] twice. Once in while, next time in for loop.

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

          aijey can you please tell me why the position of element doesn't matter ?

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

            Any range you select, you should check all elements, whether they are in range, and change them if not.

            Example: 2 4 1 5 2 3 5. [3, 4]

            Checking a[1] = 2 -> changing...

            Checking a[2] = 4 -> in range(don't change)

            Checking a[3] = 1 -> changing...

            Checking a[4] = 5 -> changing...

            Checking a[5] = 2 -> changing...

            Checking a[6] = 3 -> in range

            Checking a[7] = 5 -> changing...

            So ans = 4. You can see, that any way you shuffle the array, the answer for [3,4] will be always 5

            UPD: a[5] isn't in range

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

              But can you please tell me why a[5] = 2 is in range . By the way thanks actually I misinterpreted the question .

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

                Oh, it's not. Sorry)

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

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

What was hacking test for Div2 C/Div1 A ?

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

    maybe 2^(I*8/n) is too big to exceed the range of int.

    (sorry, I made a mistake

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

    I wrote I=min(31,I),I=1<<I and I was hacked.Because 1<<31=-2147483648

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

When can I resubmit? I have almost solve. I want test my new code.

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

Messed up problem A itself. Can somebody explain the logic now?

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

    Iterate for whole array :

    Run two loops :

    for(int j=i-x;j<i && j>=0;j++)

    for(int j=i+1;j<=i+y && j<n;j++)

    if in any of them a[j]<a[i] than index i wont be answer else that index is answer and return that index.

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

How to solve Div2-C?

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

    From disk size and number of samples you calculate the available bits per sample. This determines the biggest difference from lowest to highest possible storagable value.

    Then you find among the input samples the biggest possible count of samples with a difference less than or equal to the above value.

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

      The problem statement is easy to misread. The number of bits needed is calculated based on the number of distinct values, not the range of the values. So you need to find the optimal range to clamp the values such that the number of distinct values after the clamp is small enough.

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

Can someone please explain an online solution for DIV2-D?

mango_lassi can u please share your approach?

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

    What I tried to do was sort all people on the basis of the last change of type 1, with that change.Start iteration from last 2nd type change, and maintain 2 pointers, 1 on people array(sorted by last change), and other on the array holding 2nd type of events, maintain a maximum variable and update the final value of in-range people with maximum of (current value of that person, largest of x till now) and decrease pointers, continue....

    Edit:: Sorry didn't read "online" in your comment.

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

    build a lazy propagation segment tree where the lazy values represent the value x in type 2 updates.

    A type 1 update would need to push down the lazy values from the root to the leaf, and then update the array value at the leaf. A type 2 update just sets the lazy value at the root. To push a lazy value of a node to its children, you update the lazy value of the children to the maximum of the node's lazy value and the child's lazy value, then set the node's lazy value to some garbage value which is at most 0.

    When querying for the value of one point, we push down the lazy values from the root to the leaf, and max the array value with the lazy value at the leaf.

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

How's that even possible that O(n(x+y)) solution does not pass A? 58001554

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

    It's (s — x) in the 2nd loop i think, buddy! :D

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

    You wrote in line

    $$$ for $$$ $$$($$$ $$$int$$$ $$$j$$$ $$$=$$$ $$$s$$$ $$$-$$$ $$$1$$$; $$$j$$$ $$$>=$$$ $$$j$$$ $$$-$$$ $$$x$$$ && $$$j$$$ $$$>=$$$ $$$0$$$ $$$;$$$ $$$--j)$$$ j >= j — x instead s — x

    I think its the error

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it

Any ideas why it's TLE xd? 58001816

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

    Maybe its because array V is not global

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

      I think passing an argument to a function shouldn't affect complexity

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

        If you send data without reference to function, the function will copy the value first. So complexity of each checking is $$$O(n)$$$. Sending reference as vector& and you will get AC. I think.

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

For Div. 2 D, anybody has ideas about what is the 4th test case? Please share it :D

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

Btw, F can't be solved in polynomial time for big integers.

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

If Um_nik in panel AND you use Java, Run Virtual Contest at same time.

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

Div. 2 C is a bad problem

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

@Um_nik: Out of curiosity, question about F: If there is no prime that divides at least n-2 numbers, is it true that if there exists a solution then solution trying out completely random assignments will find one?

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

    I don't know, tests were prepared by Burunduk1

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

    random assignments

    for me it's not obvious, what "random assignments" are

    i tried out "random shuffle + greedy assignments", on my tests it finds answer during first 100 tries.

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

      I meant simplest possible way, no greedy or whatever, just i-th number belongs to first group with prob 1/2 (all events independent)

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

        Wow =) i even could not imagine so simple solution.
        It gets WA 46 with cutting by TL=0.5 seconds

        WA 46

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

          But does this test satisfy the assumption that no prime divides at least n-2 numbers? Because my solution that got accepted in contest 1) does some weird mumbo-jumbo, 2) tries some random assignments satisfying some.constraints determined by first part. However if there is no prime dividing >=n-2 numbers then my first part does nothing and second part is trying simplest possible random assignments as I described (and it got accepted as I said). It seemed fine to me as 3-edges are far less limiting than 2-edges and I still can't have a lot of them, but I didn't have any formal proof and was curious whether I am right.

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

            does this test satisfy the assumption that no prime divides at least n-2 numbers?

            Hm... No. Moreover, it seems, none of tests, where random assignments fails, satisfies the assumption.

            You may investigate tests more precisely

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

How to apply Segment tree in problem D?

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

hackforces!

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

Div.2 C can be solved using binary search.

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

    Yes! Here is my code : https://codeforces.net/contest/1199/submission/58018073 Techniques used : Sorting,Prefix Sums, Binary Search. Feel free to ask the doubts !

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

      Could you please explain the work of this line of your code ? ans = min(ans,pre[i-m]+suf[i+1]);

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

        pre[x-1] is used to get the number of terms which are less than the term at x and suf[x+1] is used to get the number of terms which are more than x. Basically, I am calculating the number of element which are not in range [l:r] in constant time.

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

Find the bug in code. Spoiler in edit history :(

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

Can someone explain me how to use segment tree in problem D(div 2) please

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

Just out of curiosity, can I get a count of how many solutions failed system tests for Div2C/Div1A?

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

nobody:

pretests:

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

Somehow I didn't think $$$O(n^5)$$$ could fit the time limit for D and tried to come up with an $$$O(n^4)$$$ one. My idea is basically to only consider rectangle $$$(x_1, y_1, x_2, y_2)$$$ where $$$x_1 = 0$$$ or $$$y_1 = 0$$$. I don't know how to prove it formally though. Code

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

can we solve C by Binary search ?

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

    Yep! I solved it using binary search, first applying BS on the answer, which would be b/w 1 to cnt (cnt being the number of distinct numbers) and then another binary search nested in it to find the min number of changes needed to obtain that particular distinct element count. Here's a link to my solution div2C

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

Correct me if I am wrong,

But my Div2 D's solution passed the system test, without being right. Test Case:

input

4

1 2 3 4

2

2 1000

2 1

Output 1 2 3 4

Expected 1000 1000 1000 1000

Link to Code https://codeforces.net/contest/1199/submission/58024929

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

    Yeah, it is incorrect, mine gives 1000 1000 1000 1000. And i was expecting the pretests to be strong, jokes on me :P.

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

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

Auto comment: topic has been updated by Um_nik (previous revision, new revision, compare).

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

https://codeforces.net/contest/1199/submission/58037512 https://codeforces.net/contest/1199/submission/58025301 Two same solution one giving wrong answer and other being accepted.

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

    One of the submissions was during the contest and the other was after the contest. The test case (Test 109) which the first submission failed on was added after the contest as part of uphacking, but is not used to judge submissions in the contest.

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

Div2C: 

If there are exactly K distinct values in the array, then we need k=⌈log2K⌉ bits to store each value.

As they talking about bits, I thought the distinct values are continuous (that's how bits work right?) . Am I the only one who faced this confusion?

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

    Even the question talks about the range: 

    We choose two integers l≤r, and after that all intensity values are changed in the following way: if the intensity value is within the range [l;r], we don't change it. If it is less than l, we change it to l; if it is greater than r, we change it to r. You can see that we lose some low and some high intensities.

    I thought every number from l to r (both inclusive) are represented by one of the bits. So the distinct values are contiguous. Did anyone else feel it ambiguous?

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

      Um_nik can you please look into this? I felt the question statement was confusing.
      As it says about K distinct values, but then it says about a range [l, r]. So I thought we can represent values [l, r] (contiguous) using the 'k' bits. But it turns out that we can use 'k' bits for non-contiguous values as well.
      In that case why did they talk about a range [l, r] and had confused the statement?

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

        The range is necessary for the problem statement. If you can select arbitrary values to modify then you would greedily retain the K distinct values with the most occurrences.

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

      I thought the same thing. I should really read questions more carefully next time.

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

      If there are exactly K distinct values in the array, then we need k=⌈log2K⌉ bits to store each value.

      I was confused too. But after looking at it a second time, I think this means to compress with a dictionary.

      For example, if there are 3 different values 'A', 'D', 'K', and message M ['K', 'A', 'D'].

      'A' => 00

      'D' => 01

      'K' => 02

      M => [02, 00, 01]

      With a dictionary, values don't have to be continuous.

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

    No it just means that if you had distinct values a1, a2, a3, .... an then you can describe each of them with ceil(log2n) bits.

    Example: if you know that you are given values 11, 12, 15, 257 then you don't need 9 bits to hold 257. Instead of it you can mapping 11 to (00), 12 to (01), 15 to (10) and 257 to (11).

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

    I didn't completely understand the statment too.

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

Is there anyone like me who didn't understand the problem statement of C?

If you already got AC,then please share your idea.

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

2D/1B solution

Let request time be it's order number.

Let's keep two arrays: the first one will hold our values and the second one will hold the time for the last first type request (1 p x). Let's name them values and last_upd.

Iterate over the requests.

If it's first type request (1 p x), then values[p] = x; last_upd[p] = request_time;

If it's second type request (2 x), then save it as pair (request_time, x) in the array second_type_requests.

Right now there are the last values in the array values, which were changed by the first type requests. Let's find out which second type request can change this value. It goes without saying that the request_time of the second type request should be more than the request_time of the first type request. If such request is not alone, we should choose the one with the biggest value.

We've reduced our task to finding maximum on suffix of the array second_type_requests. We can find it fast using the suffix_max_array.

Time complexity is O(N + Q)

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

Hi. Can anyone point out any optimization to improve my solution? https://codeforces.net/problemset/submission/1199/58040359

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

    Fast I/O makes a huge difference. You can check my submission and see my comments marking the optimizations at the beginning. Include those lines at the beginning of all of your submissions (or use scanf/printf) and your programs should run considerably faster.

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

Can someone explain how to solve div1E? I realized that I need to somehow reduce the problem to flow, it is clear that you need to compress coordinate, but I'm apparently stupid and can't understand what kind of graph here you need to build.

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

    Because the cost function is min(h, w), you can assume that all your actions are of two types only: paint whole row in white or paint whole column in white. Than we can say, that every black cell needs to be painted either from the corresponding row, either from the corresponding column. Let's create a bipartite graph. One half will be for the x coordinates, another one for the y coordinates. First lets assume that we don't compress the coordinates. We will add a single edge from ith row to jth column for each cell (i, j) which is black. Now you need to find the minimum vertex cover of this graph, because at least one of row/column needs to be painted. When you compress coordinates, every vertex will correspond to the range of columns/rows, and because of it will have a weight equal to the length of this range. Finding the minimum weighted vertex cover can be deduced to finding minimum cut of the network, where you add edges from source to each vertex of the first half and add edges from each vertex of the second half to the sink with with the capacities equal to their weights, and keep the original edges of the bipartite graph with the infinite capacities.

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

    A similar version of this problem is "Given a $$$N \times N$$$ grid containing white and black cells. In each operation one can color all black cells in a row or a column white. Determine the minimum number of operations required to turn all black cells into white".

    The solution is to construct a bipartite graph of $$$N$$$ vertices on both sides, and for each black cells $$$(r, c)$$$ we connect the $$$r$$$-th vertex on the left side to the $$$c$$$-th vertex on the right side. The minimum vertex cover of the resulting bipartite graph is the answer since each black cells is destroyed by the operation corresponding to the vertex which covers that edge.

    As for Div1 E, a similar bipartite graph $$$G = (X, Y)$$$ can be constructed on the compressed coordinates. So the problem is to find the "minimum weighted vertex cover" on the graph, which is equivalent to the min-cut on the following flow graph:

    1. For each $$$x \in X$$$, connect $$$S \rightarrow x$$$ with capacity $$$w_x$$$.
    2. For each $$$y \in Y$$$, connect $$$y \rightarrow T$$$ with capacity $$$w_y$$$.
    3. For each edge $$$(x, y) \in G$$$, connect $$$x \rightarrow y$$$ with capacity $$$\infty$$$.

    See this article for detailed explanation.

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

Solution for Div2 D without using segment tree.

Observation:

  1. a later higher payoff will cancel all previous lower payoffs.

  2. a citizen's final balance is determined by the last change and the highest payoff after that.

We go through events in reverse.

Record a visited array for all citizen and the highest payoff.

On event 1 p x:

If the p-th citizen has been visited, then its balance has been changed later, pass.

else, mark it as visited, update its balance to max(highest_payoff, x)

On event 2 x:

update highest_payoff to max(highest_payoff, x)

It may be easier to understand by reading the code: 58038489

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

My submission
58042687 on Div1 C
and
58041401 on Div1 F
passed the system test.

Of course, they failed during the contest, but after I tried to do some voodoo programming, I finally managed to write some randomized sols that (I think) should not be passed, but they finally got accepted (almost TLE/WA).

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

An interesting thing, cf predictor says that cnnfls_csy should get 583 pts, whilst he got only 296. Why is there such a difference?

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

someone please recommend some other problems like Div2 D where we can get answer without using segment tree?

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

Weak pretest, random algorithm bypassed, flood of fst.

Good contest.

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

Is there an optional solution to solve Rectangle Painting 2 if cost is max(h, w) ?

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

FST

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

How to solve Div2-D without using segment tree?? (I tried to understand through comments but can't)

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

Can someone please help me on DIV2 problem C question. Let me know if my logic is correct:

first find critical k <= min(n, 2^((8*I)/n)). Then sort the given array, and convert the array to its freq array i.e. if original array is 1, 2, 2, 3, 3, 4: change it to 1, 2, 2, 1 (each element in this new array represents the frequency of distinct elements in original array). Now original task is to minimize the number of changed elements, that is now equivalent to finding k-subarray with maximum sum in new array (using sliding window method in linear time), and then return new array size — max sum found.

Am I missing something here? It is failing on 10th test case. Link to my soln:

https://codeforces.net/contest/1199/submission/58049910

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

    Your logic is correct, but there was a flaw in your computing the window sum. In maintaining the maximum seen so far, your code takes the max of the current window and the next one instead of updating the window sum. This could mean that sometimes you include elements more than once, and sometimes consider a group of non-contiguous elements.

    I've made a slight modification (here), and marked the place where I changed code for convenience :)

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

      Oh yes! So silly of me. Thank you so much for taking your time & debugging, and even writing down the correct code :). Much appreciated. Finally, submitted the correct code. ✌

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

I need editorial, please :(((((

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -37 Vote: I do not like it

Fuck D, E's author. Losing free point for E just because of min/max. They didn't even bold it.

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

    Once again please. You thought that we gave two exact same problems, you can't open your eyes, and it is my fault somehow?

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

    Afaik, if the problems were the same but with different constraints, they would be named D1 and D2 instead of D and E. Moreover, the author always mentions it before the round whether there is a problem with 2 subtasks.

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

    Turn out it’s not free point when you still need to be able to read, right?

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

    I agree that it should have been bolded. It's a small thing that would prevent many people from misreading.

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

    These problems have very small statements, how is it possible not to notice the difference? There are different examples and descriptions for them. Why don't people read the whole text before solving the problem? Isn't it their problem?

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

      fhgfhgfdgfbecueiyukcbsycuwcbuaipcbsdivdsnuwdilcgwyiulncsauciowh8vioer;vbudsivnwioeprnvisdosdc bywduiveybukbyvlsdnuiweciwopbh8pec9jaspch8vr8v9dsov7sdv8ogw78veg7v8erovhe7ovshd8v9s

      fhgfhgfdgfbecueiyukcbsycuwcbuaipcbsdivdsnuwdilcgwyiulncsauciowh8vioer;vbudsivnwioeprnvisdosdc bywduiveybukbyvlsdnuiweciwopbh8pec9jaspchBvr8v9dsov7sdv8ogw78veg7v8erovhe7ovshd8v9s

      These two strings are definitely shorter than these problems statements, how is it possible not to notice the difference?

      Of course two very similarly looking statements could bring the impression that they are the same and we need to fight that feeling for like 1-2 minutes before actually finding the significant difference, but we could have been saved from that by just either bolding min/max or writing a short note "the main difference is different cost function".

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

Some SegmentTree solution of Div2D shoule be hacked like this
https://codeforc.es/contest/1199/hacks/575652/test

why it passed system test?????

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

    Can you explain why it will break ST solutions

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

      I use SegmentTree by a method different from others.I maintain the interval minimum and the interval maximum and a tag which notes whether the interval has been modifyed.

      When it comes to Case 2 ,if the interval minimum >= x then return immediately , if the interval maximum < x then update tag[p] , else update its subintervals

      When it comes to my hack case it will update all the subintervals in a enquiry .This will make it TLE

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

    UPD: Hacking~

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

    I have no idea how others used ST solve this. I used a segment tree with lazy propagation. There is no case I can think of for which my solution will fail. Can you give a hack for my solution?

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

Weak system tests. A lot of accepted Div2 C solutions give incorrect results for

9 1
1 2 2 2 2 2 2 2 2
→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Getting TLE. Can anyone check which test case is taking up time or can possibly give wrong answer?

58060352 Thanks!

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

thanks to div1b's author. through this problem I found my segment tree is wrong, but it passed all the systests. what a bad contest

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

Div 1F : Why the time limit have to be 0.5s ? I was scared that the naive $$$O(n * \sqrt(10 ^ 9))$$$ factorization can't pass so I implemented Polard's Rho and it's got TLE.

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

    It's probably set that low to disallow us from factorizing all the numbers. :P

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

      But if I find all $$$O(40000 / log(40000))$$$ primes in range [1, 4000] then I can factorize all the numbers. My code : 58053947

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

        Hacked :>

        (It's so weird that a similar case wasn't in the systests.)

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

      SQUFOF still works: 58085119

      Edit: Some other part of the previous solution 58078132 has been hacked, but the fast factorization still stands.

      Edit2: Updated solution with better randomization.

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

        Looking at the submissions above, I now think that they set the 0.5s time limit because [reasons], and they didn't think how fast the factorization can be. (Maybe they wrote a naive $$$O(\sqrt{n})$$$ factorization only and called it a day, who knows.)

        Personally, I really dislike tasks like F (some number theory stuff, you have to invent some construction, it's really hard to create a good test against any dumb heuristic, and some uninsightful 20-liners pass the systests). Future problem setters, please don't be afraid to drop/modify a task if you feel it's nearly impossible to make nice tests for it.

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

        Yeah man, nice factorization, thank you; however, it's not enough to consider only 2-edges, sorry

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

    During the contest I implemented naive factorization and it was way too slow to pass (2.7s on my laptop which is significantly faster than cf). So I just ignored prime factors larger than 1000 xD. Seems like a completely foolish thing to do, but I actually had arguments why that should not change much performance of my code.

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

My algorithm idea for Div1A/Div2C seems not working. Can someone give me counterexamples or i'm missing something in my implementation?

  1. Number of distinct elements in answer must be K = 2^(8*I/n);
  2. Calculate number of distinct elements in original array, let it be cnt;
  3. Calculate frequencies of elements and sort in ascending order;
  4. Answer = sum of (cnt — K) minimum frequencies.

Code implementation 58059706 — Python and 58039964 — C++ both fails with WA on test 11.

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

    Your step 3 and 4 is wrong.

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

      Countertest:

      6 1

      2 1 1 4 4 3

      Your code gives 2 while correct answer is 3.

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

        How is the answer 3 ?

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

          You can choose interval [3; 4] then 2 -> 3, 1 -> 3, 1 -> 3. And transformed 3 elements. There is no interval for which you transform at most 2 elements and get at most 2 distinct values.

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

can someone please explain how to solve DIV1-F?

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

    Yes, someone definitely can explain it. Not me, I haven't tried the problems yet.

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

I didn't expect that a tester's or author's solution uses unordered_map...

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

    It was tester's bad solution. We changed its type to "Time limit exceeded or correct".

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

Why 400k numbers and 1s in Div1A?

Your solution is definitely O(n * log n) as well. Did you try to reject O(n * log^2 n), or what?

In my view, you only made it worse for those writing in Python/Java/Kotlin. My reasonable code in Kotlin with groupingBy() doesn't fit into 1s.

It would be really good if you thought about "Python etc." people when setting limits.

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

    I think that "Python etc." people don't deserve high TL. You can choose any language you want, Codeforces even supports C++. If you choose Python, you basically want to get TL.

    200k wasn't enough to cut out $$$O(n^{2})$$$ with pragmas in C++.

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

      Do you think it is still a bad idea to keep Python users in mind even when we are talking about beginner level problems (like div1A)?

      I also agree with "you can choose any language" part, but I think that discouraging beginners this way isn't beneficial for competitive programming community development and growth.

      I wonder if your point here is that we should care about it at all, or that div1A is already above the level at which we should care, or that it isn't actually beneficial for community (as everybody should realize the part about Python as early as possible)?

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

        I think that it is good when Python solutions are accepted for easier problems, but in no way it should be a decisive factor for choosing problems for the round

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

I submitted the following code for problem C(div 2) . The verdict provided was wrong answer on test case 2 while on my compiler it's returning the correct answer . Can anybody suggest anything? 58028994

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

    It seems like the issue was in your binary search. I modified it so the initial value for end was $$$n - 1 $$$ instead of $$$n$$$, and had it return a large value ($$$10^{9}$$$) if it hadn't returned anything during the search. You can see my changes marked by comments in the code.

    Without the modification to return $$$10^{9}$$$, it would not return anything, and without the modification of the initial value of 'end', it would access the vector distict out of bounds. I'm not sure what happened with your compiler, but your program may have just been lucky (or unlucky, in your case) and your compiler's C++ implementation allowed the function to return a value that led to the correct answer. Likely something with differing memory handling.

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

Tasks' ratings are not updated still.

→ Reply