Ormlis's blog

By Ormlis, history, 2 months ago, In English

Hello, Codeforces! We're glad to invite you to take part in Codeforces Round 980 (Div.1, Div. 2), which will start on Oct/20/2024 12:05 (Moscow time). Note the unusual time of the round. Each division will have 6 problems and 2 hours to solve them. The round will be held according to the Codeforces rules and will be rated for both divisions.

The problems were authored and prepared by Mangooste, Tikhon228, adepteXiao, Artyom123, sevlll777, yunetive29, glebustim, Endagorion, isaf27 guided by Ormlis and Helen Andreeva.

The round is based on XXII Moscow Team Olympiad, high school students competition based in Moscow that is an elimination contest for All-Russian Team Olympiad. Also thanks to the authors of the Olympiad whose problems were not included in the round : vaaven, TeaTime, pakhomovee, TheEvilBird, ch_egor.

We would like to thank specially:

Great thanks to the testers: Kapt, SomethingNew, k1sara, Pekiban, automac, theRealChainman, marks39, cosenza, pengin_2000, Killever, perchuts, Endagorion, maomao90.

As well as the teams testing the main Olympiad: (RP-1, kostylevGO, PBBx0), (AgafonovArtem, blyat), (daubi, talant, alexxela12345), (tem_shett, crazyilian, sevlll777), (katyaporay, Igorbunov, Dart-Xeyter), Kirill22, (rama798, FlameDragon, egneeS), (MOHOXPOM, Goshix, shevnin_d), teraqqq, (Siberian, Um_nik), (kova1, Aleks5d), (makcvim, Silver_Fox), polosatic.

UPD1: Score distribution:

Div.2: 500 — 1000 — 1250 — 1750 — 2250 — 3000

Div.1: 500 — 1000 — 1500 — 2250 — 2750 — 3000

UPD2: Due to the official competition source codes of other participants will not be available for two hours after the end of the round.

UPD3: Editorial

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

»
2 months ago, # |
  Vote: I like it +30 Vote: I do not like it

The trend of rounds based on other rounds.

»
2 months ago, # |
Rev. 4   Vote: I like it +39 Vote: I do not like it

Want to see tourist rating change.

»
2 months ago, # |
  Vote: I like it +49 Vote: I do not like it

As a tester I can guarantee that the contest consists of at least two problems.

»
2 months ago, # |
  Vote: I like it +9 Vote: I do not like it

As a tester I can confirm that there are problems.

»
2 months ago, # |
  Vote: I like it +36 Vote: I do not like it

As a tester,

Spoiler
»
2 months ago, # |
  Vote: I like it +2 Vote: I do not like it

First time seeing so many RED author's excited to participant.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

As a tester, as well as CEO of vulestamenkovic fan club, please join vulestamenkovic fan club.

»
2 months ago, # |
  Vote: I like it +108 Vote: I do not like it

As a tester I tested.

Linkedin version: I’d like to express my sincere gratitude for the opportunity to contribute to testing the recent Codeforces round. It was a great experience that allowed me to sharpen my problem-solving skills while supporting the quality of the contest. Being involved in such a meaningful project was both rewarding and insightful, and I truly appreciate the trust placed in me. I look forward to future opportunities to collaborate and contribute further. Thank you again!

»
2 months ago, # |
  Vote: I like it -15 Vote: I do not like it

The MX weekly contest coincides with the time of this contest, so I regret that I cannot participate in this contest.But I will Looking forward to your next contest!

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I have registered for tomorrow's div1, what if I lose rating points in this one and become expert, will I be able to give both div1 and div2 simultaneously tomorrow?

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

    Sadly you can confirm what'll happen now

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

      Yeah I'm now registered for both contests, will try giving both at once.

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

    Did you sacrifice points to find the answer to your question? I am genuinely interested in the answer too, please give an update.

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

      I didn't wanna sacrifice points but my stupid brain was like use segtree, sets, 8 cases for simple D problem and here we are

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

      Update it automatically unregistered me from div1 5 mins before the contest started.

»
2 months ago, # |
  Vote: I like it +21 Vote: I do not like it

watch me drop back to cm

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

    Ok so turns out I am not going to fall back to cm

»
2 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Clashes with CSP-J/S 2024 Simulation Test in luogu.

»
2 months ago, # |
  Vote: I like it +18 Vote: I do not like it

tourist is going to reach $$$4100+$$$ this time.

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Last early (time) round like this also followed Meta Hacker Cup.

Tonight
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Are boarding schools common in your country? Are they strict?

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

Why can't anyone in 1900-2099 register for Div.2 this time ?

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

    this is always the case for combined contests.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

12 contests since newbie, yet havent faced rating decrease. I hope it never comes.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    well done

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

    That's impressive.. But is this your alt account?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      Well few ppl i see are always crooked and cant tolerate others get what they couldnt, aint it ? Sad

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

        lol why are you getting so triggered ? i just asked if u were practicing in other accounts or something cuz it seemed cool that you reached that so fast.. but i didnt know u were this much arrogant.. anyway happy coding and just an advice : try to be a little bit nice

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

        lol

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          well, kid, prove !

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

            ok

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              But that is only for C, for A, B and D, it doesn't look like cheating.

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I use comments for Long codes for which i tend to forget variables. And for the rank, blame the ranking system, not me.

              • »
                »
                »
                »
                »
                »
                »
                »
                2 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Also the code in which i gave comments didnt get accepted till end as my logic was wrong (which i got after the contest)

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Also u arent someone to judge who is cheating or who is not ! mind your own business from next time !

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

First time seeing so many RED author's excited to participant.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what will be the score distribution for Div2?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

RED Alert!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please, show the score distribution.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Score distribution LOL

»
2 months ago, # |
  Vote: I like it -8 Vote: I do not like it

As a participant, the girl in Ormlis pfp is cute

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

nice score distribution

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wish to find a good problemset.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping for the best CF round!

»
2 months ago, # |
  Vote: I like it +16 Vote: I do not like it

having a downfall since way too long now, hoping to atleast get back to 900 today :(

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

2 hours speedrun!

»
2 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Hope orzdevinwang can reach Top5 in "Top rated" after the contest

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +141 Vote: I do not like it

    Lost rating sadly... But the process of my performance in this contest is so dramatic that I want to share it.

    • Solved A~D.
    • Tried to solve E. Got the idea and implemented it in thirty minutes, but the code got a wrong answer. There were thirty five minutes left.
    • I didn't know why my code is wrong, so I wrote a stress test. Sadly, the code didn't failed when the n is less than 10, but it failed when n is less than 20. Due to the large scale, I couldn't analyze such a big tree.
    • In the last few minutes of the contest, I just randomly modified my code. Surprisingly, when I did a change which was useless in my mind, my code worked! I submitted my code when it was only twenty seconds left. But it got a "wrong answer on test 1"! I checked it and found that I submitted to the problem F. It was only one second left, the contest ended.
    • After contest, I submitted the code I had submitted to F to E. It passed.
»
2 months ago, # |
  Vote: I like it -8 Vote: I do not like it

udgm is a cheater, you can see his submissions.

he used chat GPT to solve problems and remove comments manually.

Please Ban him

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

    How do you know this? Submissions aren't public and you haven't locked the one problem you solved.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      im talking about previous submissions

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

        I still don't see anything? Their previous submissions (at a quick glance) don't seem to show much GPT usage, plus they solved Maximum MEX first try (A problem which GPT o1 wasn't able to solve), yet didn't attempt E1 of that same contest, which o1 could solve

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i hope cheaters like udgm get banned sooon.

»
2 months ago, # |
  Vote: I like it +7 Vote: I do not like it

I have never hated a question as much as B

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

    It was a simple greedy problem!

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you help in finding the flaw in my logic for problem B, as i am unable to find the case where it could fail 287013577, Thankyou

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Solutions are locked. Instead, write your code here.

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

            You are not considering the value of the previous elements, which had reduced the value of all the elements by their values.

            Your updated code
            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              now i get as we are doing operation on all the slots we have to remove their values as well, thanyou

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you please explain how exactly you approached it? i had an idea of using each button once till it becomes zero and then not using that button again. but unfortunately it was wrong.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        My Code

        You might have forgotten to use prev if your approach is similar to mine.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I attempt to take all the cans from the slots (by doing slot * e.first) until the slot with the minimum count allows it, as long as it is not zero. As soon as a slot becomes zero, I add the frequency of that slot to my answer, as these actions can be ignored for the slots that are now empty. I then reduce the number of slots accordingly (slots -= e.second) and repeat this process until k is no longer greater than zero.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          why are we subtracting from prev?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I spend the whole contest on it (after I solved c and came back to it) and then the problem was just I used int instead of long long :)

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      means i was getting WA on pretest 9 cause i was using long long ?

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        no, because you are using int some where (that was the case for me)

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

The round is based

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is fft required in 1C?

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

    No: I have only KMP.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    FFT in 1C?

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

    EDIT: probably wrong, ignore

    I don't think so, given that you only really need to solve the problem for $$$k=2$$$ and $$$k=4$$$ (for all "normal" cases, $$$k=1$$$ works and other values of $$$k$$$ fail).

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The solution comes down to the following observation:

    In an SCC component $$$G$$$ for a directed graph, denote by $$$h[v]$$$ the distance from the (arbitrary) root of the vertext $$$v$$$ in the DFS tree of $$$G$$$. Then $$$k$$$ divides ALL cycle lengths iff: for each edge of the graph $$$u$$$ to $$$v$$$, we must have that $$$h[v] \equiv (h[u]+1)$$$ $$$mod k$$$

    We need the digraph to be an SCC for this lemma to hold because of edges across SCCs don't have to be part of cycles.

    With this observation, the problem is simple: we need to perform DFS over the 2 SCCs we are given. Now, if the 2 given SCCs dont form a cycle (all edges from one SCC are outgoing), then the answer is always YES, of course.

    Otherwise, we need to find the "shift" of the second DFS tree wrt the first mod k. This is just finding if two arrays are cyclically equivalent, which can be done by hashing easily.

»
2 months ago, # |
  Vote: I like it +51 Vote: I do not like it

Very strong examples. I'm amazed.

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

    Very strong examples. I'm amazed. Got -9 on 1C.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

OMG Jiangly will become 3900+ after this, can't believe it! Congratulations to jeroenodb as well for becoming LGM!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is Div2-D graph??

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes.

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

    nah it is like a difference array except for minimums

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

      can you explain the approach? I used dijkstra

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

        Sure, so basically we can set up our answer as $$$pre_i - skipped_i$$$ where $$$pre_i$$$ is the prefix sum up to $$$i$$$ and $$$skipped_i$$$ is how many we have skipped to get to the $$$i^{th}$$$ index. So now we just have to minimize $$$skipped_i$$$.

        To minimize $$$skipped_i$$$, it helps to see that the only possible answer for $$$i = 2$$$ is skipping $$$1$$$ (or $$$skipped_2 = \infty$$$ if we can't even reach $$$2$$$ from $$$1$$$). It follows that skipping $$$1$$$ lets us get to $$$[2, b_1]$$$ just by skipping $$$1$$$. So, in an "opening" difference array, we can place $$$a_i$$$ at index $$$2$$$ and in a "closing" difference array, we can place $$$a_i$$$ at $$$b_1 + 1$$$. This is assuming that $$$b_1 \ge 2$$$, because, otherwise, we don't have any skipping options for index $$$1$$$.

        In each index $$$i$$$, we can get the minimum skipped by processing the difference arrays (adding any ones in the opening $$$i$$$, and removing any ones in the closing $$$i$$$ to a SortedList), and we can just take the minimum in the SortedList. That is the minimum skipped at index $$$i$$$. After processing an index, we must add $$$a_i + skipped_i$$$ to the opening difference array at $$$i + 1$$$ and $$$a_i + skipped_i$$$ to the closing difference array at $$$b_i + 1$$$. Of course, you have to make sure that $$$b_i \ge i + 1$$$. I hope that this is a clear explanation.

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

          ohh i see, that makes sense. thank you

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Nice method, but for example if $$$ j < i $$$ and when adding $$$a_i + skipped_i$$$ to the array $$$[i+1, b_i + 1]$$$, we could duplicate $$$skipped_j$$$, if we had already added it to $$$[j + 1, b_j + 1]$$$ , and both arrays intersect, isn't it?

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Sorry but I'm not exactly sure what you're saying. The difference arrays make it so that each addition of $$$a_i + skipped_i$$$ is only two insertions.

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I can't believe you became purple before me

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

              Yes, I am not talking about complexity, the problem is the value added to the difference array.

              This example:

              10 20 30 3 3 3

              It can be proccessed like this :

              $$$i = 1$$$ : $$$pref_1 = 10$$$, $$$skipped_1 = 0$$$

              after we have add $$$a_1 + skipped_1 = 10$$$ to difference array $$$df = [0,10, 0 ,-10]$$$

              $$$i = 2$$$ : $$$pref_2 = 30$$$, $$$skipped_2 = 10$$$

              after we have add $$$a_2 + skipped_2 = 30$$$ to difference array $$$df = [0, 10, 30, -40]$$$

              Or for $$$i = 2$$$ we can add only $$$a_2$$$ to the difference array, because skipped_2 which is $$$a_1$$$ had been added to actual difference array, during $$$i = 1$$$.

              But by reading again, I think I misinterpreted. What are the insertion and the sorted list you talked about, and how you manage them with the difference array?

              • »
                »
                »
                »
                »
                »
                »
                »
                2 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Ohhh these things aren't "real" difference arrays. They are kind of like difference arrays but on minimums.

                For example, in your example $$$[10, 20, 30]$$$ $$$b = [3, 3, 3]$$$ the first step would be to process the element 10, and we see that, if we skip $$$10$$$, we can go to $$$2$$$ or $$$3$$$. So, to our opening difference array (which is a vec of vecs) at index $$$2$$$ (the vector at index $$$2$$$), we add $$$10$$$ and to our closing difference array at $$$b_1 + 1 = 4$$$, we add $$$10$$$ to the vector at index $$$4$$$.

                Then, in our iteration, when we reach $$$2$$$, we add the opening element $$$10$$$ to a SortedList (so we can easily access the minimum element) and at index $$$4$$$ we remove the $$$10$$$ from the SortedList. It might be the case that the difference arrays can store multiple values.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Ah thanks, got it.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i was so damn close to solving B, im literally annoyed

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

Thank you for the round, the problem div2C really good even I can't solve it in contest time. Will upsolve it later.

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

e problem is hash problem?

»
2 months ago, # |
  Vote: I like it +21 Vote: I do not like it

Div. 2 A-D were really good problems, however E and F were too hard and made the contest a speedforces.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how did u do d?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      dijkstra

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        can you please explain, how you use dijkstra?

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I got it. We treat all the problems as a node. We add a edge from Node i to Node i-1 of Weight 0 (As we can always do that problem and come back to the previous problems.)

          We also add edge from Node i to Node bi with the weight ai (As we can skip this problem and go to Node bi but with ai cost as we can't do this problem now).

          Now we can use Dijkstra's to find the minimum cost to reach all problems from the First problem and find the answer

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me how to solve Div2 C Concatenation of Arrays problem?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    just sort the arrays ascendingly based on the summation of their two elements

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why does it work? Could you explain a little bit

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        i think you would want to keep elements with high value to right and in this case you can take (sum of array as whole element) then sort it

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

      How you came up with that?

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I don't now it just felt logical but I have no prove for that

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 2   Vote: I like it +4 Vote: I do not like it

        Here's what I thought: If the sum of two numbers $$$(a,b)$$$ is greater than the sum of two numbers $$$(c,d)$$$, then it is necessary that at least one of the numbers from the first pair is greater than one of the numbers from the second pair. This way, the answer can never worsen. Rather, it can only improve. It kind of rested on ONE observation. Please share problems like these where the fate of the question lies on ONE observation.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have another approach. Simply Sort the vector<pair<int, int> pr(n) based on,

    1. whichever pair has minimum value of x = max(pr[i].first, pr[i].second) comes first.

    2. if some pairs have equal values of x, then whichever pair between them has a minimum value of y = min(pr[i].first, pr[i].second) comes first.

    3. if some pairs also have equal y value, then whichever pair has pr[i].first < pr[i].second comes first.

    My Code:
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hints on d? dp or greedy?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you may not believe me, but its neither :O

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

      Well, my solution is DP.

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

        can you please explain how? I though it was dp at first, but i solved with dijkstra in the end

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

          Took the state to be dp[i] = min cost needed to reach index i.

          So the final ans will be max( sum(a[j] {j = 0 to i}) — dp[i]) for all i in [0,n]

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I mean sure, i do that as well, but how do you actually find the costs without using dijkstra?

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

              Well for any node i you can go to all nodes between [i,b[i]] provided b[i]>i with a cost dp[i]+a[i].

              Now store these values in a multiset. When u get to a node j, dp[j] = min(multiset).

              Now update the multiset. (i.e) add dp[j]+b[j] if b[j]>j and remove all those dp values from multisets that lead you only till index j.

              Works because the top sorted order is from 1 to n

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
          Rev. 2   Vote: I like it +6 Vote: I do not like it

          i did dp + segment tree

          let U[i] be the min cost skipped to get to i -> res would be $$$prefA[i] - U[i]$$$

          from i -> you can go from 1 to B[i] for the cost of A[i] (you will be transported to B[i] where you can just slowly drop down)

          updates can be done with a segment tree

          then just calculate outwards from the start (U[i] <= U[i+1] is always true so it shouldnt wa)

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes please explain both the approaches, I feel like crying now ,that I couldn't solve this problem.

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

            If b[i] is less than i+1, you wont actually ever use that, so you can not care about that. So lets look at b[i] as directed edges from a[i] to b[i] whose costs are a[i]. We also have edges from each i to i-1, for all i>1. Those edges are obviously free. After this, you can just do dijkstra and you can find minimum cost to get to any i. Then the answer is just the maximum out of all a[i]-cost[i]

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Could you explain the last line again, Why are we considering it ?

              Should the answer be max{a[i] — cost[i]} or max{prefix_sum[i] — cost[i]} ?

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              can u pls share ur code

              • »
                »
                »
                »
                »
                »
                »
                »
                2 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Here is what I wrote based on his observation and submitted it. Got AC

                void solve() {
                	int n;
                	cin>>n;
                
                	vll arr(n);
                	vll b(n);
                	cin>>arr>>b;
                
                	vvpll adj(n);
                	fori{
                		if(i!=0){
                			adj[i].pb({i-1, 0});
                		}
                		adj[i].pb({b[i]-1, arr[i]});
                	}
                
                	vll d(n, inf);
                	dijk(adj, 0, d);
                
                	ll s = 0, ans = 0;
                	fori{
                		if(d[i]<inf){
                			s+=arr[i];
                			ans = max(ans, s-d[i]);
                		}
                	}
                
                	cout<<ans<<endl;
                }
                
            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Actually i think that i dont have to add free edges, because it is not optimal to go back (since the answer of j will be bigger than answer of i) (i<j)

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

                Thats wrong because it can be optimal to go to the back edges, because some of them might be able to push us even more forward. Sample 2 shows that as well. And also the answer of j is not always bigger than i, for j>i.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  I mean that instead of going back in the array, i can just maximize my answer with(pre[i] — skipped)

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  i dont understand what youre trying to say, but the back edges are necessary for dijkstra, maybe you could do it with another approach like that idk

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 4   Vote: I like it 0 Vote: I do not like it
        can you please help with my code , i tried doing topological sort and and then tried to find maximum score while traversing the topo array using prefix sum, getting wrong ans at test case 2 . 
        

        void test() { int n; cin >> n; vector<ll> a(n), b(n); for (auto &val : a) cin >> val; for (auto &val : b) cin >> val; vector<int> topo; set<int> se; for (int i = 1; i <= n; ++i) se.insert(i); auto dfs = y_combinator([&](auto self, int node) -> void { se.erase(node); auto it = se.lower_bound(node); if (it != se.begin()) self(*(--it)); it = se.upper_bound(b[node - 1]); if (it != se.begin()) self(*(--it)); topo.push_back(node); }); dfs(1); reverse(all(topo)); vector<ll> pref(n + 1, 0); for (int i = 1; i <= n; ++i) { pref[i] = pref[i - 1] + a[i - 1]; } ll ans = 0; ll skipped = 0; int mx = 0; se.clear(); for (int i = 1; i <= topo.size(); ++i) se.insert(i); for (int i = 1; i <= topo.size(); ++i) { int curr = topo[i - 1]; mx = max(curr, mx); se.erase(curr); auto it = se.upper_bound(b[curr - 1]); ans = max(ans, pref[mx] - skipped); if (it != se.begin()) { skipped += a[curr - 1]; } } cout << ans << endl; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin >> t; while (t-- > 0) { test(); } }
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I did dp.

»
2 months ago, # |
Rev. 2   Vote: I like it +52 Vote: I do not like it

Is the solution to Div 1C something along these lines?

  • For a graph where every cycle is divisible by $$$k$$$, you can number each node with a "remainder" by simple DFS from an arbitrary node.

  • Then the added edges must all connect a node with remainder $$$x$$$ in graph 1 to a node with remainder $$$(x + C) \mod k$$$ in graph 2 for some fixed $$$C$$$.

  • We can check this efficiently by:

    • Create a sorted list $$$L$$$ of remainders for each tuple of (graph, direction), we want to check if the above condition can be achieved between the sorted remainder lists for tuples (graph 1, outgoing) and (graph 2, incoming) and vice-versa.
    • Notice that if we convert this to a list of remainder differences under modulo (i.e., $$$[L_1 - L_0, L_2 - L_1, \ldots, L_{sz} - L_{sz - 1}, (L_0 - L_{sz} + k) \mod k]$$$), the above condition is equivalent to checking if one of these lists is a rotation of the other.
    • We can check this in $$$O(n)$$$ time using KMP on [list 1] seperator [list 2] [list 2] and seeing if there is match of size $$$|list 1|$$$.
  • Also handle the obvious edge cases (outgoing / incoming list sizes not equal, all outgoing / incoming for a graph, etc) separately.

I can't see any obvious flaw in this logic but I'm getting WA on test case 2 and unfortunately writing a test generator for stress testing seems tougher than the problem itself.

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

    you can also connect the 2nd graph back to the first graph (and it's not simply just (x+C)%k)

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

    You need one extra step: checking if the new cycles formed by the edges you added alsohave lengths divisible by $$$k$$$. For all edges $$$(a_\mathrm{in}, a_\mathrm{out})$$$ from graph 1 to graph 2 and $$$(b_\mathrm{in}, b_\mathrm{out})$$$ from graph 2 to graph 1, you need to check if $$$(a_\mathrm{out} - a_\mathrm{in}) + (b_\mathrm{out} - b_\mathrm{in}) + 2 \equiv 0 \pmod k$$$.

    In your solution, this corresponds to checking whether there are a pair of $$$C$$$'s for both "directions" of edges which have a difference of $$$- 2$$$ under modulo $$$k$$$.

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

      Oops, yeah I just realized my solution implicitly considers the edges in the opposite direction to have length "-1" instead of "1".

      Thanks for helping find the mistake.

»
2 months ago, # |
  Vote: I like it +24 Vote: I do not like it

Why the example of Div1 C is so weak.I don't have any time to generate a legal input in competition.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

sorting the pairs based on the maximum element worked for Div2C. It was intuitive, can someone please explain why it works?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wait what do you mean, i tried this in contest and it didn't work for me.

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

      sorting based on max, but if the max elements are equal, sort on min elements.

      if min and max both are equal, their position does not matter.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Suppose you put the array with the bigger maximum in front of the one with the smaller maximum, now you will create more inversions.

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

      Yeah i thought the same, but it was not mathematical enough to convince me during the contest.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got WA when I did it like that, then I sorted them based on the summations of the two elements no the maximum

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

    I sorted based on minimum first and then maximum only to get WA on pretest 4. Then, I reversed the order and got AC. Still not able to understand how the order of checking min/max is affecting the algorithm.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good contest. Great problems. Also how to solve D?

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

    You can look at it as a directed graph. Every back edge is free, and every edge going forwards costs you the points that the starting point is worth, then its a simple dijkstra

»
2 months ago, # |
  Vote: I like it -14 Vote: I do not like it

really cool contest, this is the first time i actually used dijkstra in a contest

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually 1B/2D can be solved without Dijkstra, but rather with DP optimized with BIT.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ahh i see, i have no idea how to use BIT sadly, so i couldnt really come up with that

»
2 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Problem A and B were inspiring, I did them fast tho. C is kinda interesting for me (and I love graphs), just taken a little bit of time to solve. Other problems are too hard for me. I might gain rating.

In conclusion it's not undenying that this round is a STUPID TRASH ROUND.

»
2 months ago, # |
Rev. 2   Vote: I like it +20 Vote: I do not like it

what's the proof for d1A since i literally just blind guessed the sol

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

    Consider pairs $$$(a,b)$$$ and $$$(x,y)$$$. If conditions $$$\min(a,b)\le \min(x,y)$$$ and $$$\max(a,b)\le \max(x,y)$$$ are both true, it's obvious that we should put the first pair before the second pair.

    If such condition doesn't meet then their relative position doesn't matter.

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

    let inv(A, B) be the number of inversions if position of pair A < position of pair B

    if A.first + A.second = B.first + B.second then inv(A, B) = inv(B, A).

    if A.first + A.second < B.first + B.second then inv(A, B) <= inv(B, A), because max(B) > max(A) or min(B) > min(A) holds

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Can someone explain, how to solve task C?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain where I am thinking wrong for problem b i try to take cans from each slot and as soon as i reach the minimum amount, i subtract all the slots having the min value from total number of available slots, Please help me in getting to know the flaw in my logic

Submission link: 287013577

»
2 months ago, # |
  Vote: I like it +14 Vote: I do not like it
»
2 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Div2 D is proof, I still don't know Dijkstra.

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

    exactly. it looked like graphs but i wasn't sure on then how to use that knowledge

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Solved it now using djikstra

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I read the tutorial but quite not understand why we are allowed to visit each problem as many times as we want when using dijkstra to find minimum. Could you help me explain it

»
2 months ago, # |
  Vote: I like it +115 Vote: I do not like it

I understand that it is the contestants' responsibility to write correct code, but what is the purpose of 1C samples?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    To test if some contestant is able to do stress testing.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The sample only needs to be able to clearly describe the meaning of the question.

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +24 Vote: I do not like it

    To be honest, I think the constraints on the input could've been made more friendly so that the 2nd and the 3rd sample cases become unnecessary, by guaranteeing the number of in/outgoing vertices to be matched and that there is at least one in/outgoing vertex on both graphs.

    Other than these trivial exceptions, the 1st sample was also way too simple that any wrong implemetation with several mistakes would still print YES, so the whole example barely tested anything with the core implementation.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am dumb

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to Solve Div 2 B?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I sorted the array and then used binary search to find the intervals where I could remove one can and how many cans I could remove on each interval

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The strategy is to click all buttons, then in cycle click all that were nonempty in the previous step.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it -82 Vote: I do not like it

    did you try asking yourself ...

    -is-this-fft-

    LOL!!!!

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If the sum of w is less than 200000, fft could solve the problem easily. However, the problem doesn't guarantee that. :(

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it -15 Vote: I do not like it

        BRO, my comment is a JOKE !!!!!!

        LOOK AT HIS NAME... HIS NAME is -is-this-fft- . So I made a pun, may be it is FFT.

        Nobody understands jokes these days.

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

          why are you yelling

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

            You are right my friend, Yelling is not FUN.

            My small brain is fried, Cos no-one gets PUN.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Whats the solution for 2C?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    create a vector to store each array as a pair of integers. Next, for each array, input its two elements and store them as pairs. Once all pairs are collected, sort them primarily by the first element and secondarily by the second element when the first elements are equal. Finally, concatenate the sorted pairs into a single array, ensuring the relative order minimizes inversions by keeping smaller elements before larger ones as much as possible...

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hint on D1/D (D2/F)?

I came up with some observations that a game can be added only if (wi * pi/(1-pi)) is greater than the summation of previous added weights, but couldn't use it in dp or greedy

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

    1/(1-pi)<=100, so the constraint from the statement implies that the sum of previous added weights is <=2e5. You can also use that formula to conclude that you should take at most 1/(1-pi) weights of a given pi. In total now you have 100+100/2+100/3+...=approximately 500 things you have to consider, and the sum of weights is <=2e5, so dp[i]=max probability with sum i works fast enough.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I used dijkstra for div2 D but I got TLE at TC24. Can someone please explain why my solution is this slow?

Submission link

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

    UPD2: Due to the official competition source codes of other participants will not be available for two hours after the end of the round.

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

    u can check that blog

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

    Are you maybe using max-heap instead of min? Thats how i got a tle at first

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I used min-heap. You can check my code below.

      My Code
      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        maybe emplace is slow? i used push

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

        oh and also why do you have >= in "(i > 0 && mn[i — 1] >= w)", should it not be just >? i think this is redundant and slows down your solution.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh, I see. Thanks for the help.

          I updated and resubmitted and it passed with 265 ms. I never knew such seemingly minor changes can affect the time this much.

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            anytime a node was reached and the weight before it was equal, it would essentialy make an entire line back to the start, so with a good enough test case that was probably n^2 sadly. but atleast your idea was correct, just a minor implementation issue

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

            Hello, could you let me know why you used vector mn = ap; I don't understand why If I use vector mn(n, INT_MAX); there, I get WA at tc 15

            Updated: I got it, I should use LONG LONG MAX

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        In your solution to find the minimum to reach the problem i, I understand that we are allowed to visit each problem as many times as we want, right? Could you explain why we are allowed to do that?

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

    Could you explain how to use dijkstra here? Thanks.

    updated: Got the idea, each index i can either submited(go to i-1) or skip(go to b[i])
    use heap to update value in correct order.

»
2 months ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

How to div2 E, I think it similar to https://atcoder.jp/contests/arc144/tasks/arc144_e, but i have no idea

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Consider the 2 graphs, for each node u can find its relative position%k, as its relative positions to each other mod k is guaranteed due to the the property of cycles length is divisible by k. We keep track of count of each position mod k separated by graph and also by input and output. What we want is for all the output of first graph to be 1 before the input of second graph. We can do this by checking equality for all rotations of k for the second graph and seeing if the 2 graphs sync together. Equality can be checked using rolling hash.

»
2 months ago, # |
  Vote: I like it -82 Vote: I do not like it

I have given the contest using my own personal two codeforce account so the submission I have made on both the accounts is same , so will I get penalty for the plagiarism over this?

»
2 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Can anyone tell where I'm missing? I am trying this approach to solve B but getting WA on 2

void solve() {
    ll n, k;
    cin >> n >> k;
    
    vll a(n);
    forn(i, n) cin >> a[i];
    
    sort(all(a));  
    
    ll can = 0;  
    ll cnt = 0;  
    ll mini = a[0];  
    ll zero = 0;  
    ll step = 0;  
 
    
    if (a[0] >= k) {
        cout << k << endl;
        return;
    }
 
   
    can = 0;
    cnt = 0;
 
    while (can < k) {
        
        if (can + (n - zero) * mini >= k) {
            cnt += (k - can); 
            break;
        }
 
       
        can += (n - zero) * mini;
        cnt += (n - zero) * mini; 
        
        step++;
        while (zero < n && a[zero] - step <= 0) {
            zero++;  
            cnt++;  
        }
 
      
        if (zero < n) {
            mini = a[zero] - step;
        }
    }
 
    cout << cnt << endl;
}
»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Nice problemset and Problem D was beatiful

»
2 months ago, # |
  Vote: I like it +28 Vote: I do not like it
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what's wrong with my idea of Div2 B?

I thought that — In the worst case, we always press the button with the smallest cans. So, I took the smallest can and removed all elements from it and the elements to right of it.

Code
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    your intuition is correct but see you press every button once so you will get (min_ele*n) cans evrytime you press button after then you will get no can so you learnt that that slot with min cans became empty and so on...

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, that's what I did in the implementation. What is the flaw here?

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Pressing a button with minimal cost may not necessarily result in greater profits, which is clearly not a problem of greed.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You don’t have to necessarily reduce a number to zero. You could just pass the other moves left to higher values. Think of it as pressing the buttons in a cyclic manner

»
2 months ago, # |
  Vote: I like it +22 Vote: I do not like it

UPD2: Due to the official competition source codes of other participants will not be available for two hours after the end of the round.

So why are we allowed to discuss solutions about the mirror contest on codeforces if the official contest isn't finished?

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Hello 2024

The Div.2 contest is numbered 2024......

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

congrats to jiangly

less than 100 points to T now

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

Maybe we would see a Tourist jiangly soon if he keep taking top 1.

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it -16 Vote: I do not like it

    …and tourist does not participate as well :)

    Edit: meant to say that if both of them compete, we may only have one Tourist ranked

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

This contest looks unusual to me only?

Here, people starting with rank around 950, till 5k have only solved ABC (some outliers with ABD), but then the ranking comes down to just who did it faster.

It seemed that C was just a hit and try to sort by max then submit, then sort by min and submit or sort by sum and submit, etc

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't know if this is correct, so I use several different ways to sort, and then calculate the inversion numbers, finally choose the least one.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This has to do with the round being a combined Div1+2 round, so the purple contestants are competing in Div1 rather than Div2 when it's a standalone Div2 round. Almost everyone (~1k contestants) solved AB in Div1 (equivalently CD in Div2), and if you count these in we have ~6k solving up to Div2C and ~2k solving up to Div2D, which is a more normal ratio (around 3:1) instead of the apparent 5:1 ratio.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That's some nice statistics. But my focus was more on that 5k people solved atleast C in Div-2 which seemed unusual to me and hints that C was quite easier than it should have been.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have no proof for my C, just do guessforces...

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

    I can't see your source, but most solutions should be based on this observation: In-pair order doesn't matter, so we can put them first small and then big.

    You can observe that you pair a to come before pair b only if (a1 < b1 and a2 <= b2), or (a1 <= b1 and a2 < b2).

    You can also observe that for pairs between a and b, they would always minimize or maintain inversions due to the swapping of a and b and for those outside a and b, nothing changes.

    Although not that useful for getting the optimal complexity, you can also see the problem as a topological sort problem, as the data permits a partial ordering and you can come up with different systems that give you the optimal solution.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      topo sort? Are u sure? It's just greedy.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah, I meant you can make your greedy based on the observation it's a topological sort problem. You can come up with different strategies to satisfy the sorting. Either you order by summing up the pair members, or you do it by comparing first elements then second elements, only important thing is that your strategy allows a partial ordering.

»
2 months ago, # |
  Vote: I like it +139 Vote: I do not like it

In my totally unbiased opinion, this was a good contest. Thanks for the problems!

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

    Agreed. Problems felt refreshing with tough but not impossible ideas. Haven't felt like this after the contest in a while. It even makes me want to upsolve the contest :)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please uphack my $$$O(k^2)$$$ solution for D1C
287064329

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

When will the editorial be out?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved the first question but got no rating, after by code being submitted successfully. Also in the previous contest yesterday i solved the first question successfully in first attempt but got rating of -10 , can anyone explain this..

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

    Your rating directly relates with your rank, and not the number of problems you solve. Today, your rank was exactly what is expected at your rating, hence no rating change. Yesterday, your rank corresponded to -10. Read more: CF Rating System

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Six months later, I'm still 1400.I want to become blue.

»
2 months ago, # |
  Vote: I like it +85 Vote: I do not like it

It has been almost 4 hours since the round ended. When will others' submissions be available?

»
2 months ago, # |
  Vote: I like it +71 Vote: I do not like it

sir Ormlis, we cannot access the details of our submissions and others' codes currently, please fix it

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

    Sorry, I thought it was available a long time ago. I pinged the coordinator.

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

So what's C+K+S in div1C? In Russian in could be interpreted as parity (Ч) + quantity (К) + sum (S), but it's different in English. And the solution seems to have nothing to di with parity... So what's it?

»
2 months ago, # |
  Vote: I like it +39 Vote: I do not like it

Ormlis when can we view solutions of others? :'(

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved div2D using DP + Segment Trees. The code is short and simple. Here is my submission if anyone is interested : 287094337

»
2 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Can anyone tell me why my Div. 2 C doesn't work? The idea: Pair (a,b) comes before (c,d) if at least two of these inequalities hold: a <= c, a <= d, b <= c, b <= d. Else, pair (c,d) comes before (a,b)

I made a comparator with this logic and sorted the pairs. Doesn't work

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Even I had a similar approach.

    In the comparator, I took 2 scenarios, one when Ai is on the left of Aj and then calculated the inversions caused by it, and another scenario when Aj is on the left of Ai. Then whichever is better in the 2 scenarios, I just took that.

    But this approach also gives WA on test 3.

    Can someone tell why this does'nt work?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      There is an edge case when number of inversions in both orders is equal. In such a case, putting the pair with the largest number on the right gets AC. I don't know why though

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i also used comparator ,my comparator funciton that gave error on test 2: _

    wrong comparator

    after adding a small if condition gave an accepted, dont know why ...

    modified comparator

    ~~~~~~~~~~~~~~~~~~~~~~~~~~~ can someone suggest a test case for better understanding.

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

    ig you have missed the a>=d check

    my comp function is :

    bool maxm(pair<int,int>&a,pair<int,int>&b){ int amax=max(a.first,a.second); int bmax=max(b.first,b.second); int amin=min(a.first,a.second); int bmin=min(b.first,b.second);

    if(amax>bmax)return false;
    else if(amax==bmax)
    {
        if(amin>bmin)return false;
        else return true;
    }else return true;

    }

    it works

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The main problem of it, is an absence of transitivity (look at the third clause here: https://mirror.codeforces.com/blog/entry/72525). This means that if your comparator tells that a < b and b < c it MUST tell that a < c.

    But with that instruction this is not allways true. For example: (6, 2) < (4, 3) (2 inequalities are true), (4, 3) < (5, 1) (2 inequalities are true), but (5, 1) < (6, 2) (3 inequalities are true).

    Without taking into account this condition (transitivity) the comparator isn't strict enough for c++, so the code can get any verdict, like RE or WA.

    But this is not the main problem. Even though it's correct, we (not a program) can not choose wich option is better.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In div2C probkem i wrote a program that runs in O(nlog(n) but stille got TLE. Am i wrong in my calculations or is it because python is too slow?287015824

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Still Not Able to see others Answer

»
2 months ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

Ahhh...please let me see the submissions and make peace with Div2/B.. :(

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

    bro :(

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    To solve the problem B, first sort the slots by the number of cans to prioritize slots with fewer cans, minimizing button presses. Then, start pressing buttons for each slot, collecting cans one by one. For each slot, calculate the maximum number of cans that can be collected from that slot and reduce the target number of cans k accordingly. Continue pressing buttons until you’ve collected at least k cans, keeping track of the total number of presses required. Stop once the required cans are collected and return the total number of button presses.

    Solution
»
2 months ago, # |
Rev. 2   Vote: I like it +20 Vote: I do not like it

Officially 10 hours without seeing others' solutions (well 8h after end of contest)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me to solve problems C. concatenation of arrays?

How should I approach?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sort the arrays by their sum

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Create a vector to store each array as a pair of integers. Next, for each array, input its two elements and store them as pairs. Once all pairs are collected, sort them primarily by the first element and secondarily by the second element when the first elements are equal. Finally, concatenate the sorted pairs into a single array, ensuring the relative order minimizes inversions by keeping smaller elements before larger ones as much as possible..

    Solution
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Brother, the code you've written and the logic that you say are different. The code is correct, but the logic that you've written in your comment is not

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        my bad this one is my updated code!!.. actually i just sorted the pairs based on the sum of their two elements, which effectively minimizes inversions by placing pairs with smaller sums first. This approach aligns with the goal of keeping smaller elements before larger ones, even though it doesn't use standard lexicographical order. so, the logic meets the problem's requirements and gives the correct output....

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can sort it by the sum of 1st and 2nd pair.

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

deleted

»
2 months ago, # |
  Vote: I like it +25 Vote: I do not like it

Seems like I was the only person in the top 800 to make the amusing move of "2023B - Skipping" problem B...

»
2 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Why did this get removed from the home page (at the time of writing this the topmost thing on the homepage is round 979)?

»
2 months ago, # |
  Vote: I like it +19 Vote: I do not like it

Just out of curiosity, how did you generate graphs required for Div1 C?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain why this solution is giving wrong ans ?

My logics

I will choose the cans in a cyclic order. So I calculated the number of cycles that I will take by doing ceilfunction(k/n) so which ever number is shorter than ceilfunction(n/k) only that will contribute to the extra button presses other than the k button presses. So what I did was I counted the number of numbers less than ceilfunction(k/n)(let's call it x) and then my answer was k+x.

link to my submission https://mirror.codeforces.com/contest/2024/submission/286933505

Thanks in advance for helping :)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

As a tester, I managed to scam D1D using a solution that possibly has exponential runtime. However, the authors did not kill it, and it still passes in 1671ms 287035100. Feel free to hack my solution :)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think "ragam_ganesh_babu" vp this contest with gpt and i am surprised that it finish div1 a,b and d,e!

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

    E is just copied from _l_l_.

    I doubt it's GPT for the other problems either. Maybe some easier ones are. More likely ragam_ganesh_babu is just one of these people who like to "win" VCs by copying others' code in the first 10 minutes.

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

      However, gpt solve Div1 B quickly and i solve it in almost 20 minutes:(

      Edit: Perhaps he issued instructions for GPT to rewrite a certain code, but I don't think it's necessary to continue discussing this clown

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

287139892 Can someone pls tell why does this TLE ? I just iterated on the vector containing unique elements from the array inside the predicate function...

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please help me understand the issue here:

Problem: 2024C - Concatenation of Arrays

Issue: Runtime Error on Test 4 with exit code: -1073741819 (STATUS_ACCESS_VIOLATION)

Submission:

  • 287166325 (Failed when using the comparator my_comparators for the sort function).
  • 287073493 (Accepted when using the comparator compp for the sort function).

Attaching code incase submission isn't accessible:

My Code

Thanks for the help!

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The compare function you use to sort the array should not be swappable. or to say cmp(a,b) and cmp(b,a) should not be TRUE at the same time

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any problems similar to Div.2 C? I want to get some practice on constructive algorithm problems using greedy and sorting like this. Really appreciate it if anyone could give me some advice.

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

Can we add the following test case for Div2C & rejudge all the solutions?

2
2
10 4
4 10
2
4 10
10 4

Mangooste

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    10 4 4 10 and 4 10 10 4 have 2 inversion... both ways will correct why do you want to rejudge?

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ahh yes!!, I just zoned out there, maybe I was trying to over engineer. Never mind

»
7 weeks ago, # |
Rev. 8   Vote: I like it 0 Vote: I do not like it

Hey I am being accused of leaking answer or coping internet from the internet, which is absolutely wrong. I haven't indulged myself in any sort of cheating ever and it's just an mistake please look into the matter and do the needful. If you need any proof I can present everything

»
7 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

Your solution 287001298 for the problem 2024C significantly coincides with solutions pvr04/286984233, redcapp_caos/287001298

That's so silly, I clearly wrote the code completely on my own. I don't even know who the other user is. While there is a lot of cheating going on it is embarrassing that people like me who are giving contest fairly are put under this test. I don't know where to comment and what to comment.

Could have been the use of custom sort for this message.

I hope you guys understand my concern and act accordingly.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    same bro same.. please upvote my comment too. they are just making these site worse, by not really catching the real culprits and making us look like that

»
7 weeks ago, # |
Rev. 3   Vote: I like it +17 Vote: I do not like it

MikeMirzayanov , Ormlis , Artyom123 , Mangooste , Tikhon228 , adepteXiao , Artyom123 , sevlll777 , yunetive29 , glebustim , Endagorion ,isaf27

I recently received a message regarding a similarity between my solution (ID: 286971111) and another user’s solution (Mradul2004, ID: 286933028) for problem 2024C. I want to clarify that I did not engage in any form of cheating, nor do I know the other person.Here’s my code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long 

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        vector<vector<int>> p;
        for(int i = 0; i < n; i++) {
            int x, y;
            cin >> x >> y;
            p.push_back({min(x, y), max(x, y), x, y});
        }
        sort(p.begin(), p.end());
        for(int i = 0; i < n; i++) {
            cout << p[i][2] << " " << p[i][3] << " ";
        }
        cout << endl;
    }
    return 0;
}

Given the simplicity of the code and logic for this problem, I believe there’s a high chance of similar approaches being used by different participants.

I independently developed this solution and did not share it with anyone. Please let me know if there is anything further I can provide to clarify this matter(I have not used any publicly available code).

Thank you,

»
7 weeks ago, # |
  Vote: I like it +1