Блог пользователя ch_egor

Автор ch_egor, 3 года назад, По-русски

Всем привет!

В воскресенье в Москве пройдет XVIII Московская командная олимпиада — командное соревнование для школьников, проходящее в Москве как отборочное соревнование на ВКОШП. Над туром работала Московская методическая комиссия, известная вам также по Открытой олимпиаде школьников по программированию, Московской олимпиаде для 6-9 классов и олимпиаде Мегаполисов (раунды 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594, 622, 626, 657).

Раунд состоится в 01.11.2020 14:05 (Московское время) и продлится 2 часа. В каждом дивизионе будет предложено по 5-6 задач. Раунд будет проведён по правилам Codeforces, будет рейтинговым для обоих дивизионов.

Задачи соревнования подготовлены 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 под моим руководством, а также GlebsHP, meshanya, Endagorion, Zlobober и Андреевой Е. В.

Спасибо adedalic и KAN за координацию раунда и вычитку оригинальных задач МКОШП, meshanya и cdkrot за перевод условий, а так же MikeMirzayanov за системы codeforces и polygon, который использовался при подготовке задач этой олимпиады.

Всем удачи!

UPD1: Спасибо Um_nik, satashun, mraron, ustze, Karavaiev, KKiYeer за тестирование.

UPD2: Разбалловка:

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

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

UPD3: Разбор

UPD4: Победители!

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.
Теги 680
  • Проголосовать: нравится
  • +186
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +101 Проголосовать: не нравится

Friendly time for Chinese again!

»
3 года назад, # |
  Проголосовать: нравится +93 Проголосовать: не нравится

Clashes with ABC 181 :(

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

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.

»
3 года назад, # |
  Проголосовать: нравится -36 Проголосовать: не нравится

Too early

»
3 года назад, # |
  Проголосовать: нравится +56 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +67 Проголосовать: не нравится

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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    Do you really think this is few?

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +77 Проголосовать: не нравится

      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$$$.

      • »
        »
        »
        »
        3 года назад, # ^ |
        Rev. 2   Проголосовать: нравится -27 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится +17 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится +23 Проголосовать: не нравится

            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.

»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

where are testers ???

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +71 Проголосовать: не нравится

    I think 20 authors is enough for testing

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +57 Проголосовать: не нравится

    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.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +40 Проголосовать: не нравится

The amount of red people in problemsetters scares me..

»
3 года назад, # |
Rev. 5   Проголосовать: нравится -63 Проголосовать: не нравится

Is it Rated?

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +59 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +63 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +30 Проголосовать: не нравится

    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 :)

»
3 года назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится -49 Проголосовать: не нравится

moscow team olympiad aight imma skip this one

»
3 года назад, # |
  Проголосовать: нравится +47 Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Note that the start time is unusual. :(

»
3 года назад, # |
  Проголосовать: нравится +82 Проголосовать: не нравится

Clashes with OpenCup :( (apparently)

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

hopefully we will see score distribution before the contest..

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +40 Проголосовать: не нравится

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!? :)

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Yeah, I was confused about this too.

»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

notice the unusual time)

»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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.

»
3 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

This competition is friendly for Chinese competitor!
Thanks ch_egor

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why so many authors this time??

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Gap between D and E is huge.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +28 Проголосовать: не нравится

    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.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Friendly time for Chinese again!

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +23 Проголосовать: не нравится

    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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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).

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

    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.

»
3 года назад, # |
  Проголосовать: нравится +105 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I count myself very lucky for spotting it.

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +35 Проголосовать: не нравится

    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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    Same feelings.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +64 Проголосовать: не нравится

    Nevermind. I FSTed it anyways!

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 3   Проголосовать: нравится -18 Проголосовать: не нравится

      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$$$.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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.

            • »
              »
              »
              »
              »
              »
              »
              3 года назад, # ^ |
                Проголосовать: нравится +8 Проголосовать: не нравится

              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).

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится

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)

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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 .

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

    bitset works better than FFT :)

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?)

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    Something like this:

    code
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve div2C?

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +32 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yeah what was you solution?

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        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

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          can you clarify what you mean by exponent of i?

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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.com/blog/entry/84198?#comment-717476. Seems like I am not the only one.

»
3 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
3 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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$$$

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

        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

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
            Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.com/contest/1445/submission/97349096

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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.

»
3 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

So many people got FST in D1C...

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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...

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +46 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

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
»
3 года назад, # |
  Проголосовать: нравится +151 Проголосовать: не нравится

Thanks for strong pretests!

»
3 года назад, # |
  Проголосовать: нравится +52 Проголосовать: не нравится

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)

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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 :/

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Fastest Rating Updation : )

»
3 года назад, # |
Rev. 3   Проголосовать: нравится +21 Проголосовать: не нравится

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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +37 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +15 Проголосовать: не нравится

      Why even have pretests then?

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +14 Проголосовать: не нравится

        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.

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Thanks for this great contest!

»
3 года назад, # |
  Проголосовать: нравится +86 Проголосовать: не нравится

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!

»
3 года назад, # |
  Проголосовать: нравится +66 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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

Edit, I mean in Div 2

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +24 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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 :)

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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)

»
3 года назад, # |
Rev. 3   Проголосовать: нравится +51 Проголосовать: не нравится

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.

»
3 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
    Rev. 3   Проголосовать: нравится -10 Проголосовать: не нравится

    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!

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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?

»
3 года назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

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.

»
3 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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.

»
3 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Dreams come true ;)