Aris's blog

By Aris, 3 years ago, In English

Hello! Codeforces Round 780 (Div. 3) will start at Mar/31/2022 17:35 (Moscow time). You will be offered 6-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

You will be given 6-8 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

  • take part in at least five rated rounds (and solve at least one problem in each of them)
  • do not have a point of 1900 or higher in the rating.

Thanks to NEAR for supporting this round, details can be found in this post.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of our work. Problems have been created and written by ITMO University team: MikeMirzayanov, MisterGu, myav, Gol_D, Aris, senjougaharin and Vladosiya.

We would like to thank: arvindr9, hocky, lucasxia01, Evirir, Sorting, 244mhq, yorky, Jostic11, sansen, leaf1415, Masha237, amr_abdelazim, coderbd, gs17005, nebula for testing the contest and valuable feedback. List of testers will be updated.

Good luck!

UPD: Editorial

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

| Write comment?
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Very nice! Good luck everyone, I wish you high rating. Hopefully I can become blue after this round

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

Finally, div 3 contest. We waited for this 2 weeks)

»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

First unrated div3 for me, yay noice :)

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Very interesing

»
3 years ago, # |
  Vote: I like it +26 Vote: I do not like it

As a tester, make sure to participate in this brilliant contest.

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Always love a good old div3 round.

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

(line 1) You will be offered 7-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600.

(line 6) You will be given 6-8 problems and 2 hours and 15 minutes to solve them.

Is that a typo or you want to confuse us?)

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

    not a typo, just inference. $$$x \in [7,8]$$$ and $$$x \in [6,8]$$$ implies $$$x \in [7, 8]$$$. so there wud be atleast 7 problems and at most 8.

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

      Your interpretation is illogical, because if the number of problems is not mentioned in the first line, there is a possibility that the contest contains only 6 problems, while with its presence this possibility disappeared, This is what m_bolshakov pointed out.. lol

»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Good luck everyone!

»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

div 3 contests on codeforces are as rare as tourist not getting rank 1.

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

It's my first contest since I recovered from COVID-19. Hope I can reach 1400 rating!

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Hope this one's the rating booster!!

»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Excited for my first unrated round!

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

I am going to miss this contest after a contest streak of 22 months

»
3 years ago, # |
Rev. 2   Vote: I like it +44 Vote: I do not like it
  • A: nice and easy, thanks for including 0 2 into samples.
  • B: a bit tricky for its position, but okay.
  • C: nice greedy, even tho not all people proved it.
  • D: the worst problem I've solved in March.
  • E: a bit too easy for its position, definitely easier than D.
  • F: nice observation-based problem.

Nice contest, but D should've been removed or at least switched with E.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    nice greedy, even tho not all people proved it

    what exactly is there to prove?

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

      That you can take the first recurring character into the answer. See 151525744. Also it just came to my knowledge that some people did dp, then yes, there is nothing to prove.

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

    what can be the approach for E

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

      There are only $$$n$$$ possible diagonals, one can explicitly check them all.

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

      Note that any shift, up/down/left/right, preserves the diagonals as they are (if you consider the diagonals as 'wrapping round' when they reach an edge). Find the diagonal with the most 1s on it, say it has X 1s out of a total of Y 1s on the whole grid. Then the answer is (Y — X) + (N — X): the number of 1s off main diagonal is Y — X, and the number of 0s on the main diagonal is N — X.

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

      I observe that after any operation finally what you have to do is choose some row and move downward and check the cost. there are n rows and n operation to check each row.

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

    my solution to f1 is taking 982ms runtime, i think it is hackable, can you please try to hack it Your text to link here...

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

      I don't think that it is hackable unless 982ms comes from re-running your solution several times (CF does that to close-to-tle solutions). From my experiments, the worst case for your solution is simply 3000 minuses. Here is a generator that I used in experiments.

      This is also visible in code, as it takes the longest to run if p<m all the time and condition y-(a*2)<m never breaks early. This is exactly the case of 3000 minuses.

      Some reasoning for why this works fast may be that:

      • you process each substring in $$$1/3$$$ of its length;
      • there are roughly $$$n^2/2$$$ substrings;
      • the average length of a substring is roughly $$$n/3$$$.

      It follows that your solution performs roughly $$$n^3/18$$$ operations, or 1.5 billion, which is not that far off what is usually considered to be acceptable.

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

    how to solve C with greedy?I can only come up with a DP solution

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

      You can take the first recurring character into the answer. See 151525744.

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

      you can solve it without dp like this:

      imagine we want to maximize the # of characters preserved, instead of minimizing the # of deletions. Supposed we want to preserve a pair of some character c, which occurs at indices [i1, i2, i3 ... ] (in sorted order). We would never want to preserve the c's at i1 and i3, because (i1, i2) will give us the same result for fewer deletions.

      So let's consider the adjacent intervals for each occurrence of every character. (i1, i2) (i2, i3) (i3, i4) ...

      Note that if we choose to take some interval (i,j) it means we are preserving the 2 characters at i and j. This also implies, that everything between them is deleted. If that's the case, then the optimal answer which maximizes the # of preserved characters is clearly reduced to: the maximum number of disjoint intervals we can take.

      If we stick all of these adjacent intervals, for each unique character, into a big array, we can run a greedy algorithm to compute the max disjoint intervals taken.

      Here is code: https://codeforces.net/contest/1660/submission/152393885

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

    I agree. Problem D took an hour out of me, and I ended up with an RTE on test 2. 151575805

    EDIT: Thanks for pointing out the greedy approach for C. Like several others, I used DP. 151539005

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

    I think D is a Directly Calculating..

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

    thank for your ideas

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

    I think F2 and D are both a lot easier to come up with than E

    Maybe a severe intuition gap on my part

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve F2? I'm too weak :(

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

    You can use divide an conquer in $$$O(Nlog^2N)$$$

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

    Claim: $$$(l, r)$$$ is good if $$$\text{balance}[r] \le \text{balance}[l]$$$ and $$$\text{balance}[l] \equiv \text{balance}[r] \pmod{3}$$$, where $$$\text{balance}[i]$$$ is balance of prefix $$$s[0..i]$$$. We will count $$$(l, r)$$$ grouped by $$$r$$$. This means counting numbers greater than or equal to something with a given remainder modulo $$$3$$$. I used 3 ordered_sets for this purpose, with balance numbers grouped by remainder, but there is also a linear dp that uses discrete continuity.

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

      Thank you so much! Now I get it :) I thouht too much and didn't solve it even though I came up with the idea of $$$3$$$ QAQ

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

        Why cant u a purple refer to Fenwick Tree??i dont think f2 a hard one since youve done f1

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

          My solution to F1 was too complex so that I constrainted myself in that way :<

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

    3 BITs solves in $$$O(nlgn)$$$.

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

    I think the key observation is that if minus count > plus count + 1, you can always combine some minuses together to makes plus (since they would definitely be minuses adjacent to each other), which simplifies the question greatly because now you don't really need to keep track of the position of minuses and whether they can merge or not. When that idea struck me after trying for a while, the question became rather classic.

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

      Same.

      When I was solving F1, I forgot the limit of adjacent minus signs, but I got an accepted verdict. An interesting thing is that I have even not noticed that the limit is not necessary after that. Then I resubmitted the "corrected" code on F1.

      This minor mistake took me more time to get the right idea of F2.

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

    I made it $$$O(NlogN)$$$ with a segment tree(of course Fenwick tree can also solve it)

»
3 years ago, # |
  Vote: I like it -17 Vote: I do not like it

My approach for F1. Promising String (easy version).

Part 1: A necessary and sufficient condition for a string to be promising.
Part 2: $$$O(n)$$$ algorithm to check the previous condition.
Part 3: $$$O(n^3)$$$ solution to the problem using 2D DP.
Part 4: Optimizing the previous solution to $$$O(n^2)$$$ .

Part 1
Part 2
Part 3
Part 4

Code

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

    I suppose presenting the process of problem solving is often useful for adequate programmers..? Can not understand so many downvotes though some little mistakes in Part 3.

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

      i think downvotes are just because there's an easier way under f1 constraints. Can just brute force it directly without any dp

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do 'C'? I couldn't come up with any solution in two hours

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

      thank you & you are so strong

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

      How do we now if the previous position of i was already coupled with other previous k: k < j < i ?

      For example: "aaa". Here we couple 1 with 0. After that we can't couple 2 with 1 because 1 is already coupled.

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

        You don't need to know that. When you try to couple the current position i with the previous position j, you then look at the answer for the substring that ends at j-1. So for your example the solution will look like this:

        1. Current substring is "a". The answer is 1.
        2. Current substring is "aa". We either delete 1 and add the answer for 0 (1+1=2 total deletions), or couple 1 with 0 (0 total deletions)
        3. Current substring is "aaa". We either delete 2 and add the answer for 1 (1+0=1 total deletion), or couple 2 with 1 and add the answer for 0 (0+1=1 total deletions).
  • »
    »
    3 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    For any character at a position i , you can only do 2 things.
    a) Remove the ith character b)Pair up ith character with the next index j , such that j>i AND s[j]==s[i].

    Now , you can write a recursive function to do the same and memorize it for the constraints.

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

    Greedily selecting pairs of same characters traversing from left to right to not be deleted, and removing the rest was what worked for me. My intuition was that it would never be better to remove the "closest" pairs of same characters, because in doing so we'd be removing 2 characters just to merge 2 other characters. I don't have a proof for this though.

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

    if you're interested, you can solve it without dp like this:

    imagine we want to maximize the # of characters preserved, instead of minimizing the # of deletions. Supposed we want to preserve a pair of some character c, which occurs at indices [i1, i2, i3 ... ] (in sorted order). We would never want to preserve the c's at i1 and i3, because (i1, i2) will give us the same result for fewer deletions.

    So let's consider the adjacent intervals for each occurrence of every character. (i1, i2) (i2, i3) (i3, i4) ...

    Note that if we choose to take some interval (i,j) it means we are preserving the 2 characters at i and j. This also implies, that everything between them is deleted. If that's the case, then the optimal answer which maximizes the # of preserved characters is clearly reduced to: the maximum number of disjoint intervals we can take.

    If we stick all of these adjacent intervals, for each unique character, into a big array, we can run a greedy algorithm to compute the max disjoint intervals taken.

    Here is code: https://codeforces.net/contest/1660/submission/152393885

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what was the website showing smallest countertest to submission?

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

    You called? :)

    Will be adding the problems from this contest in an hour or two. Stay tuned!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

any hint to solve C?

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

    Let $$$dp[i]$$$ denote the minimum number of deletions to make string $$$s[0..i]$$$ even. Then you can either delete $$$s[i]$$$ (corresponding to $$$dp[i-1]$$$), or you can match $$$s[i]$$$ with another $$$s[j]$$$ where $$$j<i$$$ and $$$s[j]=s[i]$$$. Now how can find that $$$j$$$ by doing preprocessing?

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

    Work greedily on segments When s[i] == s[i+1] increment i by 2 when i == n-1 increment res by 1 When s[i]!=s[i+1] Now try to search for two chars in a segment that are the same like here mbacb two b are there So we will remove mac here

    Simply to search whether there are two same chars we can use set If we found one then res will be inc by window_size — 2 otherwise, res will take that entire window.

    This was my approach. I hope it doesn't get hacked 151529755

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

    greedy approach: if s[i]==s[i+1] you move to s[i+2]. else you choose to either remove the whole remaining string, or match two characters. To match two characters iterate through every character c from 'a' to 'z', then find the next occurrence of c and the next next occurrence of c and in order to match the two characters you will remove every character before the first occurrence of c and every character in between the first occurrence and second occurrence of c.

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

    if you're interested, you can solve it without dp like this:

    imagine we want to maximize the # of characters preserved, instead of minimizing the # of deletions. Supposed we want to preserve a pair of some character c, which occurs at indices [i1, i2, i3 ... ] (in sorted order). We would never want to preserve the c's at i1 and i3, because (i1, i2) will give us the same result for fewer deletions.

    So let's consider the adjacent intervals for each occurrence of every character. (i1, i2) (i2, i3) (i3, i4) ...

    Note that if we choose to take some interval (i,j) it means we are preserving the 2 characters at i and j. This also implies, that everything between them is deleted. If that's the case, then the optimal answer which maximizes the # of preserved characters is clearly reduced to: the maximum number of disjoint intervals we can take.

    If we stick all of these adjacent intervals, for each unique character, into a big array, we can run a greedy algorithm to compute the max disjoint intervals taken.

    Here is code: https://codeforces.net/contest/1660/submission/152393885

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Were the problems too easy?
First time AK'ed any div3. contest.(Hoping I won't FST)
Thanks for the problemset.

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

    Actually I only solved A and B

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

    Far from it, I'd say. C and D were quite difficult by Div 3C and Div 3D standards. I solved C with dynamic programming and D with a relatively fiddly implementation. There may have been easier ways to do it, but I found them far from trivial. Then E and F1 were much easier. That was strange! A fun contest.

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

    It feels so, because its the first time I also AK'ed a Div3 without a single wrong attempt!

    Maybe E should've more harder.

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

    Also my first AK.I think the difficulty of the questions is more average.ABC is not that easy and EF is not that difficult.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is the time limit for question d, can someone help me take a look, I think it is O(n)Your text to link here...

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

    i'm sorry that your solution works in $$$O(n^2)$$$ because of the first line in f()

        while(l<=n&&a[l]==0)l++;while(r>=1&&a[r]==0)r--;
    

    when a[] are all zero, l will run to n+1 and r will run to 0.

    That costs O(n) each time, and it will process n times.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can you give me test case for problem D . https://codeforces.net/contest/1660/submission/151583999 I can't find why it gets wrong answer.

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

What was test case 14 in D

Can someone provide me a corner case for this solution?

My approach was to calculate the maximum product subarray ending index then, remove n-that_index-1 elements from the array after that pop element and check their product when product == max product print size of the remaining array.

151575450

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

    bro u cant just multiply the numbers as if we have 100 numbers 2 in our array so ur code will calculate 2 power 100 which is a very huge value and cant be stored so u should have calculate the frequency of 2 or -2 in spite of product because only frequency of abs(2) matters in the products

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

    $$$2^{200000} = $$$ overflow.

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

    I want to bang my head against wall :)

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

    You can probably still do it this way using this property: log(a*b) = log(a) + log(b) to avoid overflow errors.

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

My solution to problem D:

It's easy to find that the final product must be positive,so we can divide the sequence by every $$$0$$$.

For each subsequence:

If the product is negative,find the far left negative number and the far right negative number,compare their results and shorten the subsequence. It is easy to see the product must be postive after this operation. When we compared the subsequences,we only need to pay attention to the $$$2$$$ and $$$-2$$$,so we can use prefix sum to solve it.

Finally we check all the subsequnces and find the best answer.

The solution is $$$O(n)$$$.

Pardon me for my bad English :(. You can try to connect the code to understand it.

code
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    tfw solved it but used a prefix product array and thus overflowed. Feelsbad

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

    I tried that, but couldnt figure out the reason for tle

»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Definitely, one of the best contest i have given so far. Expecting to become specialist once again!!

Great questions by the setter and good strong test cases. Thank you!!

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Love Aris

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Is it possible to hack the slow solutions of problem F1?

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I think problem C is the hardest problem. I use 22min on it.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think this div 3 round should be declared div 2.

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

    I think it is of medium difficulty in div3s.

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

      Just the way the first 2 questions of div 2 are doable at least the first three questions of div 3 should be doable. But, the number of submissions is telling a different story.

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

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table to increase/decrease the constraints.

I've also added a new feature to view progress of your judgement in near real-time. (For example, the current state of your ticket, how many inputs were evaluated, etc).

If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.

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

Learning From Mistake (Mistake 4)

Initially, After getting the usual wa on test 2, I tried another approach 151583179, which gave a runtime error on test 15. I went around stress testing as to why is giving Runtime error, and spent way too much time on it.
After the contest, I tried to print the error 151598207 and it was this
In python, int does not have an upper bound on size (It depends on the system), but float does. Float has an upper bound, which can be checked using sys.float_info.max. I did not know it. It cost me an AC. After replacing the / with //, It 151598360 gave an AC. How foolish of me!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Bruh... Managed to only solve B and A, failed at C. Now tried E and solved it within a couple of minutes. I think I am just a total disgrace at DP. Could anyone recommend me a way to master on problems of this tag?

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

    if you're interested, you can solve it without dp like this:

    imagine we want to maximize the # of characters preserved, instead of minimizing the # of deletions. Supposed we want to preserve a pair of some character c, which occurs at indices [i1, i2, i3 ... ] (in sorted order). We would never want to preserve the c's at i1 and i3, because (i1, i2) will give us the same result for fewer deletions.

    So let's consider the adjacent intervals for each occurrence of every character. (i1, i2) (i2, i3) (i3, i4) ...

    Note that if we choose to take some interval (i,j) it means we are preserving the 2 characters at i and j. This also implies, that everything between them is deleted. If that's the case, then the optimal answer which maximizes the # of preserved characters is clearly reduced to: the maximum number of disjoint intervals we can take.

    If we stick all of these adjacent intervals, for each unique character, into a big array, we can run a greedy algorithm to compute the max disjoint intervals taken.

    Here is code: https://codeforces.net/contest/1660/submission/152393885

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

when i try to hack a solution i received an Unexpected verdict, what it means?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

First contest, big thanks to the writers and testers! For problems that I struggled with, what is the best way to get guidance? Thanks!

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

    You can wait for the editorial thread or just ask here.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      When do editorial threads post?

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

        Within 24 hours typically.

        Sometimes the threads are posted immediately after the contest but for Div3/Educational I think they wait at least after the hacking phase (12 Hours).

        Also the ratings are updated at more or less the same time.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am getting TLE on problem D please help!! submission : link

»
3 years ago, # |
  Vote: I like it +43 Vote: I do not like it

My speedrun and video solutions to all problems is available here on my youtube channel for anyone interested.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Commemorating my first time to solve all tasks in a contest.

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

Please if someone can help me with Problem D, my code computes the first and last index of the subarray. I can't find anything wrong with it (Overflow shouldn't be a problem because Python supports arbitrarily large integers). Submission: 151614920

Nevermind: ...empty product has value 1. But still got TLE despite O(N). Guess large products are costly.

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

    Python's large integer operation is slow when the integers are extremely large.Don't use that.You can express it as $$$\pm 2^x$$$ instead.(sorry for my poor English

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

    Maybe the value of cur overflows.

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone explain me the intuition of MAP solution in C prblm ?

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

    I believe it comes from thinking of those elements left in the map as being unavailable for the upcoming letters in the string or that they shouldn't be matched with any of the upcoming letters as this will break the order of the string.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am getting TLE on problem D please help!! submission : link

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

F1 and C should be interchanged

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it unrated really, can anyone please reply ?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello. I have a rating under 1600, and I believe I am a trusted account. But last night, when I participated in this contest, my ratings didn't change. Can anyone help me understand what happened?

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

    I satisfy the conditions too but my rating didn't change too idk what happened

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

      What should we do? How do we attract the attention of CF authorities?

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

        It seems that no participant got a change in their rating, idk if it is true If any samples which conflicts my opinion just reply me

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

    Just wait. The ratings will be updated within few hours since there was a hacking phase after the contest that's why it's taking time.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where is the solution?

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

    You can read other people's code(in status) and try to understand the correct solution until the official solutions.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me why am I getting wa on testcase 2? Here is my submission : 152264434

Approach : get all segment without zeros , and try to find the best answer from those segments .

any counter example would be so much helpful

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

Someone has spammed the problem tags for F2 — if anyone has tag edit access and can undo it that would be good.

UPD: resolved, thanks

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why this submission TLE? I think it is right and I have submitted after the contest, however, it was Accepted. Could anyone give me a hand?

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

I have a problem with the problem D. In contest time I got "Accepted". But now I got "wrong Answer" in the same test case (Test case 2). So, why I didn't get "WA" in contest time. I still had 10-15 minutes. Please help me with this situation.

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

    Maybe it's because in the hacking phase somebody else's solution was hacked and then that hacking test was added to the rest of the other D tests, and your solution fails the test

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

      NO. It's not like that. The test case existed before. The test case was -

      1 0

      For this I printed "0 0", it got accepted in contest time. But now I am getting WA.

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

        Maybe the original checker was wrong and got fixed.

        From the problem statement:

        The product of elements of an empty array (array of length $$$0$$$) should be assumed to be $$$1$$$.

        So for this testcase:
        Another testcase:
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I know. But my point was if I got a correct verdict in contest time maybe I could solve the problem. But I didn't. I got the correct verdict in system testing. Why ? I am the one who suffered.

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

            The world is not perfect. Sometimes mistakes happen.

            Do not take it too seriously. Maybe you could have gained a bit more rating, but others would have been better too, so maybe not. Anyway, do a few more contests in the future and your "suffering" will be forgotten.

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

      The test case was 2. It was already in the pretest. From my previous submission I can see that my answer for that case wasn't considered wrong.

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

        exactly same happened with me, my code gave 0 0 on test case 1 0, which is indeed wrong ans due to a typo but during the contest it showed accepted, so i didn't checked it again, but now its wrong ans on test case 2, i had 10 -15 min remaining when i submitted D, i could have corrected my solution

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why haven't the rating changes been applied yet?

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

    Me too.

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

      I've waited for a long time! Is it a trick on April Fool's Day?

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

        It's usual for div3 and educational rounds

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

when will I get my score

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone tell me the solution of C problem without dp

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

    Work greedily on segments When s[i] == s[i+1] increment i by 2 when i == n-1 increment res by 1 When s[i]!=s[i+1] Now try to search for two chars in a segment that are the same like here mbacb two b are there So we will remove mac here

    Simply to search whether there are two same chars we can use set If we found one then res will be inc by window_size — 2 otherwise, res will take that entire window.151529755

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

    Greedy.

    Make same letters into pairs $$$(l,r)$$$

    For each time,choose the pair that the $$$r$$$ is minimal.

    Pardon for my bad English,you can see the code to understand it better :p

    https://codeforces.net/contest/1660/submission/151537948

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

      can you please explain in more detail..i will be grateful

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

        We turn the problem into choosing most identical letter pairs that the letter pairs don't be staggered (Formally,if the pair $$$(l1,r1)$$$ and $$$(12,r2)$$$ are in the answer set and satisfy $$$l1 < r1$$$,then $$$r1 < l2$$$ must be hold. ) You can simulate some examples to understand this.

        Then we consider to work it out greedily.

        It is easy to see,for each time,choose the pair that $$$r_x$$$ is the minimal must be the best choice.So we can sort the pairs by $$$r$$$,and traverse them to calculate the answer. It can be proved that the answer is correct.

        I tried my best but my English is really poor QaQ

        code with explaination
»
3 years ago, # |
  Vote: I like it +27 Vote: I do not like it

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

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

wtf no editorial till now!!

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Today I received the following message: Your solution 151546638 for the problem 1660C significantly coincides with solutions xabialonso14/151529962, Mukundan314/151534091, harshgoyal185/151546638, skhan_org/151548513, rajeshpenugonda6/151566978, raushnn/151568699, Aksnov/151569233, RishabhVarshney/151570560.

But these solutions are different (eg. submission by Aksnov 151569233 and my submission 151546638). The reason for coinciding is the use of the Python FastIO template used by all the users stated above. But the use of the FastIO template is permitted as the template is publicly available and was published before the contest (template link). The main logic of the solution is different.

So, MikeMirzayanov please look into this and do the needful!

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I received the following message. Your solution 151524331 for the problem 1660C significantly coincides with solutions ttttan/151524331, mayocorn/151541772.

The reason for coinciding is the use of AtCoder Library (ACL blog link). ACL is the official source code. I always use much of the ACL source code, and mayocorn also do the same thing. Please look at these codes(151524331,151541772). I used dynamic programming (dp) for the problem, but mayocorn solved differently. The main logic of these solutions are different.

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

Hey @MikeMirzayanov I have got a plagiarism for my solution for question C because unknowingly I used ideone.com for writing and compiling my code in the public mode. This led to the leakage of my code and thus my code matches significantly with many other people as mentioned to me in the mail. So, I request you to please rollback my rating changes as this happened to me unknowingly. I would really appreciate if you consider this for once and I can assure that this won't happen again.

Looking for your reply.

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

My solution 151559424 for the problem 1660C “langminjie/151559424”,I submitted it earlier than "Ac1dX/151581662".I do not know Why it be same,and I wrote this code by myself. Why it skipped me?

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

Attention!

Your solution 151570560 for the problem 1660C significantly coincides with solutions xabialonso14/151529962, Mukundan314/151534091, harshgoyal185/151546638, skhan_org/151548513, rajeshpenugonda6/151566978, raushnn/151568699, Aksnov/151569233, RishabhVarshney/151570560. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.net/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

I have received this message. If you have looked in the code, we all have used the same template from https://github.com/cheran-senthil/PyRival Also I have uploaded the same template on my github https://github.com/rishabhvarshney14/Competetive-Coding/blob/main/template/pypy.py. If you look at our main function, the code along with the logic is quite different.

I hope this can prove that I didn't cheat.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I've received this morning your message about identical solution with some other competitors of problem 1660C(my solution is 151529962), but I think it was just common use of greedy algothrim. It's not a cheat but a coincidence. Looking forward to your response.

»
3 years ago, # |
  Vote: I like it -6 Vote: I do not like it

About Round#730 Div-3 I got a message that my code is similar to Firewarden07. But iftakheralam01 and Firewarden07 both are my accounts. please check I also comment from that account.

This is my second account

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

    Multiples submissions on different accounts during the same contest ... Trying to dodge some submission penalties...? (yep, I'm accusing you of cheating, and if you're not, why using two accounts for the same contest?)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In 780 div3,My solution 151559424 for the problem 1660C “langminjie/151559424”,I submitted it earlier than "Ac1dX/151581662".I wrote this code by myself.that means I do not copy anyone code, why my rating has dropped, it's not fair for me.I have sent a Message to the MikeMirzayanov and also sent a statement but no one told me how to fix this, can anyone tell me what to do?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone help me to solve F2 using ordered sets or segment trees I am not aware of Fenwick trees

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F2 using fenwick tree?

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

Even though I did not use online IDE for the contest and neither did I discuss or send my solution to someone else I got a message from codeforces that someone has copied my solution for Problem C and I received a warning.How is this possible??

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

arvindr9, hocky,Evirir,Sorting,244mhq There was an issue of false plagiarism detection due to template.

"My solution 151568699 for the problem 1660C significantly coincides with solutions xabialonso14/151529962, Mukundan314/151534091, harshgoyal185/151546638, skhan_org/151548513, rajeshpenugonda6/151566978, raushnn/151568699, Aksnov/151569233, RishabhVarshney/151570560."

Can you please review and rectify it as soon as possible. It has been more than 10 days.

Thank You.

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

    Testers are just random users being asked to try solving the round and have nothing else to do with the contest so we can't do anything. Tbh I don't know who you should ask to solve this problem though...sorry about that. I did look at the submissions and it does seem to be a mistake from the plagiarism detector.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

As old as this contest is, I had difficulty with understanding why the greedy solution to problem C works and I've just now come up with an explanation that is intuitive for me. Hoping that it helps others in the same boat as me.

The reason why we always prefer to preserve the pair in nested sets of pairs that is finished off first (As in, if we were going over the string "abcdab," we would choose to keep the pair of a's and delete "bcd" instead of keeping the pair of b's as the second a is at index 4 while the second b is at index 5, or if we were going over the string "abccab," we would choose to keep the pair of c's and delete the ab's as the second c is at index 3 while for a and b, it's index 4 and 5 respectively.) is because it's always more profitable than the other options: If you bring the halves of the earliest ending pair together, then anything after that pair will be free afterwards, giving you the most freedom-- should you choose a pair that is closed off later, you might lose a potentially profitable link. The potential profit you make off of bringing together the earliest ending pair and any other is the same-- you save up on two characters, so why choose any pair that closes off more opportunities?

This approach reduces this problem into a derivative of what's known as The Activity Selection Problem, you can search for it if you'd like to read about it in more detail.

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