aropan's blog

Codeforces Round #675 (Div. 2) based on Qualification Andersen Programming Contest 2020
By aropan, history, 4 years ago, translation, In English

Tryam, Codeforces!

andersen

Perhaps you are waiting for us to announce the final of BSUIR championship, but for now we are only glad to invite you to Codeforces Round 675 (Div. 2), which will be held on Oct/04/2020 19:05 (Moscow time). This round will be rated for the participants with rating lower than 2100.

The problems were prepared for you by andrew, hloya_ygrt, AleXman111 and Vladik together with me. We think that we have prepared good problems for [contest:297213]. After that we selected the best ones for this round.

The company Andersen has been holding a competition for the second year already, which is primarily intended to support students of regional universities in Belarus and Ukraine (starting this year).

First of all, we would like to thank MikeMirzayanov and everyone involved in the development of Codeforces and Polygon platforms. No less thanks to KAN for coordination — thanks to him you will be able to understand our problems. And also to all our coaches and parents who taught us to do everything that we can do.

The score distribution promises to be like this: 500 — 750 — 1000 — 1500 — 2000 — 2750.

Good luck and clean code to everyone!

UPD

Congratulations to the winners of the official standings:
1. Yukikaze_
2. lunabbit
3. kamer
4. Potassium_Fan
5. 2018LZY

And overall winners:
1. awoo
2. dlalswp25
3. tfg
4. Sugar_fan
5. hank55663

The editorial will come later.

UPD

The editorial came.

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

Comments Comments (287)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +166 Vote: I do not like it

Notice the unusual start time :)

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

Will the two contests be held at the same time?

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

    Yeap, but [contest:297213] will be officially for students of regional universities Belarus and Ukraine only.

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

This contest starts 1 hour 30 minutes later than the usual time.

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

    Comon, I was typing when the first guy put the message and it went unnoticed to me and i get 22 downvotes, nice.

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

Thanks, this is a most excellent time for those of us on the American west coast (9 AM)!

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

Wait, where are the testers?

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

    Perhaps they both prepared the problems and tested each other's problems :)

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

Are problems in proportion to scoring distribution? Or we are going to see another Codeforces Round 657 (Div. 2) where problems were much tough than their scores.

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

    my experience says it will be similar to the one you mentioned.

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

    Absolutely it was not like Round 657, but the scoring distribution was not standard. I am not sure why people strictly prefer downvoting comments, I was just talking of a possibility which came almost true for this round.

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

As a tester, I strictly recommend you to partisipate this round. Also I want some contribution.

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

    And Now you are getting contribution for your efforts. Enjoy! :)

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

Good luck and clean code

thanks :)

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

"Good luck and clean code to everyone!" Is this a hint for Implementationforces.

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

In China, I have to stay up late to participate in this contest. Hope my rating++.

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

Previous timing was better 8:05 pm(IST).

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

I wish to join in but 00:05 UTC+8 is too late for me. Anyway hope everybody has a nice contest.

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

Good luck and high rating to everyone!!!

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

00:05(UTC+8) is a bit late for the Chinese contestants.

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

Valorant statements again?

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

could you make my contribution from negative to 0 ?

I know I would add more negative from this comment but still I wanna give a try.

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

oppsss i got earlier here. 1.5 hrs still to go for contest

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

It will end at 12.04 am here. Hope I can have a sound sleep after completing a good number of problems. And good luck for everyone!

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

Hey Dear codeforces, first thank you for developing foremost and prime algorithmic platform and I know this process will continue, and second, I hope the ratio of codeforces's contest holding per days will grow to meet one contest every two sequential days. finally, I appreciate your efforts for creating a contest and hold it in codeforces's website:-)

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

Best of luck guys!! Wish you all a good contest :)

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

Why am I not able to register?

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

so bad

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

kingmanas is openly cheating in this contest, I have proofs Manas what's the use of rating when you get it through cheating!!?

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

    Woah! Could you please prove it... Might be a hacking attempt or you are just upto defaming me. If the latter case, then you might have read the article on 'evercookie' too. Mike can easily find you, if he wants to.

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

      Hahahah nice try on scaring me off. No issue, enjoy this fake rating you earn through your cheating. :) I'm gonna expose you soon don't worry

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

        Haha, I know that was meant to distract me mid-contest... Why do you feel the need to do that to me? You sent a DM about some whatsapp screenshots, please forward them here.

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

          The guy who sent me the screenshots doesn't want you to know that he shared this with, so my hands are tied. So you're saved for now. And I really don't need to distract you lol, I'm a CM for the last 3 months so I don't really care But I just don't like when someone like you cheats and gets huge delta

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

            Your statement disproves itself. If a guy helped me cheat on WhatsApp, it means I already know who he is. Whatsapp is not anonymous. Please feel free to share any screenshots you have, haha. One thing your comment does prove is that you are not a CM.

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

B should have been 1000 and c 1500

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

how to solve C?

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

    Consider the contribution of each digit to the sum. For each digit count the number of subarrays before it which were deleted. In this case the contribution is fixed. Consider 1,2,3,4 and the contribution of the 3 for all subarrays before it which could be deleted. The contribution would be 30 * (number of such subarrays) which is 30 * 3.

    Then count the contribution for the subarrays after it which can be deleted. This required some weird sum manipulation. Consider 1234. Consider the digit 2. There can be one subarray of size 2 after the digit 2 which can be deleted and 2 subarrays of size 1. So, the contribution of 2 would be 2 + 20 + 20. This can be written as 2 * (1 + 20). If you do this, you'll see a pattern.

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

      can you explain the pattern cause I tried but couldn't find one.

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

    Consider the given string in reverse. Now for each position $$$i$$$ from 1 to $$$n$$$, let us calculate the contribution of $$$s_i$$$. In case the removed substring was to the right of it, then the contribution of $$$s_i$$$ is $$$10^{i-1}s_i$$$. The number of such substrings are $$$n - i + 1 \choose 2$$$. In case removed part is to the right, then the contribution is $$$s_i\sum_{z=1}^{i-1}z10^{z-1}$$$. The summation can be maintained while iterating over the string.

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

    https://medium.com/@harryjobz/bargain-a6cf0b9a5262 I have explained it here since the actual explanation is too long to write it here

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

Some one please tell me what is the procedure of B I try for 1.5 hour but failed on test case 2

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

    Basically for a particular cell $$$a[i][j]$$$ the palindrome squares which should be equal are

    $$$a[n+1-i][m+1-j],a[i][m+1-j],a[n+1-i][j]$$$

    (notice this works even when these are 2 cells and not 4), now our task is to chose an $ x$ such that $$$|x-a|+|x-b|+|x-c|+|x-d|$$$ is minimized where $$$a,b,c,d$$$ are the four cells mentioned above,its easy to see that if $$$a\leq b\leq c\leq d$$$ then any $$$b\leq x \leq c$$$ minimizes this expression; so for convinience pick the average of the middle two numbers.

    Here is my submission 94697945

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

      Damn man! I took the average of all four numbers

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

      why average of 4 numbers will not work?

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

        take the four numbers to be: 1, 1, 1, 1000000

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

          But what's the theory behind it, Why such thing occurs? Why average not suitable here for all four numbers??? I'm noob, please explain...

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

            Finding the value where the sum of diffs to some other values is minimum possible is equivalent to following problem: Find a point on a line with sum of distances to some other points on the line be minimum.

            Assume some point x on the line, and the number of other point on the line left of it and right of it. If you move x in one of both directions, then the sum of distances changes by the number of points left/right. The sum increases by the number of points on the side you not go to, and it decreases by the number of points in the direction you are going to.

            So, to minimize the sum, you go to the direction where more points are...as long as there are more points. At some step there will be same number of points left and right. There is the optimum. And this point is definied to be the median.

            Note that with an odd number of points there is exactly one median position. With an even number of points all position in between the two "middle" points are equal optimal.

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

    My Approach was a[i][j],a[m-i+1][j],a[i][n-j+1],a[m-i+1][n-j+1] should be equal

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

    I'm not sure if this is the best solution, but here goes

    Iterate through the entire array. If for all elements in the array, ar[i][k] = ar[n-i-1][k] = ar[n-i-1][m-k-1] = ar[i][m-k-1], that means that the array is a nice array (this is derived from the definition of a nice array)

    So we iterate through all the elements in the array, and we have to make adjustments to the four elements that I listed above in order to make it a nice array.

    Call the four elements in question, a_1, a_2, a_3, and a_4. Let the value that we want to change all the four elements to be x. Clearly we want to minimize |a_1 — x| + |a_2 — x| + |a-3 — x| + |a_4 — x|. This is a pretty standard greedy algorithm problem, and the minimum ends up being achieved when x is the median of a_1, a_2, a_3, and a_4.

    My Solution: 94693568

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

What were the hacks on E?

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

    I was printing last two letters wrong in some cases and got pretests passed, so i think that was not covered on pretests

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

    my first submission fails on "bbzzbzzba"

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

      Mine fails too. Should have taken the announcement seriously but this should have been in the pretests.

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

      For the first time I'm wishing someone would have hacked my solution, Could have become Master :(

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

    Some fail on "bccba"

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

    yzzyx

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

    From my experience, there were 2 things to consider:
    1. You can't remove pairs which are not continuous in the original sequence
    2. You need to keep the two stacks in sync, the one with the last different element and the one with the current answer. If you pop from one, you need to pop from the other too. Similarly for pushing

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

    Mine broke on aaffaihe

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

    Ashishgup were you able to figure out the hack for your solution?

    I am asking since my solution had the same wrong answer on the same line in the same testcase so I was just wondering if you figure it out do reply. Thanks

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

What is up with MLE on D? M is upto 1e5 that should be doable in 256 mb?

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

Is there an elegant way to solve C without keeping track of all the edge cases?

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

    think dp

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

      is the contribution of each position i : summation(i) * summation((10 ^ (n — i — 2)) * (n — i — 1)) ?

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

      I'll do you one better, think CP

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

    Is "write a DP" elegant enough?

    My DP state is 

    [processed prefix length][# of blocks of removed digits so far][did we remove the last digit?]=(sum of possible numbers, count of possible numbers)

    Transition is to consider two options: to remove the current digit or to keep it. Code: 94671611.

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

    My approach was, take every suffix of the string, now we have to combine it with every prefix(there should be gap of atleast one character between ending of prefix and starting of suffix),maintain sum of prefixes.Combining is multiplying length of suffix with the sum of prefixes and adding it to current suffix.

    94711980

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

      Can you explain this in detail?

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

        I think the code is self explanatory, go through it and feel free to ask me anything you didn't understand

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

    My approach didn't have much edge cases except for the first and last digit. You can calculate the contribution of each digit in answer by considering 2 cases :
    1. If a substring before the current index is removed, it won't affect the place value of the current digit, say $$$d$$$ and is equal to $$$d*i*(i+1)/2*10^{n-i-1}$$$.(0 based indexing)
    2. If the substring removed is to the right of the current index, it's contribution is : sum of $$$(j)*10^{j-1}*d,$$$ where j is from (n-i-1) to 1.
    My implementation.

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

      I am not able to decode why are we multiplying with i*(i+1)/2. Can you explain a bit??

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

        That's just number of ways to pick a substring in a string of length i

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

How to solve D ?

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

    I don't have a proof but... I built a graph:

    • vertexes are the given points

    • connect start and all "movement points" with weight: min(abs(s_x — x), abs(x_y — y))

    • connect each "movement point" with 4 the closest "movement points" by x and y.

    And then run Dijkstra on this graph!

    Seems if you want to jump from "movement point" A to "movement point" B you have to spend the same time as if you visit all "movement point" between them.

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

      It should be clear why running Dijkstra on complete graph is correct. To prove that running it on this "pruned" graph is sufficient it is enough to show that any "non-adjacent" edge can be represented as a sequence of "adjacent" edges, e.g. if you want to get from vertex A to vertex B and the optimal move is to go over coordinate x, you can as well consider all vertices sorted by x and sequentially go through all vertices that are between A and B in this sorted list.

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

        Hey, could you elaborate on how you proved that you could prune it this way? I was able to prove that djikstra on the complete graph works, but that sol would give a TLE/MLE. What exactly do you mean by ""adjacent" edge and "non-adjacent" edge"?

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

          I call two vertices "adjacent" if they are next to each other in the list sorted by x or by y (so for each vertex you have a total of at most 4 adjacent vertices — 2 by x and 2 by y).

          I wrote in my comment above why this works. You may visualize it with 1D version of the problem where the claim will be more intuitive.

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

    shortest path problem

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

I got that there is some prefix and suffix stuff and modulo of long strings involved in C..but how to solve it in linear complexity?

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

    For each number at ith index, try to see how much contribution it can give to final answer.

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

    Observe the pattern :

    S = "12345"

    Removable Sub-Strings :

    length_1 = '1', '2', '3', '4', '5'
    length_2 = '12', '23', '34', '45' length_3 = '123', '234', '345'
    length_4 = '1234', '2345'
    length_5 = '12345'

    Strings Left after removing the above Sub-Strings :

    '2345' (after removing '1')
    '1345' (after removing '2')
    '1245' (after removing '3')
    '1235' (after removing '4')
    '1234' (after removing '5')
    '0345' (after removing '12')
    '0145' (after removing '23')
    '0125' (after removing '34')
    '0123' (after removing '45')
    '0045' (after removing '123')
    '0015' (after removing '234')
    '0012' (after removing '345')
    '0005' (after removing '1234')
    '0001' (after removing '2345')
    '0000' (after removing '12345')

    '0's are appended at the first for the ease of understanding. You can ignore them.

    Contribution of every index in the total sum :

    0th index ('1') = 1 * (4*pow(10,3) + 3*pow(10,2) + 2*pow(10,1) + 1*pow(10,0) + 0*pow(10,4))
    1st index ('2') = 2 * (------------------- 3*pow(10,2) + 2*pow(10,1) + 1*pow(10,0) + 1*pow(10,3))
    2nd index ('3') = 3 * (---------------------------------------2*pow(10,1) + 1*pow(10,0) + 3*pow(10,2))
    3rd index ('4') = 4 * (------------------------------------------------------------1*pow(10,0) + 6*pow(10,1))
    4th index ('5') = 5 * (------------------------------------------------------------------------------10*pow(10,0))

    Hope it helps !!!

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

Am I missing some simpler solution, or was online part of problem F simply "take offline solution with a segment tree, add persistency on top of that to make it online"?

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

    The memory limit is tight for segment tree with persistency. 1024 MB may be better.

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

      Oh, I didn't think about that. I'd say this fact doesn't make the problem any nicer, although others may have a different taste.

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

        I finally got to use the fact that C++64 pointers are larger by 4 bytes compared to C++32 pointers, rip people that can fix MLE by changing compilers.

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

          Can you tell more about which compiler's pointers are 4 bits larger and why it helped in implementing the persistence?

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

            Oops, sorry. I meant 4 bytes. C++17 64 bits has 64 bits pointers I'm pretty sure. It helps in this problem because memory is a bit tight, changing compilers made barely MLE turn into 300MB.

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

          I was able to get a smaller memory footprint in the 32bit compiler by doing two ideas:

          1. [80MB Memory | 1500ms] Use a persistent BIT rather than a persistent Segtree. (https://codeforces.com/contest/1422/submission/94824471) Basically using an array of maps<int, int> rather than an array of ints and use --upper_bound(version) to find the greatest version <= to the one I'm looking for.

          2. [100MB Memory | 750ms] As I was making multiple updates for each version of the Segment Tree, I made a small trick to skip updating the nodes in the same version multiple times. The trick was to add a version variable to each node and pass the new desired version as an argument to the update function. That way when I try to create a copy of the node I only do it iff the desired version I pass is different than the version in the current node. (https://codeforces.com/contest/1422/submission/94825863). That way even though I made multiple updates for each version, I avoided creating multiple times the common nodes among those updates. :D

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

    I think, it's to cut off solution with algorithm Мо.

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

    I know how a persistent segment tree works, but I'm not too familiar how to use it. Can you explain how you used a persistent segment tree in F?

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

The problems were really interesting and amazing,but the score distribution is very low for these difficulty level problems

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

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

another horrible contest

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

    The contest was not horrible. Your participation was horrible

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

really bad score distribution. E was more easier than C(atleast to me). imo the only reason E had less submissions is just because it was E.

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

    I agree, I spent too much time on D(which I couldn't solve). I missed to submit E by just 1min. By correct scoring distribution we could have seen atleast 600 people solving E.

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

      Lol, I would take my words back "we could have seen atleast 600 people solving E" after seeing number of solutions getting failed in system testing.

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

    I wasn't able to understand E

    In the second example, for the longest suffix "abbcdddeaaffdfouurtytwoo" choose three pairs (11,12), (16,17), (23,24) and we obtain "abbcdddeaadfortytw"

    Why (2,3),(5,6), etc weren't selected? I apologize if I missed something?

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

      Because that is not lexicographically smallest strings

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

      choosing (2, 3) will give string "acddde...." which is lexographically larger than "abbcd....."

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

    Much easier if you don't read the statement, amirite?

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

The difficulty level of this round is much higher than a div2 round

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

D is similar to Timus 1205

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

Guys, did you all even face server slow done in last 10 minutes? I tried to go for hacks, but the main site itself wasn't loading. I am doubtful that this round shall be rated, if its the problem for many.

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

    in my computer, all of things is going fine

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

System testing results on E are such a massacre that it probably would've been too much even for good old days when having CF problems that allow hacks wasn't frowned upon :)

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

Can problem C be solved using Dynamic Programming?

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

    Yes you can calculate an AGP by dp see the below comment of mine!

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

    One more dp solution for problem C: 94861783

    I store 3 things:

    1. value of substring that ends in current pos and has no crosses

    2. (count, sum) of substrings that end in currend pos and last digit is crossed

    3. (count, sum) of substrings that end in current pos and last digit is uncrossed, but it already has some cross before

    1 transition is just prev*10 + current

    2 transition: we can cross current digit only if we have previous digit crossed, or if we take substring without any crosses and put first cross now, hence count is 1 + all that end in previous digit and last is crossed, and value is just sum of same things: value ended in previous digit and all sum of values that crossed in prev step. Since we don't add anything to the end we don't need to multiply.

    3 transition: we can add new digit (uncrossed) to any sequence that ends in previous digit and last is either crossed or not crossed (but already has some crosses before). (it's sum of 2 and 3 in dp) also we multiply it both by 10 and add current digit respective number of times. Because if we have 3 sequences that end in previous digit and we can add new digit to all of them and and this will create 3 different combinations.

    And the answer is sum of all sequences where last index is crossed and last index is not crossed but it has some crosses before.

    I'm not sure that it helps anyone, but I was so glad this solution worked, so I couldn't help but share with you guys.

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

C is simple if you make AGP sequence using dp. I got this during last moment but implementation finally completed 5 minutes later Sad lyf.

For ith digit in the sequence how many times it is included is simply.

(i*(i+1))/2 *10^(n-1-i) *d[i] where d is digit sequence + .

(1*10^0 +2*10^1+ 3*10^2.............(n-1-i)*10^(n-i-2 ) )*d[i].

I hope the intented solution is similar.

PS : ACCEPTED ! 94711408

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

    What is agp?

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

    Can you please explain how you got this AGP for the right part of every ith digit, I tried to make a formula but that's completely different from this, I thought that if I am at particular index 'i' then contribution of this digit will be

    i*(i+1))/2 *10^(n-1-i) *d[i] where d is digit sequence + .

    (zC1*10^(z-1) + zC2*10^(z-2) + ... + zCz*10^0)*d[i].

    Not: here 'z' refers to s.size() — 1 — i

    Can you please help me in getting why my second part of formula is wrong? According to me there should be zCx ways to remove x elements from the given number of elements will it not be correct here?

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

      You can only remove a contiguous sequence. Hence zCx would not be correct.

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

        Ohh yaa....what a stupid thing I was doing...thanx for telling bro!

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

    Similar to what I did in-contest, but I think my approach might be quite a bit cleaner:

    My submission

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

    why i*(i+1)/2?

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

      Number of substrings till index i is i*(i+1)/2; and if you remove any of these substrings from the front of digit i then its relative position will remain same that is 10^(n-1-i).

      For example . for 12345 and I consider digit 4.

      if I remove 1 length substrings . which are possible, 1,2,3 If I remove 2 length substrings before index of digit 4 these are 12 , 23. If I remove 3 length substrings these are 123 (only one.)

      and for all these removals the relative position of 4 remains same that is we are not removing anything from back thus 4 gets multiplied by 10^(n-1-i) where is is index of 4.

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

        Thanks for the explanation! I had a bit different approach, that got ACed after i found one of the top rankers using the same approach and fixed my code.

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

nice pretests on E, F

→ Reply
»
4 years ago, # |
  Vote: I like it +46 Vote: I do not like it 
int a,b,c,d;
d =  a+b+c-1;
cout << d << endl;

1000000000 1000000000 1000000000
Unsuccessful hacking attempt
    Why? 
     |
     |
     v

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

The reason why we need testers — Codeforces Round 675

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

    Actually this one is trivial. The reason why we need testers is Education Round 95. Though it seems they had a couple of testers.

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

Can anyone give me an example where (a[i][j] + a[n-i+1][j] + a[n-i+1][m-j+1] + a[i][m-j+1]) / 4 will not be the best choice when both N and M are even.

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

    1 1 1 9

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

    n=2, m=2 1 2 3 10

    (a[i][j] + a[n-i+1][j] + a[n-i+1][m-j+1] + a[i][m-j+1]) / 4 = 4, which gives a total modification cost of 12, however the solution is actually to change all values to 2, or 3, giving a total modification cost of 10.

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

Horrible pretests on problem A, I've already seen 5 submissions that shouldn't have passed systests get Accepted. For problems like this, where there are many, many solutions, why aren't the pretests adequately comprehensive to handle this?

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

    Constraints on the number of pretests?

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

I spent half an hour debugging before I realized that for B, you choose the median of the 4 numbers, not the mean... and I'm in AP Stats. rip.

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

    Yeah, its a while ago I was solving a problem that asked us to equalize all elements of an array where you could only use an increment. I misinterpreted it as equalize using either an increment or decrement. Broke my head for 15 min to either prove that it was equalized to median or most frequent element or avg, and gave up, only to realize I had read the q wrong. But luckily after the contest when searched up upon the misinterpreted problem, I found this — proof

    Happy learning!

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

Problem E: Test case 46 wrong answer 141st lines differ - expected: '430 hhccc...io', found: '428 ccccc...io' Isn't my string lexographically small ? 94701491

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

    aropan can you please explain?

    Got it. Thanks

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

      This suffix starts with hhhhhhhxxxxllllllhhhhhhhvvllllccccccodd.... You cannot delete all h (because odd group) before block with c.

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

        when will official tutorial come?

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

In the 2nd test case of 2nd question if we convert the matrix to 4 3 3 4 5 6 6 5 4 3 3 4 its still following palindromic condition and we require 36 operation and 36<42 then is there some error..plz help

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
    1 2 3 4
5 6 7 8
9 10 11 18

    The last element is $$$18$$$, but not $$$12$$$.

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

    Even if you use your matrix, the answer is still 42, not 36.

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

Wrong answer on problem E:

wrong answer 141st lines differ - expected: '430 hhccc...io', found: '428 ccccc...io'

Excuse me?

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

    Exactly.. How?

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

    bccba

    Correct answer: 3 bba ...

    you: 1 a ...

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

      nice catch

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

      Thanks!

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

        Can you please help me with possible hack for test case 42? From the comments I can see possible hacks for test case 46 are correct from my solution.

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

    Check for "bxxb", you will understand that we had to do the operation only once. The answer for this is -
    2 bb
    1 b
    2 xb
    1 b

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

I am afraid of the round which affiliated with some local CP competitions.....

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

One of the worst div. 2 contests i ever written. Very huge gap between problems C and D. And problem F, seriously? Basic ST problem only for write two different STs without any idea, it is problem for educational round not for competitive. So upset that I only read this problem 7-8 minutes before the end and done it 30 seconds later contest ends :'(

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

Can anyone please tell me what is wrong in this code for div2-C problem? i got WA on test 6.

94699300

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

    Instead of this

    ll c1=((ss[i])*x)%mod; c1=c1*i*(i+1)/2;

    Try following

    ll c1=((ss[i])*x)%mod; c1=c1*((i*(i+1)/2)%mod);

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

wrong answer 141st lines differ - expected: '430 hhccc...io', found: '428 ccccc...io' can someone explain? Got it.explained in above comments.

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

Got a wrong answer on test 46 for problem E. wrong answer 141st lines differ - expected: '430 hhccc...io', found: '428 ccccc...io' How is the expected answer correct here? (hh should have been removed, right?)

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

    Just what I came here to write

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

    Perhaps the string looks something like hzzhccio. In this case, removing the z's puts the two h's together, but there is no way to remove the h's.

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

      Can you please help me with possible hack for test case 42(not sure why my solution failed at 42, 4711203 )? I can see above potential hack for test case 46 seems to be correct in my solution.

      Output for "hzzhccio" :

      6 hhccio

      5 hccio

      6 zhccio

      5 hccio

      4 ccio

      3 cio

      2 io

      1 o

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

    If there were letters in between hh that got removed, then hh cannot be removed as you can only remove characters are that originally adjacent.

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

Can anyone tell me why there are so many 'Wrong answer on test 46' for Problem E (including me,T_T)?

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

    Many people over looked the fact that you can only remove letters that are ORIGINALLY adjacent from the original suffix meaning that for something like abba, you can remove bb to get aa, but since aa was not an originally adjacent pair you cannot remove it. It is kind of surprising because I think it was very well explained in the problem statement.

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

      I have paid attention to this, my answer does not produce the error for type 'abba'，but I still get a 'Wrong answer on test 46'

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

    I just looked at your submission for E and it seems that you printed out an incorrect length

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

    I get my answer dont update the 'last' char in some situation

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

If you get WA on test 46 of problem E, this case may be helpful:

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

    my ansser is right for this case, but still get a 'Wrong answer on test 46'

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

    My code solves that case (except that the 0 should be a 2), but I still get WA on test 46.

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

F for the bois, who thought mean would give the minimum number of operations instead of the median.

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

Problem D

in the input line, should it be :

1 <= n * n <= 10^9.

instead ?

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

I did a quick explanation of problem D — I don't do many of these, so let me know what you think!

https://www.youtube.com/watch?v=oJcU9RWnoU0&feature=youtu.be

(tldr: look only at "adjacent" nodes instead of full graph)

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

94699532 why I am getting wrong answer on pretest 2 in Problem B ?

Anyone explain me

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

    You are taking average of the 4 values, so it will be round down integer value, but it is also possible that optimal answer exist when you take it round up.

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

In Problem D , can someone prove why just connecting instant location to all four adjacent sides will work ?

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

    (Incorrect sample, this only works for point->lines or point->rows or line->line or row->row... not point->point) Image that you are on the spot (0,0) and have 2 instant-moviments at spots (3,5) and (7, 8). If you add all forwards edges: - (0,0) -> (3,5) = 3. - (0,0) -> (7,8) = 7. - (3,5) -> (7,8) = 4.

    You can see that for all triple path xyz (with x->z greater than x->y), the total length will be x-> y + y-> z.

    Then, you only need add edges to the nearst spot.

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

      (3, 5) -> (7, 8) = 3 not 4 you only need to move 3 steps in the Y coordinate.

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

        Yes, you are right.

        My sample is incorret. But this ideia is corret when you use:

        • points to lines or rows
        • lines to lines
        • rows to rows.

        point(0,0)->row(10) = point(0,0)->row(5) + row(5)->row(10)

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

Can anyone prove why the answer is the median of the 4(or less) elements in problem B?I googled it and used the function from here, but it doesn't explain this very well.

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

    This will help — my other comment . The second proof in the stack overflow page seems more intuitive.

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

    Just try doing it for 1 100 101 102, It should be obvious

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

    Imagine that you have a ordered array V of N no-negative elements and will transform all elements into Y=0.

    • Initial cost (Y=0) is the sum(V).
    • If you add 1 to Y, the cost will be increased by (num of elements smaller than Y)-(num of elements greater or equal than Y).
    • Than, the cost will decrease until to reach into median, after that, the numbers of (num of elements smaller than Y) will be greater than (num of elements greater or equal than Y).
    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    imagine you have 4 points sorted and listed on the x axis p1, p2, p3, p4 It can be proven that the best point let's call it p0 to make the distance from all 4 points to p0 minimum is either p2 or p3

    First it's obvious that p0 can never lie somewhere less than p1 or greater that p4 Second let's assume that p0 is somewhere between p3 and p4, let x = p0 — p3 (the distance from p0 to p3) the total distance is: (p3 — p1) + (p3 — p2) + 3 * x + (p4 — p0) = (p3 — p1) + (p3 — p2) + 2 * x + (p4 — p3) now imagine p0 is at p3 the total distance now is: (p3 — p1) + (p3 — p2) + (p4 — p3) we reduce the total distance by 2 * x similar proof can be done if p0 is located between p1 and p2 try it on paper and it will make more sense.

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

      Just loop over the four numbers and take the one which we can get with minimum moves.

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

        I know that, I claim that the two numbers in the mid after sorting are the best answer :D

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

Thanks for these quality problems :)

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

Problems were very educational, Thanks.

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

Me: I have been doing competitive programming for 8 years

Also me: Use average instead of median in B (fortunately it was considered on the pretests c:)

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

Can someone tell me why this submission for F gives runtime error? I can't seem to find any overflows or index out of bounds

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

    Maybe your LCM function will overflow with large a and b. I think you have to cast to long long in that function

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

      I use #define int long long , I thought it should cover that? Anyway, thanks for looking into it:)

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

        Yes, I missed that. It seems that in your ST query function, you get the answers of the two queries in tmp. These could be large. Then in the lcmModuloM function, they could get out of bound of the array primes. Also the LCM function doesn't work nicely with modulo. So LCM(LCM(a,b)%M,LCM(c,d)%M)%M != LCM(LCM(a,b),LCM(c,d))%M

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

          Oh I see, thanks. So how can I calculate the LCMs properly under modulo operation? I'd read another comment saying 2 segment trees are required...

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

aropan Can you please help in providing test case 42/46 for problem E? If I understand correctly many people are struggling in figuring out that. Even from the comment section I am unable to find any suitable hacks for my solution. Would be very helpful if both the test case can be broken down in some smaller string and shared in the announcement or editorial.

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

    check this case baaddabdaa. your output 4 babd 3 abd 4 aabd 3 abd 4 dabd 3 abd 2 bd 1 d 0 1 a correct output 6 baaabd 5 aaabd 4 aabd 3 abd 4 dabd 3 abd 2 bd 1 d 0 1 a

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

      Thanks, it is useful.

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

      my code is giving correct output on this test case but it is still failing on test case 46

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

Screencast of somehow managing to submit n^2 for C and failing E, with solutions for at least A-D

whatever, this comment will be buried anyway

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

Can someone plz explain where my code for problem C went wrong, i was able to pass the sample tests given in the problem. Thanks in advance and i wish you a +120 rating delta the next contest!

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

    Have you considered the possibility of overflow in the expression containing i*(i+1)/2?

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

Bruh... My soluon for F got TLE during the contest's systests and AC during the upsolving. I didn't change a thing! Look at my two last submissions.

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

    Your solution have 2979 ms time. TL is 3000 ms. I think 1% error in time is not critical for testing system.

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

After debugging problem E for around 2 hours it's finally accepted :|
Yay me -_-

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

I'm totally surprised that my code for problem E passed pretests, and also worked for the first 85 tests in systest. I had at least 10 errors and typos (HUGE errors). I still can't believe what happened. This is what I get for using hashing, binary search and sparse table in a problem that can be solved using a stack.

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

What complexity was C supposed to be? I found an n^2 (n being number of digits) solution but didn't bother coding it cause I figured the complexity was too high.

→ Reply
»
4 years ago, # |
  Vote: I like it -23 Vote: I do not like it 
#include <bits/stdc++.h>
using namespace std;
int main(){
    while(true)
        cout << "So Bad !" << endl;
}
→ Reply
»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Problems were really good especially C. It was that type of problem which i had not solved in the past. Thanks codeforces for such contest. Hopefully , I am becoming specialist according to codeforces rating predictor.

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

Thanks for the round! Finally got Div 1 :D (exactly on edge, 1900)

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

In problem A, why isn't a+b+c-1 a possible answer ?

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

94730877 Problem B Can anyone help me to find the bug in my submission, thanks a lot~

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

    Between the 4 values, find the median, not the average. Finding the median gives you the minimal answer. For example, 1 1 1 10. If you use the median, 1, you only need 9 operations. If you use mean, 3, you need 13 operations. I made a similar mistake lol, hope this helps.

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

Can anyone explain the problem A? I don't understand what it mean by "no three of its corners lie on the same line, and it does not cross itself".

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

    In the first case, if 3 points are collinear, then you cannot form a quadrilateral by adding 1 extra point. I think the second is to prevent concave quadrilaterals.

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

If you search in Google "queries in range of lcm modulo", you can find a Codeforces blog in which an user asks for almost the exact statement of problem F from this round, and provides a link to the original problem

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

    Actually offline version can be solved with Mo's Algorithm also.

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

can we solve problem A by trying to give it a shape of trapezium? ceil(sqrt(a[0]^2+(a[2]-a[1])^2) a[] is sorted.

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

    This should work. The initial distance is sqrt(a[0]^2 + (a[2] — a[1])^2). Now, pivot the longer side away from the shorter side. The final distance will be sqrt(a[1]^2 + (a[0] + a[2])^2) when the longest side is parallel to the the shortest side. The final distance is greater than the initial distance. So, we have a continuous function which goes from the initial value to the final value. So, any integer value between the initial value and the final value should work. We may also need to show that the difference between the initial and final lengths is at least 1.

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

When will editorial be posted?

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

Can we solve problem C something like this?

    //dp[i][0] - possibilities with deleted substring ended before i
    //dp[i][1] - possibilities with deleted substring haven't started until i 
    //dp[i][2] - possibilities with deleted substring continuing.. from somewhere to i
    dp[1][0] = 0;
    dp[1][1] = (s[1] - '0');
    dp[1][2] = 0;
    for(ll i=2;i<=n;i++)
    {
        dp[i][0] = ((dp[i-1][2]*10 + s[i]-'0')%mod1 + (dp[i-1][0]*10 + s[i]-'0')%mod1)%mod1;
        dp[i][1] = (dp[i-1][1]*10 + s[i]-'0')%mod1;
        dp[i][2] = (dp[i-1][2] + dp[i-1][1])%mod1; 
    }

I know these are incorrect transitions , but can we solve this problem in this way (using these states)?

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

    I just did this. dp[n][3] means the sum of the current state, also we need to maintain another array cnt[n][3] means how many different way are currently at this state, so we can make the transition by two array. Submission

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

      Thankyou so much for the reply and for the logic as well.

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

who can give me the solution？thanks a lot

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

Would anyone check my code for problem D? it's wrong on the 4th test case. 94750634 thanks.

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

    I think the usage of mark[x] = 1; is wrong. Instead the push onto the queue should be done whenever the relaxation is done.

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

for problem E, this input: aaffdfouurtytwoo shoudln't the lexicographically smallest longest suffix after the operation be dfortytw instead of aadfortytw? Can someone tell me where i misundertand the question? thx in advance.

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

    Lexicographic order is the way you order words in a dictionary, so it first compares the first characters, then the second ones etc.

    Since aadfortytw begins with a instead of d it will be smaller.

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

Can anyone explain my issue in 94735674. I save lcm of [i , i+2^j) in dp[i][j]. I also save the numbers with their factorized form.

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

Does anyone see why this doesn't even pass the sample test case 2? I seem to be following the same method as solutions, but I don't see what's going wrong.

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

    Maybe consider this line in your code:

    		if(n==1000){
			cout<<l+1<<" "<<r+1<<endl;
			return 0;
		}

    Used wrong reply, sorry

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

      I think you commented on the wrong thread.

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

Has anyone tried to solve the version of problem C in which you can delete any subsequence (not only consecutive elements)? At first I thought it was such variant and it turns into a cool problem too.

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

    Is it possible to solve this faster than O(n^2)?

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

      Yes, we can compute the value for each digit. We know that for a digit $$$a_i$$$ (1-indexed) we can choose $$$2^{n-i}$$$ subsequences to the left side (values with power of 10 greater than mine that do not affect my value), regarding the values to my right we know that depending on the number of values that we choose the power of 10 of my value changes, so we can calculate for every quantity we choose in $$$O(n)$$$ (we'll optimize this). The formula is $$${i-1 \choose 0} \cdot 10^0 + {i-1 \choose 1} \cdot 10^1 + \dots + {i-1 \choose i-1} \cdot 10^{i-1}$$$.

      If we simulate the first few values we can see that we get the drawing of the pascal triangle (It can also be seen through simply looking at the formula because each value of the row has a different power of 10). Using this fact we can imagine how we can build the $$$i+1$$$-th row based on the $$$i$$$-th. To do so we can 'shift' the $$$i$$$ left by multiplying it by ten and then add to last one, this way it is noticeable that the values of the $$$i+1$$$ are the sum of two consecutive values on the $$$i$$$ and it follows the recursion the pascal triangle is built upon.

      An argument could be made that when we take each value mod 10 and 'pass one' to the next power (because each item must have at most one digit, but in the pascal triangle there are terms with more than one digit) this idea would break but from what I've seen it (stress test) it doesn't and we can simply calculate this value by taking the correspondent power of 11 ('shifting' one by multiplying by 10 and adding the last one is the same as multiplying by 11). This way if we precompute the powers of 2 and 11 we can calculate the answer to every digit in $$$O(1)$$$ by $$$2^{n-i} \cdot 11^{i-1} \cdot a_i$$$, thus leading to $$$O(n)$$$. This specific problem didn't allow us to take the complete set but we can easily remove this single value in $$$O(n)$$$ too.

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

        No, it is ok. Thanks!

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

          Instead of considering removing k I considered having k left, which would be the same as removing i-k, so the formula you would get is the same as mine but reversed.

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

        Yes, I actually misread the problem statement during the contest and was using the same approach you just described here, and I agree, it would've been a much cooler problem.

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

why editorial is not published yet

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

Can someone please tell me where did I go wrong in this solution for C?? I am taking left and right contribution of every digit but it just isn't working.

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

    For digit at position i (from left side), right contribution is 1 * 10^0 + 2 * 10^1 + ... + (n — i — 1) * 10^(n — i — 2).

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

Eagerly waiting for the editorial of Problem F .

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

It's 10/6/2020 6:05 UTC, 30 hours after the contest, and no editorial is published. Shouldn't editorials be written well before the contest? Or is there some reason that you can't post them online?

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

Is there any possible way to estimate the number of spare nodes to declare when using Persistent Segment Tree ? Or to be exact the F problem, which turned out to consumed up to 4e7 nodes ?

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

    I'm used to counting $$$2 \cdot n + n \cdot log_2(n)$$$. But your solve need more nodes, because you always make new.

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

When is the editorial coming? I really want to see Problem B and C as they were tricky. Tried looking at other peoples solutions, but cant get it

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

Since the round was nice and had interesting problems, they will destroy it by publishing the editorial when your spirit to up solve the problem and learn something new dies -_-

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

shall we even expect editorials for this contest?

→ Reply