MarkBcc168's blog

By MarkBcc168, history, 2 years ago, In English

Thanks for participating. We apologize for problem F that has appeared before. Still, we hope you all enjoy our round!

1705A - Mark the Photographer

Author: MarkBcc168

Hint 1
Hint 2
Tutorial
Code

1705B - Mark the Dust Sweeper

Author: MarkBcc168

Hint
Tutorial
Code

1705C - Mark and His Unfinished Essay

Author: MarkBcc168

Hint 1
Hint 2
Hint 3
Tutorial
Code

1705D - Mark and Lightbulbs

Author: MarkBcc168

Hint 1
Hint 2
Hint 3
Tutorial
Code

1705E - Mark and Professor Koro

Author: abc241

Hint 1
Hint 2
Hint 3
Hint 4
Tutorial
Code (Bitsets, by errorgorn)
Code (Lazy Segment)

1705F - Mark and the Online Exam

Author: MarkBcc168

Unfortunately, a harder version of this problem has appeared in a Chinese contest here and here. You can look at their solution here. We thank many contestants who pointed it out.

Hint 0
Hint 1
Hint 2
Hint 3
Hint 4
Tutorial
Code
  • Vote: I like it
  • +121
  • Vote: I do not like it

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

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

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

Can you continue in the sun time next time?

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

So fast Editorial...Love it.

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

    The editorial with hints is excellent :)

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

C was nice

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

A and B were normal. C was kinda nice. D felt kind of easier than normal.

»
2 years ago, # |
  Vote: I like it -12 Vote: I do not like it

why my solution is giving memory limit 164324383

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

    C in that problem can be up to 40, so the string can have a length of up to n times 2 powered by 40. That is because the string can be "duplicated" if they simply spam 1 as L and the current length of it as R, so it becomes twice as big. But you can not make a string of that size, because it takes too much memory, so you get MLE.

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

    l, r⩽10^18, means r-l ⩽ 10^18 this is already a large value, even if we do not take into account that q can be of the order of 10^4

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

For C: https://mirror.codeforces.com/contest/1705/submission/164336489 why this code give TLE. and how to remove TLE? please tell

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

    Note that the length of the string can be upto $$$2^{40}\cdot 200000$$$ because the copying operation could be $$$[1,n]$$$, $$$[1,2n]$$$, $$$[1,4n]$$$, $$$\dots$$$, $$$[1,2^{39}n]$$$.

    Your solution has a loop from l to r, which varies by the length of the string. Therefore, it can never loop through in time.

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

Good Tasks for Codeforces Round #807)

Editorial is perfect.

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

So fast Editorial!!!!!

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

Problem C was just awesome <3

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

Thanks for the superfast editorial, interesting round with mArK!

»
2 years ago, # |
  Vote: I like it +5 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 (or edit compressed parameters) to increase/decrease the constraints.

Disclaimer: There is a quota of 1 request per 24 hours on the free plan.

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

Hints are always helpful.

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

Wow, very fast editorial! I like this contest because the problems are easy to understand. Great job!

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

I thik C is very nice

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

So fast Editorial!!

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

Question D is so difficult

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

Amazing tutorial! It made me everything easy to understand.

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

very terrible contest. C easier than B and too easy. F appeared before. E is DS. In F you get the same result when Wrong Answer and when too many queries. Downvoted. why do you all say quick editorial? does it make the contest less bad in any way?

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

    wheather a problem is easy or not depends on personal opinions,ds is good,it's not easy to find out F appeared before

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

The tutorial for D "Moreover, if a1,a2,…,ak are the positions of 1's in s and b1,b2,…,bk are the positions of 1's in t. " , should here s/t be s¯¯¯ and t¯ ?

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

    Great catch! Fixed.

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

      In problem F editorial

      • If the difference is +1, then both answers must be F.
      • If the difference is −1, then both answers must be T.

      should we replace ±1 on ±2?

      By the way, do you know an algorithm which finds all answers faster than 2n/3 questions (without randomization)? just curious

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

        Fixed, thank you.

        The Chinese problem linked above has a much stricter query limit. I haven't checked their solution yet, so I cannot guarantee that it gives a faster deterministic algorithm. Feel free to check it out!

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

which topic i should learn for solving problems as C?

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

    There is no specific knowledge required to solve C. You can try reading the hints and tutorial provided above.

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

      ok i got it but always i solve A, B in div2 but i cant solve any C problem in div 2 could you give me some tips for improving) thx

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

        the best way to improve at problems like div2C is through problem solving and gaining experience

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

        Practice more div2Cs would be OK.

        Try to solve them as quickly as you can.

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

    C is just about implementation

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

    I though the observation that for each query you have to travel back through the (c<=40) operations was the hardest part.

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

It was super hard for me. I should do more practice

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

it's funny how bitset codes pass (in E) but my std::set solution TLE'd until i replaced them with fenwick trees

desperate pretentious and angry comments
»
2 years ago, # |
  Vote: I like it +61 Vote: I do not like it

D was really good. I don't know why I find such kinds of problem a bit hard. I wasn't able to come up with the invariant that sum of $$$(01)$$$ and $$$(10)$$$ is constant. Can someone suggest set of problems like $$$D$$$ (where I need to recognise an invariant)?

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

    Same bro :(

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

    It is easy to come up with solution for D by observing carefully.

    1. Say we have 10001 then we can convert it to 11101 -> the first block of 1 got expanded to last continuous 0 we had

    2. Say we have 11101 then we can do the opposite and convert it to 100001 -> the first block of 1 got compressed to first continuous 1 we had

    This is for left to right . U can observe similarly for right to left. Now this implies that if i have some block of 1 i can always expand(through continuous zeroes and stop before last zero) or compress it(through continuous ones and stop after 1st one). So we can easily notice that -1 case will be when count of blocks of 1 in s and t are different. Also there is that case for first and last character to be same which can also be deduced by the observation since when expanding [x,y] to [l,r] (l<x , r>y) element at l and y will never change.

    There we you can now just expand and compress these blocks greedily and make them same now.

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

    Same

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

    One perhaps easier solution is, if you separate the bit string into substrings containing either only ones or only zeros, you realize that the operations we can do only allow for moving borders between neighboring substrings. Then the solution exists only if the order of the substrings is matched and the minimal number of operations is calculated by differences in positions of borders of the substrings.

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

    I think the invariant that the number of chunks of 1 stays the same is easier to be observed.

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

    Same for me :/

    After the contest I continued to try and solve D and was surprisingly able to come up with a constructive solution that works, but it was hell to make. As a new expert who hasn't solved that many Ds before I was very pleased to read the editorial and realize that what I did wasn't the expected smart solution.

    Here is my code (it isn't pretty, but I will never touch it again): 164362277

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

    I only solved that problem b/c I saw 3+ similar problems in the past and I knew which direction to push my solution in, if that makes any sense.

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

    This could be helpful: https://mirror.codeforces.com/blog/entry/85172 (there is one problem with an invariant)

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

So fast editorial and fantastic contest!

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

C was kinda hard for me, but I really enjoyed solving it. Great problem

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

Thanks for the fast tutorial ...

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

Enjoyed this contest — definitely has a good math olympiad flavor to it (both problems and solutions)!

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

Does qn D answer overflow int ? passed three pretests then failed.

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

    The maximum possible answer is on the order of n^2, so yes, there is an overflow, and you have to use long long.

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

      Yup that was the problem,felt horrible to lose a qn like that,also i feel the bitmask soln is over complicated,all i did was checked that first and last same,the number of continuous groups of 1 same ,since a group of cont. ones can never split up or merge with another group of ones,then check if number of groups in s and t same ,then calculate distance by moving start and end points of each group in s to corresponding one in t.

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

C was bit tricky for me, Good problemset overall. Happy Coding & Happy friday :)

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

This contest was great, I wish I hadn't had classes until 8:45pm (quite sad). Anyways, that's a rapid editorial.

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

Thanks for fast tutorial and E was cool.

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

Does somebody have binary search solution for C?

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

Fun fact: something happened during testing of problem F related to different behaviours of different versions (and 64-bit or not) of g++ and we couldn't figure out the reason behind it, so I'm putting it here to see if anyone can offer some insights into the different behaviours, thanks in advance :D

This submission gets AC:

Submission

But when I submit the same code in non 64-bit version, it gets WA:

Submission

But once again when I remove two lines from the header it gets AC again, however, those two lines don't seem to be relevant at all to the algorithm:

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

    It has to do with unsigned ints, in this case vector.size(). Casting all .size() values to int in the second submission makes it AC.

    Here's what I think is happening here:

    The first submission passes since you are dealing with 64-bit numbers on both sides, so converting unsigned to signed you get the same number even after overflow, so == works ok. Likewise for the third submission with 32-bit numbers.

    For the second submission, you convert a signed integer to an unsigned one in 32-bit (after some possible overflow), which is not the same as the signed int in 64-bit, so == doesn't work as intended. Removing #define int long long fixes this.

    Moral of the story: always cast .size() to a signed int to avoid situations like this.

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

    [unrelated] why are you removing the legendary line :(

    #define ick cout<<"ickbmi32.9\n"
    
»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

isn't the TL on D too tight?

My code with long long int gives TLE but when I change long long int to int, it passes in 600ms.

My solution is $$$O(nlog^{2}n)$$$. Was this done on purpose to cut the solutions of this logistic?

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

    Based on our testing, the segment tree has a high constant factor that an $$$O(n\log^2 n)$$$ is very hard to pass. You should either use bitsets or aim for $$$O(n\log n)$$$. We apologize for the strict TL.

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

    But $$$O(n log^2 n)$$$ is too much for a problem, that can be solved in linear time, so it's quite ok that your solution TLE-d.

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

      I disagree, the $$$O(nlog^{2}n)$$$ solution was more obvious to me. I couldn't come up with that observation.

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

    Can you share your Approach towards problem D?

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

E, I would like to read a simpler version of the paragraph starting with "Proof: The upper bound is pretty clear...".

What is the upper bound here? What exactly is decreasing?

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

    This was written when there was the second operation (of deleting numbers). The editorial is updated now. Hope this eliminates your confusion.

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

I'm very bad with segment trees, so I came up with the following solution for problem E. Let's maintain two sets $$$S$$$ and $$$T$$$ ("positive" and "negative" sets) such that

$$$\sum 2^{a_i} = \sum_{s\in S}2^s-\sum_{t\in T}2^t.$$$

The following properties should hold:

  • No number appears in both $$$S$$$ and $$$T$$$.
  • The largest element of $$$T$$$ (if it exists) is not equal to the largest element of $$$S$$$ minus $$$1$$$.

The second property is important because it allows us to answer queries by taking the largest element of $$$S$$$ and subtracting $$$1$$$ if the largest element of $$$T$$$ is greater than the second largest element of $$$S$$$. (If the property didn't hold, we might need to deal with something like $$$2^6-2^5-2^4$$$.)

To add $$$2^x$$$, do the following:

  • If $$$x$$$ is in $$$T$$$, cancel it out.
  • Otherwise, if $$$x$$$ is not in $$$S$$$, add it to $$$S$$$.
  • Otherwise, remove the copy of $$$x$$$ in $$$S$$$ and add $$$2^{x+1}$$$ instead (recursively).

Subtraction is entirely analogous. To maintain the second property, just check if it doesn't hold and if so, delete $$$x$$$ from $$$S$$$, $$$x-1$$$ from $$$T$$$, add $$$x-1$$$ to $$$S$$$, and check the property again.

For all of these operations, we can do an amortized analysis by using $$$|S|+|T|$$$ as a potential function. The overall time complexity is $$$O((n+q)\log n)$$$ since we use sets to maintain the maximum.

The implementation of this is very easy compared to the other solutions.

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

    In the complexity, how do you account for the 'recursive' updates? Is there a bound on the number of updates? (a constant factor maybe? Certainly not just $$$n + q$$$ updates)

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

      That's what the amortized analysis handles, because all the extra steps that we do will reduce the value of $$$|S|+|T|$$$. You should be able to find some resources by searching "amortized analysis" and "potential method".

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

Other simpler in understanding approach for D: (TC: O(q*n*logn)):

  • s==t -> ans=0
  • basic check s[0]!=t[0] or s[n-1]!=t[n-1] -> ans=-1
  • create can_toggle[i] = (s[i-1]!=s[i+1])
  • want_toggle[i] = (s[i]!=t[i])
  • iterate from 1 to n-2
  • if want_toggle[i] = false, move on
  • if want_toggle[i]=true -> get id>=i such that can_toggle[id]=1 (can use binary search or monotonous can_toggle queue too)
  • if no such id present -> ans=-1
  • revert all want_toggle between i and id (i.e say add 1 to range[i,id] or other way xor with 1 for [i,id]) (use Binary index tree/segment tree Logn comes from here)
  • ans += range[i,id] i.e id-i+1;
  • using can_toggle[id] we reverted state of can_toggle[id+1] too, add this can_toggle[id+1] to our consideration if its true
  • TLDR: for each want_toggle[i] we get just right can_toggle[i] and bring that can_toggle to current i by toggling id, id-1, id-2.....
  • Idea comes from fact that when we use toggle at i the state of can_toggle[i-1] and i+1 changes.

Submission: https://mirror.codeforces.com/contest/1705/submission/164342095

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

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

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

C is a nice implementation problem. It also gave me a lesson:

BE EXTREMELY CAREFUL using int when you see anything like $$$x \le 10^{18}$$$ or $$$x \le 10^{12}$$$ . I literally spend ~1h struggling on C because of this :(

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

Can anyone please explain why for problem C, there is a runtime error in my solution. solution

.......got my mistake.(solved)

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

    Coz of integer overflow. You need to use long long. Made the same mistake :")

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

Nice contest! Thanks for the fast editorial! :)

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

I followed the editorial solution but I'm getting error for a particular test case that isn't even visible and I can't figure out why. Any help!? Here's my solution: https://mirror.codeforces.com/contest/1705/submission/164347601

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

PROBLEM can someone plz explain why this code didnt work!! please

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Spoiler (Problem C)
»
2 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Why is it TLE?

164335406

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

Funnily enough, in E, I never realised that we are just maintaing a binary number. The final algorithm you get is very similar to the editorial, albeit slower by a constant factor.

Here's what I did, let $$$f_x$$$ be the frequency of $$$x$$$ on the blackboard. Let $$$g_x$$$ be the maximum possible frequency of $$$x$$$ after some operations. It's easy to see that $$$g_x = f_x + \lfloor g_{x - 1} / 2 \rfloor$$$. The answer is simply the largest $$$z$$$ such that $$$g_z$$$ is non-zero.

Now, if we can somehow efficiently maintain $$$g$$$ after $$$f$$$ increases/decreases by $$$1$$$ we'd be done.

Suppose we decrement $$$f_x$$$ by $$$1$$$. Consider what happens to $$$g$$$, let's call it $$$g'$$$ after the change. Obviously $$$g_y' = g_y$$$ for all $$$y < x$$$, and $$$g_x' = g_x - 1$$$. What about the following values?

$$$g_{x + 1}' = f_{x + 1} + \lfloor g_x' / 2\rfloor = f_{x + 1} + \lfloor (g_x - 1) / 2\rfloor = \begin{cases} g_{x + 1} & g_x\text{ is odd}\\ g_{x + 1} - 1 & g_x\text{ is even} \end{cases}.$$$

In the former case, we don't need to propagate the changes any further, in the latter case, it's as if we reduced $f_{x + 1}$ by 1 and the process repeats.

In effect, we find the maximal interval $$$[x, r)$$$ such that $$$g_y$$$ is even for all $$$y \in [x, r)$$$ and then reduce $$$g_y$$$ by $$$1$$$ for all $$$y \in [x, r]$$$. Similar thing happens on incrementing $$$f_x$$$.

We can maintain all this information using two lazy segment trees, one storing $$$g_x$$$ and $$$g_x \text{ mod } 2$$$ on the leaves, and their sum in the internal nodes. The first segtree supports range increment, and the second range flip operation.

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

Can someone please recommend some problems similar to D?

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

problem C can anyone tell me why my solution is giving runtime error[submission:164331309][click here](https://mirror.codeforces.com/contest/1705/submission/164331309)

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

Why is my solution for C throwing a memory limit exceeded error?

I am iterating over the queries and splitting the queries with length > n as subcomponents and evaluating the final answer.

I am essentially generating 40 * 40 * 1000 (q^2 * TC) query ranges for each test case which should still pass the given memory limit right?

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

I don't get how to convert E to those binary numbers ? I mean i get the part for the sum being constant. But what about the condition of first number in the streak of 1's appearing more than once?

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

Does anybody have the same idea with me? it got a Memory Limit Exceeded 164356635

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

    I'm trying to enumerate the all indexes for lowercase chars

    m['a'~'z'][po1, po2, po3] when the query gives me a pos, I will search it and return the char. I think the pos array is too large

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

      It doesn't change that much storing the position that each element of the final string is equivalent to in the original string (as you are doing) and just constructing the final string, because in both instances you are storing the equivalent of the final string's length in elements, which can be up to 10^5 * 2^40 (n duplicated c times) a.k.a: way too much.

      So your guess is correct, the position array is getting too big.

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

Thanks for the superfast editorial, interesting round with mark!

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

For problem B, I started traversing the array from the second last element(n-1th for 1 Indexing). If the element is 0 and the previous element is a non-zero element, then that particular 0 will contribute in reducing the non-zero element. Thus, it will take two steps to reduce that 0 to 0 again(0 to 1 and again 1 to 0). So add 2 to the answer. If the element is non zero, then first decrement that element with the number of steps taken by the 0 element(if any) which was present next to it. Now, the dust remaining at that index is the actual dust which require individual steps to get reduced to zero. So add that number to answer.

Here is the code for the same.

include

include<bits/stdc++.h>

define ff(i,n) for(int i=0;i<n;i++)

using namespace std;

void solve(){

int tc; cin>>tc; while(tc--){ int n; cin>>n; vector vect(n,0); int i=0; ff(i,n){ cin>>vect[i];

}
   int curr = 0;
   int ans = 0;
   for(int i=n-2;i>=0;i--){
       if(vect[i]==0 && i>0 && vect[i-1]>=0){
           ans+=2;
           curr = 1;
       }
       if(vect[i]!=0){
           vect[i]-=curr;
           ans+=vect[i];
           curr=0;
       }
   }

   cout<<ans<<endl;

} }

int main() { solve(); return 0; }

This logic is somehow not working and I am unable to determine the failed test case. Can anyone please help.

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

One of the best CF rounds in a while!

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

For B: what if you can't fill all the zeros. for example, the input : 2 0 0 0 3 0 0 0 0 0 6 . In this input, you can't make all the zeros into ones and apply the operation on i and j. You would end up with 1 1 0 0 1 1 1 0 0 0 6. But then you haven't filled all the zero entries have you? You would then have to move the 1s to the right?

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

    After you end up with 1 1 0 0 1 1 1 0 0 0 6, you can move 1->3, to do operation i->j, all elements from i to j-1 must be >=1, but the j-th element could be equal to 0 :)

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

> be me
> reading editorial
> read "This is a well known fact"
> sure bud

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

Thanks for the great contest!

Here is my solution to E which used ChthollyTree, i.e., use set to maintain all the intervals.

actually, we just need these operations and there are only two types of values: 0 and 1. :

  1. set interval

  2. find first a after b.

because:

operate +1 on position x:

  • a[x] == 0: set a[x] to 1

  • a[x] == 1: find the first 0 after x, assume on pos y; then set a[y] to 1, set a[x..y] to 0.

operate -1 on position x:

  • a[x] == 1: set a[x] to 0

  • a[x] == 0: find the first 1 after x, assume on pos y (always exist); then set a[y] to 1, set a[x..y] to 1.

So we can use set or map to maintain the 1 intervals.

here is my code: https://mirror.codeforces.com/contest/1705/submission/164369724

it is written by Rust, but the logic and comment are still suitable for all languages.

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

in problem D: I can't understand why the XOR is the key idea? I see how this applied on the 4th test case but Why not we lucky that this is the case with the 4th test case only?

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

    In my opinion, after serveral operations, the number of the sum of $$$01$$$ and $$$10$$$ will not change.

    The problem says that $$$s_{i - 1} != s_{i + 1}$$$, for example, "100" will change to "110", and "001" will change to "011".

    We can find that the count of differences of the adjoining numbers will not change.

    In fact, XOR can find that if the adjoining numbers is not same, because $$$0 \ XOR\ 1 = 1$$$, $$$1 \ XOR \ 0 = 1$$$, $$$0 \ XOR \ 0 = 0$$$, $$$1 \ XOR \ 1 = 1$$$.

    I hope this solution can help you.

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

For D, I understand how "cool" the solution looks like, but seriously, how can I even approach the XOR thing.

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

    Personally I don't think I would ever directly land in the xor thing. The human and logical approach to get to the solution and possibly to that xor realization would be to look for blocks/groups of elements that have some relation with each other or certain relevant behaviour, that's a common and effective idea that you can train yourself to pay attention to in some problems and can become better in finding/identifying.

    For example, one group you might find is that all the elements with odd positions can only change the elements with even positions and vice-versa. But a more important one in this problem are the groups of ones and zeroes for example, you might realize that you can expand and contract those as much as you want, from there you start to get somewhere.

»
2 years ago, # |
Rev. 6   Vote: I like it -10 Vote: I do not like it

F can be solve in $$$n/{2.08}$$$ times. Here is another solution: blog (in Chinese).

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

Video Solutions for Problem C and Problem D

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

F is the same as this

and solution here 20210527

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

Problem E can also be solveed by set. I store the segments of continuous 1. For examplpe, 10110111 may be stored as {1,11,111}. We also stored the segment's left bounder and right bounder, so when we need to check a position, we can use std::set::lower_bound to find a section that may include that position. Modifying the set is similar as the solution of segment tree, including splitting a section, and merge two sections, tottal complex is NlogN.

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

Can somebody tell me how to think of D's solution? I think, it's just a little hard to think of. So is there anything lead to the soltuion? thx.

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

    Bro, I used to be very afraid of this kind of problems. But realize that the main approach is observing and trying. I found the solutution by this way: 110->100 100->110 This transform told me nothing, so I tried to write some long strings, such as the strings in the sample cases: 000101-> 001101 -> 011101 -> 011001 -> 010001 ->010011. I read this transform from the node under the problem statements. It is really amazing that 000101 can turn to 011101. It means that 0001 can turn to 0111, further more, 0001000 can be turn to 0111110. That is, you can freely extend or shrink a continuous ones(1111...) or zores(000...), but you can't make a section disappear. This lead to a great conclusion: If string s1 start by 1 and end by 0, then s1 is like this: 1..0...1...0...1..0.. Realizing that you can extend or shrink a section(but you can't make any section disappear), so if s1 can be transformed to s2, then s2 must be this way: 1..0...1...0...1..0.. The number of sections is the same as s1.

    The problem has almost been solved! Please finish the remaining work.

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

      Oh yeah, i got it. It's just observing and trying to find the clues as you are calculating the samples. thx a lot, bro!

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

I've decided to create my own editorial for the problems I solved(A-D)

A
B
C
D
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Our solutions are identical, but I find that my vocabulary is not enough when writing editorials.

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

    Hi, thank you so much for your take on the problems! If you don't mind could you explain the logic behind this line of your code in problem C:k = operations[i].second - (origlen[i] - k);

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

      Since we're going back in time, right now we know that the index of the kth character must be between the left and right values of operation i. This is true because operation i was the first value we found >= k, so the above statement must be true. What "origlen[i] — k" does is that it gets the distance between the end of the string and the kth character. But since the end of the string is the rth character of the previous string, we can reduce k by going that same distance down from that right value instead.

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

The editorial with hints is excellent :)

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

https://mirror.codeforces.com/contest/1705/submission/164391480 another solution for E using SegmentTree

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

    @Omar_Mohammad please can you tell what we are storing at one node of segment tree, it would be very helpful.

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

      it's a segment tree sum i.e( each node holds the sum of its segment and each leaf node holds either 0 or 1) that sets a value to some range[l,r] with some modification on its implementation to get the first one, the first zero, and the last one in a given range

»
2 years ago, # |
  Vote: I like it -34 Vote: I do not like it

https://mirror.codeforces.com/contest/1705/submission/164346961

Another Solution for E with BLOCK.

It's $$$O(n\sqrt{n\log n})$$$, which have Successfully Passed the System Test!

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

The complexity of using bitests to solve D is $$$O(n^2/w)$$$. But the maximum of n is $$$2*10^5$$$. I think this complexity can not pass the problem.

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

    Can anyone explain this?

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

      I can give you answer that "bitsets are fast lol" but I think that is not very satisfying so I shall summon sslotin and hopefully he can give a better explanation ;)

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

        Bitsets are fast lol.

        But seriously, if you are performing a simple bitwise operation, then, by the virtue of vectorization (processing a block of 256 bits per instruction) and instruction-level parallelism (capacity to execute two such instructions per cycle), $$$w=512$$$, or about $$$512 \times 3.60 \times 10^9 \approx 2 \cdot 10^{12}$$$ bitwise operations per second on CF server, which theoretically even lets you submit a $$$O(n^2)$$$ algorithm for $$$n=10^6$$$.

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

          Thank you very much for your explanation.

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

The editorial of D is a bit obscure for what it is. A more natural way to interpret and make the key observation is to note that the number of "segments" of 1's, alongside the endpoints of the string, are invariant under operations. After checking this condition, simply notice that each operation moves a boundary of some segment by 1 unit (eg. 011000 -> 011100 is expanding the right boundary by 1), so repeatedly greedy matching the leftmost segments of both strings would give the answer if we take the absolute differences between their boundaries.

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

Is there a way that i can access the testcase on which i fail? when i click on my failed submission it shows first few cases of each test but if it is failing the 272nd testcase then can i know what it was?

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

F can be solved with "Entropy" (https://en.wikipedia.org/wiki/Entropy_(information_theory)) .

You can split the positions into some groups , and each group includes at most B elements .

You find the positions of 'F' of each group independently , and use Entropy to find the optimal choice . which can be solved in $$$O(2^{2B})$$$ for each group .

Solution: 164420897 ,(B=12, and the number of queries is about 520 for n=1000).

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

    Awesome approach! I felt that the problem is about something more general, and it was entropy indeed.

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

Great Round!!

But why my submission on B got TLE on test 5?
Submission: https://mirror.codeforces.com/contest/1705/submission/164288648

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

F is a great problem, thank you!

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

There is an alternate easier solution (without using xor operation ) for D where you can store indices where change is made in a queue. Then the current element at index i will be (s[i]-48+length)%2 where length is length of queue which stores no. of indices where changes from 0 to 1 can be made with element values >=i and <n-1.

Here is the code-> https://mirror.codeforces.com/contest/1705/submission/170797410