Please read the new rule regarding the restriction on the use of AI tools. ×
Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

I_Love_Diar_Narumov's blog

Codeforces Round 973 (Div. 2)
By I_Love_Diar_Narumov, 10 days ago, translation, In English

Good Day Codeforces!

Me, Wansur and Chalishkan are happy to invite you to take part in Codeforces Round 973 (Div. 2), which starts on Sep/20/2024 17:35 (Moscow time). You will be given 6 problems and 2 hours to solve them. One problem is divided into two subtasks.

The round will be rated for all participants with a rating lower than 2100.

The problems were authored by me, Wansur and Chalishkan to solve and alter them.

We would like to thank:

Score Distribution: 500 — 750 — 1250 — 2000 — 2500 — (2000 + 2000)

Good luck!

UPD1: Congrats to the winners!

div. 2:

  1. EmmaXII

  2. hxano

  3. Muelsyse_sep006

  4. Hexagons

  5. Trumling_hasnotime

div. 1 + div. 2:

  1. maspy

  2. arvindf232

  3. Brovko

  4. aryanc403

  5. E869120

UPD2: The Editorial is out!

It is our team on EJOI 2024 4-th from left is me, 5-th from left is Wansur

We are also very glad that ICPC 2024 will be in Astana, and we wish all participants a good tour!

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

»
10 days ago, # |
  Vote: I like it +5 Vote: I do not like it

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

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

the Score Distribution shows only 1 problem divided into subtasks

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

    Thanks

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

      When does the contest Editorial will publish?

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

as a tester, can say that problems are interesting.GL for all participants

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

    worst c for me rather then preparing for tommorows exam wasted more then 1 and half hours on c

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

    For the first time, I solved three problems in div2. All that work was finally worth it!

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

      im happy for u. bro

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

        Can you help me take a look at the data for the second test point 1661 of the D problem on the Codeforces website? This is my solution 282151177

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

As a tester…

finally, can say it

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

I hope all participate honestly without ChatGPT. Good luck to all!

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

orz

→ Reply
»
10 days ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

I think there should be someone specially for AI Testing and he/she should be mentioned in the blog :)

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

I hope AI is not able to solve any of the problems

→ Reply
»
10 days ago, # |
  Vote: I like it +8 Vote: I do not like it
As a first time participant, i want to know...
→ Reply
»
10 days ago, # |
← Rev. 2   Vote: I like it +65 Vote: I do not like it

We would like to thank:

  • Thanks to my cat for touch.
  • Thanks to earth don't kill me.
  • Thanks to the mouse keyboard monitor power cord.
  • Thanks to catGPT trying to replace human.
  • Thanks to me though it did nothing

.. wait to list more

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

Kazakh contest cannot disappoint

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

rip cyan testing

→ Reply
»
10 days ago, # |
← Rev. 2   Vote: I like it +24 Vote: I do not like it

As a tester, this round is awesome, and I wish y'all good luck

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

Alga Kazakhstan

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

Hope that would be a lucky round for me.

I_Love_Diar_Narumov the best

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

Wansur will win ioi

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

As a participant, I_Love_Diar_Narumov and Wansur orz.

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

Hope I'll not lose my rating again QwQ

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

As someone who not a tester, wishing everyone best of luck !

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope the problems are thoroughly tested to be non standard. Thanks for making the round!

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I_Love_Diar_Narumov orz. Hope to get + on this round

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

I_Love_Diar_Narumov orz

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

As a setter, I wish good luck to participants.

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

Nice hair bro. Gll to all the participants.

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

As an EJOI participant, I can confrim that Wansur and I_Love_Diar_Narumov are cool

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

hope pupil will accept me in this round

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

it is required to thank the creators of the internet now

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

    everyone and their mother is creator of the internet these days

    → Reply
»
9 days ago, # |
  Vote: I like it -8 Vote: I do not like it

As a tester ..... I hope i can say it one day :(

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

Also make an option for unrated registration, please.

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

Return Specialist?

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

KAZAKHSTAAAAAAAAAAAN

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

gl

→ Reply
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to become pupil in a month?

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

    Don't ask silly questions which have already been answered several times.. That's how

    → Reply
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe a smooth ride until 1250, then a 750-point jump.

Maybe I should try D this time.

→ Reply
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

feels like its been a decade since last contest.

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

is it rated?

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

Wow, this is the big head of the milk dragon.

→ Reply
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

gang

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

Good luck everyone!

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

expecting a good problemset

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

I wish D is not GPT solvable

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

i dont wanna participate until Mike fix his site. I'm sad last div 4 failed and unrated

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

Technoblade never dies

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

i hope i will be lucky.

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

I actually believe that we are not completely powerless in addressing the issues with AI. For example, the following approach could probably work (though, of course, it requires cooperation from OpenAI and cannot completely prevent cheating with AI, but at least it offers an approximate direction): Before a particular contest, CodeForces provides the statements (possibly with editorials) of contest problems to OpenAI. As a result during the contest period, ChatGPT could forcibly reject any requests related to the problems if detected. Through this way, normal AI usage wouldn't be affected, while cheating with AI during the contest could be prevented to some extent. Of course, determining whether a user’s request is related to the problems (to clearly identify where the boundary is, without ambiguous judgement) would still be a challenging issue that needs further exploration, but given the current advancements in AI technology, it is obviously achievable through proper training.

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

    What is the need to provide problems WITH EDITORIAL ?? Why not just problems??

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

      If handled properly, only ChatGPT would be able to access the editorial, which means it would just terminate the conversation as long as it encounters something related to algorithms or logics appeared in the editorial. But as what I've said before, the specific boundary between related or not should be carefully restricted.

      → Reply
»
6 days ago, # |
  Vote: I like it +1 Vote: I do not like it
  • Help Dimash find out the password in no more than 2n operations; otherwise, Mansur will understand the trick and stop communicating with him.

No more than 2n operations, but its WA if Im doing exactly 2n operations.

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

    Please, can you give me link of submission?

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

    I wrote a code, which I thought would find the answer in 2n queries, but it was actually giving in 2n+1 queries, I guess you could be doing the same mistake...

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

why not reminding that there are some interactive problems? I guess you forgot it

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

question 3 is extremely confusing. I dont even get how to take the inputs.

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

I hate interactive problem.

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

One of my worst contests, carrot predicts -52 rating loss.

C was pretty annoying, I probably could have solved D if I spent all my time on it, but I ended up splitting my time after A and B on D and C which was a mistake.

:(

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

    I'm having the same mistake, I guess it's -6x for me and soon going back to newbie in a few contests...

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

D solution, please

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

    First, you should have a function $$$f(x, y)$$$ which determines if its possible to have an array $$$a$$$ such that $$$\min(a_1, a_2, \dots, a_n) = x$$$, and $$$\max(a_1, a_2, \dots, a_n) - \min(a_1, a_2, \dots, a_n) = y$$$.

    If you look at $$$f(x, y)$$$ for all values of $$$x, y$$$ from one of the sample, you will have this pattern:

    f =
00001111
00011111
00111111
00000000
00000000

    Now, you can binary search on the maximum value of $$$\min(a_1, a_2, \dots, a_n)$$$ by querying $$$f(i, 10^{12})$$$.

    Lastly, you binary search on the minimum value of $$$\max(a_1, a_2, \dots, a_n) - \min(a_1, a_2, \dots, a_n)$$$ by querying $$$f(\text{min val}, i)$$$.

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

      The double binary search is so ingenious but just too hard to observe, may I ask if there are some similar problems as advice?

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

      I think n time is possible for finding min and max

      For minimum, iterate from start to end while taking sum Min = min(Min,average till that point)

      Same for max only starting from the end to start

      Max = max(Max,average till given point)

      And then answer is max-min

      I will attempt my solution once system testing in done

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

        https://mirror.codeforces.com/contest/2013/submission/282108743

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

        Insane, how does this logic even work and how did you come up with it ? Would you explain please ?

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

          The idea is pretty simple, you have to minimize the value of ~~~~~ max(a1,a2,…,an)−min(a1,a2,…,an) ~~~~~ The obvious way to do this is, you select the maximum value to be as small as possible and the minimum value to be as large as possible. This will reduce the gap between max and min value and that would be the required solution. Now comes the part where you minimize the value of max, you can do a binary search on answer. Assume you hold a max value, now iterate over the array a, and check if you can achieve this max value in the array. The checking process goes as: if a[i] < (our assumption of max) then just continue as it is already smaller. But if a[i] > (our assumption) then you can simply reduce (a[i] — our assumption) from that and add this value to a[i + 1], and at last if you check a[n] and find it to be less than or equal to our assumption then return true, or else go for a larger assumption. Similar for the case of finding minimium.

          You can check my solution 282139332

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

            How can you guarantee that the case the maximum value to be as small as possible and the case minimum value to be as large as possible happen simultaneously?

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

              The max and min value will always be an element of the array a. I guess you have no confusion regarding this line. Now for an array (a), the max value will always be greater than or equal to the min value. And by any method if we can find the max value then you can obviously find the min value without affecting the max value. Because max and min values are independent of each other.

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

                I don't understand how we can guarantee that the min value do not affect the max value that we can minimize. Like, exist a proof on that? A proof that guarantee that if we modify the array values for reach a maximum minimum, do not affect the minimum maximum.

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

                I don't think it is necessarily true, that max and min will always be the elements of the array, Consider an array [12, 8], Here max and min will come out to be 10, neither one of them is in the array.

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

                  I didn't mean it in a sense that it will be an element of the given array. I meant that it will be part of the array itself. which needs or need not to be derived

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

            Your solution is very interesting. But like others pointed out, I also find it a little unintuitive that the operations you perform to attain the maximum element never worsen the minimum element you can achieve. Does anyone have a proof for this? Alternatively, consider the other solution which has two parameters that control both the max and min and prove the monotonicity of this (as dartvolley did above).

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

              Actually I don't have a formal proof for it rn. I'd get to it when I deduce it :(

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

      Hey, I think I might have found a small mistake in your comment. $$$f(x,y)$$$ follows the pattern you described if you define $$$x$$$ as $$$\min(a)$$$ and $$$y$$$ as $$$\max(a)$$$, not $$$\max(a)-\min(a)$$$.

      For those interested, here's a proof for the monotonicity of $$$f(x,y)$$$.

      Going by the above definition, $$$f(x,y)$$$ is $$$1$$$ when it is possible to transform $$$a$$$ to satisfy $$$x \le a_i \le y$$$ $$$\forall 1 \le i \le n$$$.

      I make the following two claims:

      1. If $$$f(x,y)$$$ is $$$0$$$, then $$$f(x+1,y)$$$ is also $$$0$$$. If any $$$a_i$$$ was $$$>y$$$, then both outputs would be $$$0$$$. So assume that $$$a_i \le y$$$, then $$$\min(a) < x$$$ directly implies that $$$\min(a) < x + 1$$$.

      2. If $$$f(x,y)$$$ is $$$0$$$, then $$$f(x,y-1)$$$ is also $$$0$$$. The proof for this is symmetric.

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

        In the first claim, can you check if you have got it right-

        1. if $$$f(x,y)=0$$$ and we assume that $$$a_{i} \leq y$$$, then $$$min(a) \geq x$$$ implies that $$$a_{i} \geq min(a) \geq x$$$ which gets us $$$x \leq a_{i} \leq y$$$ and hence $$$f(x,y) \neq 0$$$ contradiction.

        I tried to find the assumptions which would hold true. Can you check if I got them right —

        1. If $$$f(x,y)$$$ is $$$0$$$ , then $$$f(x+1,y)$$$ is also $$$0$$$. If any $$$a_{i}$$$ was $$$>y$$$, then both outputs would be $$$0$$$. So assume that $$$a_{i} \leq y$$$, then $$$f(x,y)=0$$$ and $$$a_{i} \leq 0$$$ implies $$$min(a) < x$$$, so $$$min(a) < x+1$$$ and hence $$$f(x+1,y)=0$$$ whenever $$$f(x,y)=0$$$.
        2. If $$$f(x,y)$$$ is $$$0$$$, then $$$f(x,y-1)$$$ is also zero.
        → Reply
»
6 days ago, # |
  Vote: I like it +3 Vote: I do not like it

for people who got ac after wrong answers: what's a corner case test case for F1?

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

    I am not sure what others did,

    I did something like BFS from both nodes simultaneously (with node 1 being first) Then if the longest chain that bob can reach is of length greater than or equal to that of alice, I print 'Alice', else 'Bob'. But this fails this test case

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

    In this test case, Bob would win, but my code outputs Alice.

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

      Alice moves to 4, Bob is forced to 7, Alice moves to 6, Bob is stuck -> Alice can win

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

        Sorry, I made a typo, can you check the testcase now.. (changed the edge 7-8 to 6-8)

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

        In this test case, Bob would win, but my code outputs Alice.

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

funny problem C. I really feel dumb actually

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

Did only one question, feeling demotivated, again.

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

I could only come up with a solution to solve C with 2n + 1 queries ugh. Couldn't come up with a way to get it to 2n in contest time. https://mirror.codeforces.com/contest/2013/submission/282098849

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

    I have another approach that would still generate 2n + 1 queries in worst case scenario. If you construct the correct suffix by taking up to 2 queries, then you figure out it is the end by 2 queries failing so it takes 2 * length_of_suffix + 2, then can solve for prefix in length_of_prefix queries, and it is required that 2 * length_of_suffix + 2 + length_of_prefix <= 2 * N. But if N = 5, and length_of_suffix = 4, and length_of_prefix = 1, then 4 * 2 + 2 + 1 = 11. Unless this is wrong somehow.

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

      it cannot happen i guess. for something like that to happen we may suppose that we're querying 1 first and 0 later. so in order to get 8 queries to get the suffix and then 2 to check if the suffix is done or not the suffix has to be nothing but $$$ 0000 $$$. and then the first character has to be 1 to get to 11 queries according to you. but since we're asking 1 first, we will start from $$$ i = 0 $$$ and not $$$ i = 1 $$$

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

      One query is sufficient for the first character because if "1" is not a substring, you don't need to check "0" — the string must be only "0"'s.

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

        Wow thanks I didn't see that, yeah that get's accepted with 2*n queries at most cause now it is 1 + 2 * (suffix_length — 1) + 2 + prefix_length = 3 + 2 * suffix_length — 2 + prefix_length = 2 * suffix_length + prefix_length + 1 <= 2 * N, even in the scenario that prefix_length = 1. If prefix_length = 0, then suffix_length = N and 2 * (N — 1) + 1 = 2 * N — 1 <= 2 * N https://mirror.codeforces.com/contest/2013/submission/282136094 I just had to add this line of code to get accepted for adding first character. if (ask(s + '0')) { s += '0'; } else { s += '1'; }

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

Was D really that easy?

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

Buffed versions of problem C: here and here.

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

I would love to learn the intuition behind problem C. I tried to build a solution based on previous guess information but it became confusing to combine all this information into an educated guesses.

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

    first check if there is a '0' in the string. if there isnt, then its obviously just n 1s. so lets assume there is a 0. then we can just start guessing what is to the left of the zero and what is to the right of the zero. check out my submission for details, i think its pretty straightforward

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

      pretty straightforward solution bro, thanks. How did you got that intuition to go on both sides of "0" ?? Because I was doing that both in single loop and if I found the end of string then setting a flag and doing for left side of string.

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

Good contest, expecting to reach Pupil.

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

    You've done 5 contests. In the first four you managed to solve only problem A. In this contest you managed to "solve" four questions and rank in the top 1000...

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

      You guys only observed that I solved just one problem in my last four contests, but you didn't notice that the time difference between this contest and the previous one is approximately a year. During that period, I solved around 1,000 problems.

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

You guys didn't mentioned for interactive why :(

Its my fault also I should have solved B from my first thought only I fcked it up due to overthinking

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

Was E intended to be greedy (pick the smallest number first, then repeatedly pick the next number which will minimise prefix GCD until prefix GCD = array GCD)? Or is that solution hackable?

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

    Than correct :(

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

    I also solved it that way.

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

    bruh how did i not think about this

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

    I wrote a DP solution in order to avoid greedy solutions which can not be proved. Here is my submission.

    → Reply
    • »
      »
      »
      41 hour(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hi, I have tried reading your submission, but I am not able to fully understand what is happening here. Can you please explain the approach for this solution?

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

    I also did that without proving XD

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

    This is correct.

    For example, let the optimal solution be b1, b2, ..., bi, ..., bn where bi is the minimum. Then consider bi, b1, b2, ..., b_(i-1), b_(i+1), ..., bn. Note that gcd after b_(i+1) is the same so we can ignore the sum of that part. Then if b1 > bi, then we have gcd(bi, b1) <= b1 — bi since gcd(bi, b1)=gcd(bi, b1-bi). Hence in our modified solution, the gcd sequence look like bi, <= b1 — bi, <= gcd(b1, b2), <= gcd(b1, b2, b3), ... and the original look like b1, gcd(b1, b2), gcd(b1, b2, b3) It is clear that sum of our modified sequence is better so taking minimum as first is optimal.

    For the recursive part we simply reduce the problem by taking gcd(bi, -) with the rest of the numbers. It is clear that this correspond to the subproblem of the sum of the rest of the gcd sequence and the sum is the same.

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

how to solve D or why my code D Runtime Error ? Thank 282102762

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

    Runtime error may be caused by division by zero，if nn is 2

    nn -= 2;
		
int xx = ss / nn;
int yy = ss / nn + (ss%nn?1:0);
    → Reply
»
6 days ago, # |
  Vote: I like it +10 Vote: I do not like it

Could solve only 1 in my 1st contest. But still, eagerly waiting for the editorial.

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

Problem C is nice, I faced the same problem at OII 2022 but 2*n queries were enough to get only 40 points. (https://training.olinfo.it/#/task/oii_dna/statement)

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

Is there something wrong with my logic for problem D:

Lets use ternary search for lower bound t1 to find minimum (t2-t1) where t2 is optimal upper bound for given t1. It's not hard to show that declared function is convex.

For each t1 lets use binary search to find minimal t2 so that you can readjust array between t2 and t1

For each (t1,t2) we can check if we can fit array into [t1, t2] going right to left one time.

Complexity should be O(log(Max)^2*ArraySize) which should be ok for given values. But for some reason I got Time Limit Exception. Is there flaw in the logic, or I just make a mess with terrible constant? Submission

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

    i just used a simple stack algo for D lmao

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

    In fact, it can be proved that ternary search for lower_bound is unnecessary. Only binary search or O(n) algorithm is OK for finding lower_bound. I can prove that as the lower_bound increases, the optimal upper_bound does not increase. So let sum[i] be the partial sum of a[i], then the lower_bound SHOULD be min(sum[i] / i). After that, we can binary search for upper_bound and it works.

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

    Same approach. I don't know why this fails, Let me know if you encounter a test case where your solution failed.

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

what's edge case in pretest 2 for F1

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

finally for the first time i am into 5000 ranks....... long way to go

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

How to solve B?

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

    (sum of the first n-2 elements) + (the n-th element) — (the n-1st element)

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

      Why last second element os goven so much importance?

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

        well you know that the second to last element has to fight the last element. and you also know that the last element will be the last one standing. so your goal is to reduce the 2nd to last element as much as possible before they fight. you do that by making him fight all the ones before him

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

          Upvoted!

          Thank you for the explanation.Understood!

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

Saw my first ever interactive problem, panicked, but eventually did it when around 3 minutes were left. Feels good.

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

accumulate(a.begin(), a.end(), 0L) - 2 * a[n - 2] why this not working for B

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

    It should be 0LL for long long

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

      thanks bro, crazy how using java at work changed my reflexes from 0LL to 0L

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

For D, I tried to find the minimum and find the maximum using binary search on difference. Looking at others' solutions, many have computed min and used same idea to compute max by going in reverse. However, I got WA upon doing this. This is the relevant of calculating the min in the array. What am I missing:

    auto ceil_div = [](long long x, long long y) -> long long { 
        return x / y + (x % y > 0);
    };

    auto get_min = [&]() {
        long long mn = a[0], excess = 0;
        for (int i = 1; i < n; ++i) {
            if (a[i] < mn) {
                if (a[i] + excess >= mn) {
                    excess -= mn - a[i];
                } else {
                    long long steps = ceil_div(mn - a[i], i + 1);
                    mn -= steps;
                    excess += a[i] + steps * i - mn + i * steps;
                }
            } else {
                excess += a[i] - mn;
            }
        }
        return mn;
    };
→ Reply
  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I suppose the mistake I made was not using up excess when a[i] + excess is not enough to get to mn. I'll just try to resubmit once the task is available for practice.

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

I got D in the last 5 minutes :D, specialist woohoo!

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

It's interesting that most of the people seem to have used binary search for D. I actually solved it by realizing that the optimal array in the end can be made non-decreasing and this way the min_val in the end is just the minimum over all floor(sum[0..i]/i) and max_val is the maximum over all ceil(sum[n-i..n]/i). https://mirror.codeforces.com/contest/2013/submission/282089570.

Not sure if this was intended or I will get a WA in system tests

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

    Same but I can't prove if both the minima and maxima can occur simultaneously. Hoping not to get FST.

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

    Yeah, I think my idea was similar to try to make array non-decreasing. I think floor(sum[0..I]/i) is certainly elegant and I saw this in other solutions too. I tried to do this more mechanically as I could not convince myself that the simple version will work.

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

    I had a similar idea for the minimum, but I could not work out quite what it would equate to for the maximum. I ended up finding the minimum in a similar way to that, and then binary searching for the maximum after that. Good find on your solution.

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

    i just reconstruct the whole array using stack lmao

    i noticed that if the average of a prefix $$$k$$$ is higher than some future prefix $$$l > k$$$, then using the average of the prefix $$$l$$$ is better. otherwise, the prefix cannot be changed. which means, i can separate it into several intervals using stack.

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

    Seems correct to me. I used same logic for max, and binary searched min. Feeling my binary search is essentially the same to your min calculation.

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

      we can calculate the min and max separately. but can we prove that both such max and min can occur at once?

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

        the min will in some prefix and max will be a disjoint suffix (since you can always move values backwards), so shouldn't be any conflicts between the min and max

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

          What exactly does it mean that you can always move values backwards?

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

    I understand why it is guaranteed min_val <= min(floor(sum[0..i]/i)), but why must they be equal at optimal(max-min)? What if this value of min_val makes us have some bad max_val?

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

skip PC and doing PD then failed :(

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

About last 20 min, I was unable to enter in the codeforces. Response was: Verifying you are human, This may take a few second.. Why this problem ? My internet connection was ok. At last i reached m1.codeforce, there i was able to submit,, but no problem was shown.

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

How to prove the greedy solution of E?

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

    Let $$$A$$$ be the smallest possible gcd with the current prefix gcd, and let $$$B$$$ be the optimal one, with $$$A < B$$$. Then, if we take $$$A$$$, then $$$B$$$ and continue in the same way as in the optimal case, the result will not be worse, since $$$A + gcd(A, B) \le B$$$.

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

      Just in case it's not obvious where $$$A + \gcd(A,B) \leqslant B$$$ comes from, note that $$$\gcd(A,B) \mid A$$$ and $$$\gcd(A,B) \mid B$$$ which means $$$\gcd(A,B) \mid (B-A)$$$ since we have $$$A < B$$$ and a divisor of a positive integer must necessarily be $$$\leqslant$$$ than that integer, so we have $$$\gcd(A,B) \leqslant B-A \implies A + \gcd(A,B) \leqslant B$$$.

      Brilliant proof btw!

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

Just a request:

Please mention beforehand whether there is an interactive problem. Newbies like me will benefit a lot.

I would have opted out of the contest because I did inevitably lose time in my futile effort on the interaction rather than the algo crux. I would have not registered had I known beforehand of the presence of interactive problem(s).

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

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

Is there an issue with AtCoder's Library's lazy segment tree? Or did I improperly use it. I would appreciate any advice anyone can give. Because I tried using ACL's lazy segtree in problem D and got WA. The exact same code but with AI.Cash's lazy segment tree (from here) passed the pretests.

I was able to stress test and find out a test case that the code with ACL's lazy segtree failed on.
1
4
5 1 3 2

Expected Output (in my opinion): 1

Submission that passed pretests: 282094170
My WA submission: 282066742

Cleaned code (without debugging lines and comments):
Pretests passed code
WA code

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

Can anyone explain the logic of problem C?

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

    You can start by appending to the back of string (so lets append 1 initially):

    - if after appending 1 you get positive response, continue the loop otherwise pop_back() and append 0

    - if after appending 0 you get positive response, continue the loop otherwise pop_back() and now you know you have found the suffix so you can do similar thing but append on the front of the string to find the prefix

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

    Sure, ill explain my approach (this is rushed so no fancy LaTeX sadly)

    essentially, this problem, if youve ever seen ioi 2018 d1 p1 (combo), is a lot like that, even in its statement it bears heavy resemblence. But in addition to that, this one is a binary string

    Now if we think of a naive greedy approach, we can notice that

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

      greedy can be optimized easily to get $$$ <= 2n $$$ queries. You realize that once we reach the end of the string, elements on left have to be either 1 or 0. So we don't we need to ask two times. We can only ask if its $$$ 1 + suffix $$$ or not. if it is then the suffix increases by 1 on left otherwise increases by 0 automatically

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

      lever how so orz

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

Good problems, binary search idea in D was pretty good, tried something similar for the first time

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

is E basically this? https://mirror.codeforces.com/problemset/problem/1614/D2

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

    bruh exact same

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

    funny part is, I have solved above qs already, but messed up in today contest

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

    No, but I also thought the same during the contest. For E you need minimum, not maximum

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

why system testing is not get started?

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

good problemset

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

Why don't you mention that there would be an interactive problem in this contest? We'd have prepared accordingly...

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

is it just me who felt this contest was significantly easier than the last one? i only solved A in the last contest but i was able to solve AB and got the logic for C very quickly (couldn't solve C because i had never solved interactive problems before, so i struggled with converting the logic to code)

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

What a greedy round.

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

Guys, any questions list i can upsolve to become better?!

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

C my first interactive problem and damn how I hate interactive problems now. Anyway anyone got solution of D. My code was like this:

Spoiler

It is pretty straight forward as can be seen but obviously it is wrong and more obviously it did not work. So anybody can tell me what could be the correct approach and how to avoid this infinite loop problem will be much appreciated. peace

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

    just an advice so you don't get downvoted. put the code in spoiler tag. people don't like long comments and they may downvote you

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

In Problem A, In the input statement, the meaning of x and y was switched, which caused me one wrong answer. Please review.

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

could anyone provide edge cases for F1? i am pretty confident my soluton is right, but i am still getting WA even after debugging. link

nvm, found the edge case

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

Am I the only person who used prefix sums for D?

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

    How did you solve it using prefix?

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

      Minimum element = min(P[i]/i) where P[x] is sum of first x elements.

      Maximum element = max(ceil(R[i]/i)) where R[x] is sum of last x elements.

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

        Can you please explain why this works and the intuition behind it? I thought of doing something something similar after realizing that the overall sum of the array doesn't change after operations but couldn't get the actual solution.

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

          It is because we if you think you can actually shift a +1 from the left to right and -1 from right to left,

          lets just say we have

          [3,1,1,10,10,10]

          1. when we are at index 1 we cannot shift any bit from left as there is nothing
          2. when we are 2 we can see that we can shift 1 bit ahead to make [2,2,1,10,10,10] => (3 + 1) / 2;

          so like this at any given index we can find the minimum like this by traversing the array from left to right and taking always the minimum og the average till there.

          and same we can iterate a from right to left to find maximum

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

            great intuition, but how were you sure this would work like when i was trying to figure that out I couldnt really get why this works

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

              I was not able to come up with this in the contest I got it after reading this comment

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

            so how would this work for [1,3]? if i understood correctly, this approach would say that the minimum is 2, while it is actually 1, since the 3 cant be reduced. sorry if i misunderstood the explanation

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

              ya that what i said at any current index you are calculating the minimum by just looking at the average till that index

              for [1,3]

              1. minimum will be set to 1 as average till 1 is 1
              2. minimum will still remain 1 as it was set earlier to 1 even if now the average is 2.

              note we cannot back propagate a +1 so at any current index we can either make the average decrease by 1 or make it same and we have to decrease maximum and increase minimum for our optimal answer we will just calculate the minimum till that index.

              similarly you can calculate the maximum by either traversing from last or reversing the array,

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

                i understood right after writing the comment xD, thank you for the explanation anyways. this seems very intuitive, i shouldve probably focused on this problem instead of F1 :(

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

          Just try to equalize all elements in array.

          For any two elements i,j where i < j and a_i > a_j. Simply imagine pushing one from a_i to a_j (Do one operation of all k where i <= k < j). Repeat until array is sorted. The Psum method is the efficient way to calculate min/max.

          The proof that psum works is through induction.

          Obviously, we can equalize any singular. element of the array, by doing no operations, and we can near-equalize(max-min = 1) a subarray of elements that are a a a b b b where a>b, by simply decreasing each a and increase each b.

          Now lets assume we have equalized the first k elements where p[k]/k = a, and the exists a l where p[l]/l = b and b<a. We can equalize the next l-k elements, through the inductive structure we are building. So, this results in the subarray aaabbb, which we have proven we can equalize.

          The proof for the max remains an exercise to the reader, but is VERY similar to the min.

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

            Hey, Can you please once look at this code of E and try to find why it's failing for a hidden case -> 282135524

            Logic -> I will get the minimum gcd possible in every iteration

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

            For maximising the minima, I tried to greedily increase each element without lowering the current maximum minima till the ith index by trying to make it equal to the average till now (only possible if avg was higher than element at i) doing so may result in increasing the minima but never lower it. We dont make it more than the avg since it risks decreasing the global minima till now without ever increasing the global minima. We also dont leave it lower than the average since we always can make it equal to the average guaranteed to not reduce the global minima. If the avg was however smaller than element, then then we would leave it as is and take care of it in future iterations as the elements which gets decreased when an element is increased to its avg. I did it separately for the maxima and subtracted the and to my surprise it was AC lol.

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

        I did the same thing

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

        omg what a great solution, i was so close to this did the exact same for the minimum but was not able to come up that we can do the same for maximum.

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

        Did exactly this and got AC

        https://mirror.codeforces.com/contest/2013/submission/282078787

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

    I used prefix sum too. The first thing that came to mind was binary search on looking at the constraints.

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

I get burned by i32's every time :(

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

why this code is not giving TLE

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

A B C Tutorial in Bangla

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

How did you solve E?

I don't know why "the sum of $$$\max(a_1, a_2, \ldots, a_n)$$$ over all test cases does not exceed $$$10^5$$$" at all.

My solution is very sample. This is my code: https://mirror.codeforces.com/contest/2013/submission/282110416

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

    E can also be solved using dp. Let A = max(a[1],...,a[n]). dp[i][j] denotes minimum gcd(a[1])+...+gcd(a[1],...,a[i]), gcd(a[1],...,a[i]) = j. We should only consider i <= log2(A), since it is optimal if gcd decreases at the beginning and it can decrease at most log2(A) times. j <= A. Transitions are as follows : dp[i][j] = dp[i-1][j*k]+j if there exists some a[l], such that gcd(a[l],j*k) = j, k is some constant 1 <= k <= floor(A/j).

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

      "if there exists some a[l], such that gcd(a[l],j*k) = j." How do you check this quick enough?

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

        gcd(a[l],j*k) = j => gcd(a[l]/j,k) = 1. Let's maintain cnt[i][j] meaning number of numbers x, such that x is divisible by i and x/i is divisible by j. Now, a[l] such that gcd(a[l],j*k) = j exists IFF M(d1)*cnt[i][d1]+M(d2)*cnt[i][d2] +...+M(dm)*cnt[i][dm] > 0. M denotes Möbius function. d1,d2...,dm are all divisors of k. We can calculate cnt in O(nlog^2(n)).

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

Can someone tell why this gives TLE https://mirror.codeforces.com/contest/2013/submission/282114560

And to avoid TLE using this solution for problem C

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

In problem F1, can someone explain why the answer for this test case is Bob:

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

My logic is that Alice can go 2 -> 1, then Bob can only move to 8, then Alice moves 1 -> 7, and Bob can't make a move so Alice wins.

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

    Alice starts from 1 and Bob starts from 2.

    1. Alice goes from 1 to (one of 3, 4, 5, 6, 7), can't go to 2 because Bob is there.

    2. Bob goes to 8 from 2.

    3. Alice is one of 3, 4, 5, 6, 7. In any case can't go anywhere

    Bob Wins

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

      Oh thank you, I misread the problem and thought that both Alice and Bob start from the same node $$$u = v$$$.

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

Could someone help me proving the TC of this solution in Problem D?

Every iteration I convert all the decreasing subarrays to their almost-equal values with the same sum.

I keep doing this until no operation changes the current array. I can't think of proper upper bound for this solution.

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

Great contest :)

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

Can Someone Please Help me with solution of problem C, which causes TLE 282128399 Thankyou

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

    Actually it should gives you WA, but because you don't assert whether you were given $$$-1$$$ or not, so your solution run limitless without terminating.

    Here is your submission with assertion to avoid TLE

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

Hey friends! Does anyone know why I am getting TLE on test 1? 282130372 I know my approach is incorrect, but I'm just trying to figure out the TLE. If you cast ans.length() into a long long it works, but I'm not sure why it doesn't otherwise.

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

    As I mentioned in the comment above. TLE is in fact a WA verdict. Because you are given $$$-1$$$ as a response and the program should terminate after. So, treat TLE here as WA or you could just assert that $$$n$$$ is not $$$-1$$$ before proceeding into your logic

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

      Ah I see, so n could be -1 as well, that makes a lot of sense. Thanks for your help!

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

        If you make an incorrect attempt or exceed the limit of 2n attempts, you will receive −1 instead of an answer and get the verdict Wrong answer. In this case, your program should terminate immediately to avoid undefined verdicts

        Honestly, It's my first time facing such issue in interactive problems. But it's good to learn :)

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

First time solved an interactive problem in a contest..feeling good

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

Rating Prediction

A — 800

B — 900

C — 1500

D — 1800

E — 2100

F1 — 2600

F2 — 3100

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

Never thought I would be in the leaderboard of a contest ever! Thanks a lot

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

Looks still no editorial yet. This is my unofficial editorial.

A
B
C
D
E
→ Reply
»
6 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

My submission: 282147053

Can someone please explain why the following approach works for C-Password Cracking?

Start with an empty string query = "".

Finding the longest suffix:

1s. Guess query + '0'. Yes -> {goto 1s} No -> {goto 2s}

2s. Guess query + '1'. Yes -> {goto 1s} No -> {longest suffix found; goto 1p}

Finding remaining prefix

1p. Guess '0' + query. Yes -> {goto 1p} No -> {goto 2p}

2p. Guess '1' + query. Yes -> {goto 1p} No -> {query is the password}

Up to this point, I know that this approach may take $$$2n + 4$$$ queries at max ($$$2*n$$$ for each character, 2 when the longest suffix is found and we query by appending '0'/'1', and 2 for the prefix similarly.

Improved approach: I maintained two vectors of strings yes and no. Each time I get 1 as a response, I put query inside yes, else into no. Before querying, I put the following checks:

  1. query.size() <= n

  2. every substring in yes must be a substring

  3. no substring in no should be a substring

In this case, I can see that the extra 2 queries for prefix will be cut off leaving $$$2*n + 2$$$ at max. However, this approach has passed all test cases, so queries are reduced to $$$2*n$$$ at max. How?

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

    When you change from suffix to prefix, you can actually be sure the next character that is added to the start of the string is not the same as the first character as you current string. For example:

    0: 1

    00: 1

    000: 0

    001: 1

    0010: 0

    0011: 0

    Here, because 000 is not a substring, the longest contiguous substring with all 0 is only of length $$$2$$$, so guessing 0001 is not needed at it has three consecutive 0. When you check if the no substrings are actually not in your queries, you saved the wasted query of 0001 in the above example, which means this lowered the queries by $$$1$$$, as now you only need $$$1$$$ query for the first time checking prefix).

    Also, in the query of size $$$1$$$ strings, you either get 1 when you query 0 (which means the first character only take $$$1$$$ query, cutting another query from the total), or you get 0 for 0 and 1 for 1 (which means the string is all 1 and ended with $$$n+1$$$ queries)

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

      Thank you very much for your explanation. Is the worst case still $$$2*n$$$ (I think so)? I tried submitting my solution on oj.uz (link). As you can see, it's saying TLE (obviously because of repeated substring checks). Also, in the problem statement on oj.uz, for a string of length 1000, the maximum number of queries is limited to 1024. How can I improve my solution so that it takes fewer queries and is fast enough?

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

Just now I solved D by guessing, but I couldn't prove my solution. Can someone tell me why the following approach works?

Find the highest possible min using the operations, find the lowest possible max using the operations, then the answer is just lowest_max - highest_min.

Intuitively, it makes sense to me the fact that when using the operations to maximize highest_min you don't violate the operations used to minimize lowest_max, but I can't definitively prove it. Link to my submission.

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

    what did this row k = max(0, k — diff)?

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

      Well that is just implementation detail. Basically the operation can be rewritten to "choose i and j and move any amount from arr[i] to arr[j]" and k is amount of operations we've done to get all arr[i] so far to become mx (or mn in the case of checkmn), but haven't picked the index j to move it to. So every time we meet an element that already satisfy mx or mn we treat it as arr[j] and want to deduct as much from k as we can.

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

    Check this and this out. Using these, you can see that choosing the maximum does not change which minimums are possible to obtain and vice-versa.

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

It was a really good and varied contest. But we are waitting the tutorial.

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

Can anyone tell me why problem F1 WA on 11?

My submission:https://mirror.codeforces.com/contest/2013/submission/282168778

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

Problem F1: My solution fails at 1326th test case of test point 2. see 282161893

I just simulate the game process by finding what next nodes the current player could reach by bfs, and block these nodes from now on. The one who can not reach any new node fails the game.

Could you give me a hack case, or is there something wrong with my code? Thanks a lot!

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

    Why dont you learn how to stress test.....

    Anyways, here you go 

    1
10
1 2
2 3
3 4
1 5
5 6
6 7
2 8
4 9
9 10
4 4

    Your code outputs Alice, however here Alice is actually in zugzwang. If she moves to 2, she loses when Bob moves to 9 and if she moves to 5, she loses when Bob moves to 3.

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

      Just curious, for stress testing these type of problems do you just generate many random trees?

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

        Yes

        (i, random(1, i — 1)) trees should be fine for most problems, and is what i did for F2 stress testing

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

      Thank you!!!

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

My solution to E that doesn't use "greedy":

  • First find $$$d = \gcd(a_1, a_2, ..., a_n)$$$, then transform $$$a_i \leftarrow a_i / d$$$. We will work with this new array $$$a$$$ and just multiply the result by $$$d$$$.

  • Realise that because $$$\gcd(a_1, a_2, ..., a_n)$$$ is now $$$1$$$, the prefix $$$\gcd$$$ must go to $$$1$$$ sooner or later.

  • Imagine we have arranged the array optimally, let $$$g_i = \gcd(a_1, a_2, ..., a_i)$$$, then the answer is $$$g_1 + g_2 + ... + g_n$$$, or we can write it as $$$n + \sum_{i = 1}^{n}{(g_i - 1)}$$$.

  • Realise that if $$$g_i = 1$$$ then $$$g_{i + 1} = 1$$$, so once $$$g_i = 1$$$ then we don't have to care about later elements because they don't contribute at all to the answer.

  • Which mean to choose the optimal sequence, we want start from some $$$g_1 = a_i$$$ and go to some $$$g_i = 1$$$ with the lowest cost possible, where from $$$g_i$$$ we can go to $$$g_{i + 1} = \gcd(g_i, a_j)$$$ with some $$$a_j$$$.

  • The cost is just the sum of the elements $$$g_i$$$.
  • There might be some concern about using a number $$$a_i$$$ multiple times, but we can see that it's not a problem:
Proof

So now we can try to find the best way to go from each $$$g_1$$$ to $$$1$$$, and we will do this with dynamic programming:

  • Let $$$f[x]$$$ be the minimum cost if we start from $$$g_i = x$$$ and want to get to $$$g_j = 1$$$.
  • Then $$$f[x] = min(f[y] + (y - 1))$$$ for each $$$y$$$ where we can find $$$a_i$$$ such that $$$gcd(a_i, x) = y$$$.
  • The answer will be $$$min(f[x] + x - 1 + n)$$$ for all $$$x$$$ where we have some $$$a_i = x$$$.
  • To calculate this, we have to find the possible $$$y$$$ values for each $$$x$$$ or vice versa.

In my solution, I find $$$x$$$ for each $$$y$$$ like so:

  • Let's count how many $$$i$$$ exist for $$$x = py$$$ such that $$$y = \gcd(x, a_i)$$$.
  • $$$y = \gcd(x, a_i) = \gcd(py, qy)$$$ where $$$a_i = qy$$$ and $$$gcd(p, q) = 1$$$.
  • So for each $$$y$$$, we find all possible $$$q$$$.
  • And then we count for each value $$$p$$$ from from $$$1$$$ to $$$q_{max}$$$, how many coprime number with $$$p$$$ we have.
  • Then for each $$$x = py$$$, we just need to check if $$$q$$$ exists.
Coprime counting

Let $$$k = a_{max}$$$, the final solution is as follow:

  • Iterate $$$y$$$ from $$$1$$$ to $$$k$$$.
  • For each $$$y$$$, find all possible $$$q$$$ where there is $$$a_i$$$ such that $$$a_i = yq$$$.
  • Perform the coprime counting on values from $$$1$$$ to $$$q_{max}$$$. Note that $$$q_{max} \leq \frac{k} {y}$$$.
  • Then update $$$f[x] = min(f[x], f[y] + y - 1)$$$ for each $$$x$$$ such that $$$x / y$$$ has some coprime numbers. Note that $$$x \leq q_{max}$$$.

The iterating $$$y$$$, finding $$$q$$$, and updating $$$x$$$ is done in $$$O(k\ln(k))$$$.

The prime counting is done in at most $$$\sum_{i = 1}^{k}{O(\frac{k}{i} \ln(\frac{k}{i})})$$$. This is a bit complicated, but it should be $$$O(k \ln(k)^2)$$$.

My implementation: 282179720 (pretty much the same as the one in contest but cleared up to use the same variable name I used in this post)

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

    This looks a bit complicated considering an $$$O(n^2)$$$ solution passes AC

    https://mirror.codeforces.com/contest/2013/submission/282184391

    This just starts from $$$gcd$$$ being mininum $$$a_i$$$ and on each iteration find next minimum $$$gcd$$$ with all remaining elements in $$$a$$$ and sum these $$$gcd$$$s in $$$ans$$$.

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

      That is O(NlogN). gcd's prime factorization will consist of at most logN numbers and each time finding the next minimum gcd will remove at least one of those numbers. Your code will loop through array at most logN times until gcd becomes 1 and it will stop. Thus it's N logN

      That aside, the point of the comment you're replying to is to describe a method that we can use precisely to avoid this approach if we can't prove it.

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

        Considering nested loops is the first thing that comes to mind isn't this problem too simple for E on Div.2?

        During contest I discarded this approach as too simple, thinking it was a bait of some sort.

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

          Well based on the fact many skipped D to solve E, probably many people will agree with you. But yeah it is definitely quite straightforward, even compared to some Div 2 D in the past.

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

where is the editorial? (cry emoji)

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

Editorial ?

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

why is this giving Idleness limit exceed 282218277

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

C can be solved with $$$2n-1$$$ operations.Just by starting with "? 01" and "? 10" when $$$n>=2$$$.

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

I_Love_Diar_Narumov please give the editorial

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

Still waiting for the editorial

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

editorial please!! (>_<)

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

can we do something like this for Problem D using one binary search: minvalue=0 maxvalue= 1e12 (possible answer of max-min)

so for each mid value try to change the array such that the max-min in the array is at most mid value

Can anyone share this solution if someone tried it and got accepted?

I tried but I wasn't able to pass all tc

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

Customary thanks to Dominater069 for solving the contest and providing his clean and consise solutions.

→ Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I have been sent an email for possible violation,but I assure you that no malpractice has taken place.

The code looks extremely similar, but I even have my intution notes, I have no idea how two people can come up with this similar code.

But I have submitted the code earlier as well:

Submissions: Their submission : https://mirror.codeforces.com/contest/2013/submission/282098987 Mine: https://mirror.codeforces.com/contest/2013/submission/282060860

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

Hi, I have been flagged by the system for my solution to problem E. I ensure that the code was written by me, in a private environment. The logic is quite simple and similar to few grandmasters as well. Kindly help with this issue. I have been a trustful participant. I have also tested rounds on CF, with few coordinaters knowing me. I am happy to provide any more evidence. Thanks! MikeMirzayanov

→ Reply
»
20 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

I am writing to address the recent issue regarding my submission in the codeforces round 973 It has come to my attention that my submission was skipped due to its similarity to another participant's solution. I understand that such situations are treated with caution to maintain the integrity of the platform.

However, I would like to clarify that any similarity between my solution and the other participant's is purely coincidental. I have always strived to adhere to the rules and maintain the spirit of fairness during competitions. Given this, I kindly request you to reconsider my submission and restore my rating for this contest.

→ Reply