ch_egor's blog

Codeforces Round #680 [Div.1 and Div. 2] (on the problems of Moscow Team Olympiad)
By ch_egor, 4 years ago, translation, In English

Hi everybody,

This Sunday there will be a XVIII Moscow Team Olympiad, high school students competition based in Moscow that is an elimination contest for All-Russian Team Olympiad. This contest is prepared by Moscow Olympiad Scientific Committee that you may know by Moscow Open Olympiad, Moscow Olympiad for Young Students and Metropolises Olympiad (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594, 622, 626, 657).

The round will be held at Nov/01/2020 14:05 (Moscow time) and will last for 2 hours. Each division will have 5-6 problems. The round will be held according to the Codeforces rules and will be rated for both divisions.

Problems are prepared by vintage_Vlad_Makeev, NiceClock, ismagilov.code, vintage_Vlad_Makeev, KiKoS, wrg0ababd, ch_egor, Roms, voidmax, DebNatkh, budalnik, Endagorion, craborac, 300iq, cdkrot, LHiC, vintage_Vlad_Makeev, V--o_o--V, grphil under my supervision with great help of GlebsHP, meshanya, Endagorion, Zlobober and Helen Andreeva.

Thanks to adedalic and KAN for the round coordination and verifying statement of original olympiad, meshanya and cdkrot for statement translation, and also thanks for MikeMirzayanov for systems codeforces and polygon, which was used to prepare problems of this olympiad.

Good luck everybody!

UPD1: Thanks to Um_nik, satashun, mraron, ustze, Karavaiev, KKiYeer for testing.

UPD2: Scoring distribution:

Div.1: 500 — 1000 — 1500 — 2000 — 3000

Div.2: 500 — 1000 — 1500 — 2000 — 2500

UPD3: Editorial

UPD4: Winners!

Div. 1:

  1. hos.lyric
  2. Benq
  3. ksun48
  4. Isonan
  5. jiangly

Div. 2:

  1. Algorithms_with_Shayan
  2. God_Of_Blunder
  3. jiazp
  4. c2020HXW
  5. Aishiteru.
Tags 680
  • Vote: I like it
  • +186
  • Vote: I do not like it

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

Friendly time for Chinese again!

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

Clashes with ABC 181 :(

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

This round directly clashes with Atcoder Beginner's round 181 which starts after 1 hour of the start of this round. I request authors to please check once.

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

Too early

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

    This round is based on onsite olympiad and they can't change time of start.

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

It's gonna be another Div.1.5-like Div.2 contest, and Div-0.5 like Div.1 contest

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

Most div1 people complain because there are few div1 rounds. Maybe proposing more rounds based on Olympiads can be an improvement. There are a lot of rounds based on Russian Olympiads, so I think that it can be extended to other nations.

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

    Do you really think this is few?

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

      It's an exception to the rule.
      In the average graph of div1 people, the number of dots (contests) is significantly lower where the rating is $$$\geq 2100$$$.

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

        Why is it a 'rule'? It's just the result of 'Div.2 only' exist but 'Div.1 only' doesn't. And because creating good harder problems usually takes more time than creating good easier problems, it would be inevitable there are fewer Div.1. If I can choose more lower-quality Div.1 or less higher-quality Div.1, I will choose the latter.

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

          But Olympiads from countries other than Russia also contain good problems, so why there are only Russian Olympiads on codeforces?

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

            That might be because codeforces is originally a Russian website, so the olympiad organisers may feel good if it is organised in a Russian platform too. Codeforces is growing as a more international platform, so we can see other countries' olympiads in the future maybe.

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

where are testers ???

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

    I think 20 authors is enough for testing

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

    Well, I'm one of the testers of this round. Seems that they haven't put the testers in the announcement yet.
    Upd: It’s updated now.

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

      Yes, I will add all testers after testing is over

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

The amount of red people in problemsetters scares me..

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

    As a red, they scare me too.

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

      I was literally searching for your comments to upvote them xD.

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

        Well you found them, Sherlock Holmes.

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

        They still haven't added the tester list, so I suppose there's no one to stop me from claiming I'm a tester for contribution farming purposes.

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

Is it Rated?

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

    Yes

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

    when I ask this question , this answer not mentioned in blog.

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

      When it is mentioned that it is a div2 / div1 round its anyways rated. It would be specified if it is some external contest. :)

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

There’re only 32 Legendary Grandmasters at all, and 4 of them took part in preparing the problems!

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

    That's the number of LGMs who competed in the last 6 months. There are inactive LGMs too.

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

      Yes, you are right, but then what is rating(all)?

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

        Rating (all) lists all users, but it lists all the active users before all the inactive users.

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

          Thanks a bunch, but this doesn't change how cool people were involved)

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

    actually 5 LGM's were involved(Um_nik as a tester)

    someone tell Codeforces Halloween was yesterday!!

    :|

    I don't know about you people but actually I prefer contests with harder problems because speed matters less :)

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

Will the round be rated? Also will it be codeforces rules or something like ACM ICPC?

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

    It is mentioned in the post that It is rated

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

      Clarifications to both my questions were added in bold after I posted my comment

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

moscow team olympiad aight imma skip this one

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

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

Note that the start time is unusual. :(

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

Clashes with OpenCup :( (apparently)

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

    Fortunately managed to solve all my problems, including first solution to Geo3D, in 2:47 and left teammates with optimizing code to last one :D

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

We will face one of the hardest contests. Let's see what happens.

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

hopefully we will see score distribution before the contest..

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

How will tie be resolved? Sorry I am new to cf so that's y asked

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

How can 20 authors propose 10 problems? Isn't it like one problem is completely written by a single writer?
Screenshot-2020-11-01-001628.png

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

    Seems like showing the name of movie makers before starting a horror movie!!

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

For those in US, note the clock change. On Nov 1st at 2 a.m. most US states will fall back one hour to 1 a.m.

Those who didn't know this happens... sounds stupid uh!? :)

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

    Thank you, I did not notice this! It seems the time zone adjustment on Codeforces is different from the one if you click the link to timeanddate.com

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

    Yeah, I was confused about this too.

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

Last time when I saw this many reds, I saw an accident.

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

Can't we have rounds in codeforces based on other olympiads? This would increase the rate of contests for both divisions and you would not need that much of co-ordination cause these problems appeared in Olympiads so it must be good. We only see rounds based on Russian Olympiads in codeforces unfortunately.

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

This competition is friendly for Chinese competitor!
Thanks ch_egor

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

Why so many authors this time??

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

All the best for everyone who are giving the contest !!!

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

Gap between D and E is huge.

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

    I'd say the gap between C (your E) and D is the huge one.

    I think the gap always seems biggest near the limit of your abilities.

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

Friendly time for Chinese again!

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

What is test case 2 of Div 2 C :(((

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

How do you do Div2E/Div1C? I think the problem reduces to "Find number of pairs of groups $$$G_1$$$ and $$$G_2$$$ such that $$$G_1 \cup G_2$$$ is bipartite", but I can't think of anything better than brute force.

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

    There are only $$$O(m)$$$ pairs $$$(G_1, G_2)$$$ such that $$$G_1$$$ and $$$G_2$$$ are bipartite but $$$G_1 \cup G_2$$$ might not be.

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

      Ohhhhh that's actually pretty obvious, thanks!

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

    Efficiently perform bipartite checks for each pair of groups that have an edge between them. You can look at the graph formed by edges within groups, find its components, throw away bipartite ones (along with whole groups), compress the 0/1 parts of remaining components into single vertices and on that graph, bipartite search takes O(number of edges between groups).

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

    checking if a graph is bipartite with DSU + restorable DSU

    the number of pairs you have to check is bounded by the number of edges, so for each pair, add in all of it's edges, check if it's bipartite, and then rollback.

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

    You can check if a graph is bipartite using a modification of the union-find data structure: for each vertex, we keep a bit indicating whether it has the same color as its parent in the union-find data structure. When inserting an edge between $$$u$$$ and $$$v$$$, if $$$u$$$ is already in the same component as $$$v$$$, we check if they have the same color. Otherwise, we merge the components of $$$u$$$ of $$$v$$$.

    Then we can simply check whether a pair $$$(G_1, G_2)$$$ is good by inserting the edges between $$$G_1$$$ and $$$G_2$$$ in that data structure, and we do a rollback after each check.

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

Please, why didn't you bold non-increasing and non-decreasing in D1B? Of course it's my fault, but I was solving wrong version for $$$40$$$ minutes.

Also, it's duplicate of SRM 781 Med

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

    Same here, but didn't see it till the very end :((

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

    I count myself very lucky for spotting it.

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

    I also misread the problem. I saw the sample test cases before solving the problem and couldn't understand why the answer is 12. After around 10 minutes, I finally realized that I misread the problem.

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

    Similarly, please bold "teams may have different sizes" in C. I made a mistake at first, and then spent lots of time wondering if it is even possible to do knapsack this fast.

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

    Same feelings.

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

    Same here, take my upvote. Spent ~30 minutes trying to solve the wrong version until I tried to run the samples.

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

    Nevermind. I FSTed it anyways!

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

    saw it right now, was solving the wrong version until the end :(

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

    Same here. BTW I thought the wrong version was a nice problem.

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

    Same, but I reread the problem after my $$$N^2$$$ gave WA on the sample ...

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

    Same here :(. I think the answer in that case was related to Catalan numbers. Can someone verify?

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

    Hello, I am here to complain about yet another problem statement again. After seeing editorial of Div1D, I was confused as to why $$$h=v$$$ was given, since drawing the following polyline works: $$$(0,1) -> (1,1) -> (1,-1) -> (-1,-1) -> (-1,1) -> (0,1)$$$. It isn't clarified in statement that they have to cyclically alternate, I think. Please, please, have more testers (who are perhaps non-native speakers) read and test the round so that such issues do not happen.

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

      I don't think that many people misunderstood the statement. Even if they had more testers, it's not certain that some of them would think that a closed alternating polyline may satisfy $$$h = v + 1$$$.

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

        I specifically asked for a clarification there because it's not given.

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

          It seems I didn't express myself clearly. I tried to say the probability of misunderstanding is low to begin with. It's just my speculation, though.

          Closed polylines don't really have a beginning nor an end.

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

            The statement says "One drew a closed polyline...". What isn't clear to me is if the alternating was just for the drawing, or for the actual diagram. I didn't get to asking clarifications as I was too busy misreading C, and thought that this problem would be hard (based on what I thought the problem was — might need to handle annoying cases). Turns out it was very clean.

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

              Oh, I see. Yeah if you think that way it's quite possible to be confused.

              Probably it would have been better if they simply gave two equal length arrays (it could ruin your results in some unexpected ways even if you interpreted the statement correctly).

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

How to solve div2E, I am struck for 1 hour and haven't got a single hint

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

this is first time i have ever solved 4 questions in div2,just hoping not to fail system test

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

In Div2D or Div1B , I was getting some double summation. For optimizing that i need to calculate summation of the form $$${n\choose n-k}$$$ + $$${n+1\choose n-k+1}$$$ + $$${n+2\choose n-k+2}$$$ .... $$${n+k\choose n}$$$ faster. Can some one tell O(1) formula for that (or some log(n) method will also work)

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

    Sort the array and then find the sum of the absolute difference of elements at index 0 and n,1 and n+1 and so on.... then simply multiply it by 2nCn.

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

      Can you please elaborate the multiply it by 2nCn part ? I guess you are trying to pair up element $$$i$$$ with elements at indices greater than or equal to $$$i+n$$$ and multiplying difference by number of times they can occur in two sequences such that they face each other. My approach was similar .

      Edit : Got it by comments below .

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

How do you find two subsets of equal sum fast enough in D?

I tried to do it with iterative NTTs, which should be $$$O(MN \log M \log N)$$$ (where $$$M = 1000$$$ is the maximum value) and then some loops to check which pair actually makes the target value, but this TLEd.

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

    bitset works better than FFT :)

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

    If you just want to find two subsets of equal sum, can't you just do normal knapsack with bitsets? (in O(NW/32) ish time?)

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

      Isn't that $$$O(N^2 W / 32)$$$?

      Too bad I didn't have time to try bitsets after getting TLE :(

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

    Something like this:

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

    I haven't got AC but I think this might work: you want to assign "+" and "-" to elements of the sets such that the set sums to 0. Shuffle the input and use a dp table $$$\mathrm{dp}[i][j]$$$ where $$$0 \le i \le n$$$ and $$$-B \le j \le B$$$ for sufficiently large $$$B$$$ (you can cut down a lot from $$$10^6$$$ here). Because the input is randomized, if there exists a solution there exists one where $$$j$$$ is not too large.

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

      I tried just adding the "+" segments from the largest one and then subtracting the "-" segments from the largest (absolute) one, but got WA...

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

      That won't work, what if we have $$$n-1$$$ copies of $$$1$$$ and one $$$n-1$$$. Then no matter the order we need $$$j$$$ at least $$$(n-1)/2$$$ or so.

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

        Huh? $$$j$$$ being around $$$n$$$ is totally fine, the complexity here is $$$O(nB)$$$.

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

how to solve div2C?

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

Div2D/1B is same as the topcoder problem I set.

Fun fact: You can perform a magic trick based on this problem in front of your friends too. :D

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

how to solve div2 C? O(n^1/2) is too slow...

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

    my solution passed pretests with $$$O(q^{1/2})$$$.

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

      Yeah what was you solution?

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

        The idea is that $$$ans$$$ will be largest divisor of $$$p$$$ for which the following holds: for at least one prime divisor $$$i$$$ of $$$q$$$, the exponent of $$$i$$$ in $$$ans$$$ will be less than that in $$$q$$$ (so that $$$q$$$ does not divide $$$ans$$$). My solution: link

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

          Dude yes I just read the editorial as well. The problem was that even if I have thought of this solution I discarded it immediately because I was like "Oh the prime factorization of q will take a lot of time" and now I just realized that no! it would not since I have to find the primes up until the sqrt(q).. smh. I will never ever become a master unless I sit down and solve all math tagged problems until 2000 rank.

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

          can you clarify what you mean by exponent of i?

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

            the power of a prime in prime-factorisation

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

Problem B: Am I the only one who thought that both $$$p$$$ and $$$q$$$ are sorted in the same order for 30 minutes?

EDIT: Just read https://codeforces.me/blog/entry/84198?#comment-717476. Seems like I am not the only one.

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

How the hell the answer to the example in D2E (D1C) is 3?

4 3 3
1 1 2 2
1 2
2 3
3 4

The number of possible combinations cnk(3, 2) = 3 and one combination is wrong, we cannot chose first and second group, because there is not way to split four students according to the rules
The answer should 2

Do I miss something?

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

How to solve DIV2D/DIV1B ? I thought ans is $$$\sum\limits_{i=1}^n a_i *(c_i - d_i)$$$

But I was not able to fill $$$c_i$$$ and $$$d_i$$$

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

Problem c division 2 why my solution gives TLE ? its O(LOG P) https://ideone.com/fDlClB

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

I have no idea what I missed in Div1B :|
I mean... I had multiple n^2 solutions, but nothing close enough.
For every element I tried to calculate how many times it will be with + and with -. (if a is sorted) a[i] will be +, as long as it is in the first i/2 elements if his array, and will be — otherwise.
That amounted to a sum of binomial coefficients that I didn't know how to reach a formula for.

By the amount of people who solved it, I assume the answer had a completely different approach...

Edit: just as an example, a[0] will always (i.e. 2n choose n times) be with a minus, and a[2*n-1] will always be with a plus.

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

    The trick is
    It does not matter how you split the array, the cost is always the same
    I noticed it accidentally while looking at different partitions

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

    No matter which arrangement you take, cost of partition remains the same. So just find the cost for an arrangement and multiply by total possible arrangements i.e., 2nCn.

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

      WitchOfTruth Yogi79 What do you mean by the cost of the partition is same ?

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

        Sum of all differences

        Let's say the array is 1 2 3 4 5 6

        1 2 3
6 5 4

        Total cost is 5 + 3 + 1 = 9

        1 3 5
6 4 2

        Total cost 5 + 1 + 3 = 9

        No matter how you swap elements, it will always be 9

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

          Wow! that's an amazing observation, just curious how did you come up with it ?It is very difficult to arrive at it analytically.

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

            I wrote down a couple of partitions for n = 3 and tried to figure out some non-quadratic formulae, then just observations

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

    Yup... I just noticed that even though I knew it was non-increasing and non-decreasing, I tried solving it for non-increasing and non-increasing....

    LOL

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

Can someone provide a testcase where this would fail ? It ofcourse seems the wrong solution looking at other peoples answers but I'd like to know why :/

https://codeforces.me/contest/1445/submission/97349096

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

    I believe you did not consider the case where q is prime (so then divs would be empty)

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

Is CF PREDICTOR not working ? I think it's showing wrong rating prediction .

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

    how can u say that u did't participated in the contest??

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

    Yeah I think it is broken because it has been showing wrong predictions for some time now. Maybe the ranking algorithm changed.

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

Can anyone tell me how C was solved because I can't wait for editorial. I bet it needed some witchcraft of math to get it. My thoughts were that if p % q != 0 you print p otherwise you know that p is divided by q and I could do nothing from there. I guess math is the reason I will never rank up. I guess I just need to solve all math problems until 2000 to be able to rank up from expert.

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

So many people got FST in D1C...

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

I was solving D1B in math all through the contest, but not until last five minutes did I find the pattern to solve the problem. I had no time to complete my code. It was the worst thing I met today...

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

    I was also trying to solve some double summation formula in fast way to solve this problem.

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

E is very close to what I do in my uni research. In short it is computing treedepth of a line graph of a tree. I was even reviewing one paper about problem which was related to that one, but I didn't inquire on how to do that specifically and papers I've found were too long too read. There is a fair share of papers tackling this problem and in fact it is possible to solve it in linear time as proved here https://sci-hub.se/10.1007/s004530010076

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

Pretests for Div1C are soooooooooooooooooooooo weak!!!!!!!!!!!!!!!!!!!!!!

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

I failed sys tests in DIV2 C because of precision issues in python!! urghh! So stupid of me writing

int(x/i)

instead of 

x//i
→ Reply
»
4 years ago, # |
  Vote: I like it +151 Vote: I do not like it

Thanks for strong pretests!

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

Tfw I FSTed on C because I read the input wrongly. How did I pass pretests :thinking:

(My code uses 0-indexed group numbers but I read group numbers in the input and forgot to subtract 1 from each of them oof)

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

Obviously Codeforces is not to blame but I discovered something I didn't really know before. Thought it might be useful for others.

So basically my approach was if the prime factorization of q exists in p such that for each prime factor and its respective power in q, there exists the same prime factor with >= power in p and this is true for all prime factors of q then I would have to try and set one power less of one of the prime factors of q in p and find the largest such number.

This obviously works in theory but what I didn't account for was that pow() in C++ takes only double as arguments, converts everything down to double due to which for larger bases and exponents which were still in long long reach, there was inaccuracy in the result. Implemented with custom pow() it works perfectly.

Very interesting, thought I'd share. Here are my two submissions :

97340883 97357774

PS: RIP Rating :/

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

    Everyone learns not to use pow() the hard way xD

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

Fastest Rating Updation : )

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

    But with wrong name color.

    (It seems that CodeForces predicted my future.)

    CF bug.png

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

      Same happened with me also but between Expert and Specialist

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

Hello,FST forces! :)

This round is successful,but...

We all passed during the contest time,but all failed in the system testing.

Although our wrong solutions were hacked in the end,I think this is still one of the shortcomings of this round — pretests are too weak, leading to the wrong solutions must rely on the data submitted by users.I think you can strengthen pretests the next time.

If we can get the WA result during the contest time,perhaps we will pass it.That's a pity for us.

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

    Wrong solutions are wrong because contestants don't test them properly, not because the pretests are weak. It is completely in the contestant's power to test more thoroughly, and thus not depend on the whims of fate, authors, pretests, or whatever else.

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

      Why even have pretests then?

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

        There are three test groups: samples, pretests, and final tests. Ideally:

        • Samples help to understand the problem statement.

        • Pretests catch obvious flaws in a solution.

        • Final tests let only the correct solutions pass.

        As you can see, each group has its distinct purpose.

        The formal rules regarding pretests can be found here, and the contest format overview with a section on pretests is here.

        I think the question is vague, and tried to not imply any specific interpretation, as it would most probably be wrong. If the answer turns out to be unsatisfactory, please be more specific.

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

          What can't be an obvious flaw?

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

Thanks for this great contest!

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

There are only one test in pretests of problem C except samples whose answer is not C(k,2). (I guess all of the tests in pretests are random graphs with fixed number of nodes and edges)

Thanks for strong pretests!

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

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!

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

Can someone tell what is the minimum constant rank someone should keep, to become expert?

Edit, I mean in Div 2

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

    since u asked minimum, i would say 1, be careful you might become red

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

      I don't know if you can become red, if you come 1 in Div2

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

    A consistent 1000 should be a low-to-mid expert, although I'm not very sure.

    However, this is probably pretty useless, since you can't just say "I will be rank 987 for round #X". Just aim to solve more problems and learn more about solving problems :)

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

    Just look in the standings table the rating changes of participants on that level.

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

    I'd say you need to be around top1500 in contests like that and around top2500 in isolated div2 (because there is higher rating threshold)

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

I usually dislike the usage of mod $$$998244353$$$ and favour $$$10^9+7$$$, but this time it was hilarious because input in B was up to $$$10^9$$$ and it allowed me to hack a solution which assumed the input is less than mod. Nice.

P. S. Thanks for cool pretests in C! Admire that.

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

please explain why my code is not passing all the test case.

My logic is — Both the array is already sorted so i reverse the array b and calculate the sum of a[1]+b[1] and a[n-1]+b[n-1]. This will give the possible range of sum of all corresponding indexs .so check the condition only these two will give the answer. Code link-https://ide.geeksforgeeks.org/aPAZIrNwTO

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

    Are you dumb? Can't you provide the link to your submission instead of copy pasting the whole code, can't you see how ugly it looks!

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

Are there somebody know the feature of test 29 on Div.1 C, which I FSTed on it.

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

Idk if it's normal or not but I'm specialist with 1300 rating

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

After this contest, my rating has increases by 159. And now my rating is 1328. But yet it shows that I am newbie. Has the rating system changed or it is a system problem?

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

Thanks for the nice problems!

My Div1C failed system test because I literally forgot to write a part of the solution. Surprisingly, pretests didn't catch that.

Contrary to some other expressed opinions, I think it's a Good Thing. It's good when the contests teach us to actually test our solutions, instead of being given an instant and omniscient check on a silver platter.

Solving problems, as a general skill, shouldn't depend on an oracle instantly telling you whether your solution is completely right, or has flaws. Some of the skill is to be able to gain confidence that you actually solved the problem, all by yourself.

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

Easy way to avoid a lot of C FSTs: just make a lot of small test cases and, since the graph in the input doesn't have to be connected, you can just merge them all into 1 test case.

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

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

Anyone knows why rating changes of this round are rolled back?

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

Dreams come true ;)

→ Reply