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

1705B - Mark the Dust Sweeper

Author: MarkBcc168

1705C - Mark and His Unfinished Essay

Author: MarkBcc168

1705D - Mark and Lightbulbs

Author: MarkBcc168

1705E - Mark and Professor Koro

Author: abc241

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.

• 3 days ago, # ^ | The editorial with hints is excellent :)

• 4 days ago, # ^ | ← Rev. 5 →   +1 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.

  • 4 days ago, # ^ | Oh okay, I got it..Thanks a lot.

• 4 days ago, # ^ | 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

• 3 days ago, # ^ | pay attention to the range of data, especially 1e18.

• 4 days ago, # ^ | Note that the length of the string can be upto 240⋅200000240⋅200000 because the copying operation could be [1,n][1,n], [1,2n][1,2n], [1,4n][1,4n], ……, [1,239n][1,239n]. 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.

  • 4 days ago, # ^ | ok Thanks a lot!

• 4 days ago, # ^ | you are 607 mouse ?

• 4 days ago, # ^ | you are 607 mouse ?

• 3 days ago, # ^ | I am sorry to keying D as C

• 4 days ago, # ^ | Great catch! Fixed.

• 4 days ago, # ^ | There is no specific knowledge required to solve C. You can try reading the hints and tutorial provided above.

  • 4 days ago, # ^ | 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

    • 4 days ago, # ^ | the best way to improve at problems like div2C is through problem solving and gaining experience

    • 3 days ago, # ^ | Practice more div2Cs would be OK. Try to solve them as quickly as you can.

• 3 days ago, # ^ | C is just about implementation

• 3 days ago, # ^ | I though the observation that for each query you have to travel back through the (c<=40) operations was the hardest part.

• • 3 days ago, # ^ | ← Rev. 2 →   +3 This made my day a whole lot better i will just go and jump off a cliff now. Thank you, stranger

• 4 days ago, # ^ | Same bro :(

• 4 days ago, # ^ | It is easy to come up with solution for D by observing carefully. Say we have 10001 then we can convert it to 11101 -> the first block of 1 got expanded to last continuous 0 we had 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.

  • 3 days ago, # ^ | this was my sol as well.

• 4 days ago, # ^ | 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.

• 4 days ago, # ^ | I think the invariant that the number of chunks of 1 stays the same is easier to be observed.

• 4 days ago, # ^ | 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

• 3 days ago, # ^ | 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.

• 3 days ago, # ^ | This could be helpful: https://codeforces.com/blog/entry/85172 (there is one problem with an invariant)

• 4 days ago, # ^ | yeah I got the idea from josephes problem finding the value of index in previous recursion using mathematics

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

  • 3 days ago, # ^ | 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.

• 4 days ago, # ^ | Not needed

• 4 days ago, # ^ | ← Rev. 2 →   0 You can see 164372123 But as the range of c is too little 1≤c≤40 , it doesn't make that difference.

• 4 days ago, # ^ | ← Rev. 4 →   +22 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.

  • 4 days ago, # ^ | Thanks a lot, that would explain what happened.

• 3 days ago, # ^ | [unrelated] why are you removing the legendary line :( #define ick cout<<"ickbmi32.9\n"

• 4 days ago, # ^ | Based on our testing, the segment tree has a high constant factor that an O(nlog2n)O(nlog2⁡n) is very hard to pass. You should either use bitsets or aim for O(nlogn)O(nlog⁡n). We apologize for the strict TL.

• 4 days ago, # ^ | The comment is hidden because of too negative feedback, click here to view it

  • 4 days ago, # ^ | I disagree, the O(nlog2n)O(nlog2n) solution was more obvious to me. I couldn't come up with that observation.

• 4 days ago, # ^ | Can you share your Approach towards problem D?

• 4 days ago, # ^ | This was written when there was the second operation (of deleting numbers). The editorial is updated now. Hope this eliminates your confusion.

• 4 days ago, # ^ | 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+qn+q updates)

  • 4 days ago, # ^ | ← Rev. 2 →   +3 That's what the amortized analysis handles, because all the extra steps that we do will reduce the value of |S|+|T||S|+|T|. You should be able to find some resources by searching "amortized analysis" and "potential method".

• 4 days ago, # ^ | in b what if the array is 3 0 0 0 0 2 0 0 4 how it work ??

  • 4 days ago, # ^ | Initially: 3 0 0 0 0 2 0 0 4 1 => 2 1 0 0 0 2 0 0 4 2 => 1 1 1 0 0 2 0 0 4 3 => 0 1 1 1 0 2 0 0 4 4 => 0 0 1 1 1 2 0 0 4 5 => 0 0 0 1 1 2 1 0 4 6 => 0 0 0 0 1 2 1 1 4 Now you can see that for clearing the rest, you need a minimum of (1+2+1+1) = 5 turns Total: 5+6 = 11 turns

    • 3 days ago, # ^ | the array should be 0 0 0 0 1 2 1 1 4 6 not 0 0 0 0 1 2 1 1 4 the final answer is 9+6

• 3 days ago, # ^ | Yes, you are right, I made a lot of mistake on intint and long longlonglong. In a contest, you can try this: #define int long long …… signed main() { } **** And when you use printf to output, don't forget to use "%lld" instead of "%d".

• 4 days ago, # ^ | Coz of integer overflow. You need to use long long. Made the same mistake :")

• 4 days ago, # ^ | Take a look at Ticket 15743 from CF Stress for a counter example.

• 4 days ago, # ^ | Take a look at Ticket 15750 from CF Stress for a counter example.

• 4 days ago, # ^ | From diagnostics: "Probably, the solution is executed with error 'division by zero' on the line 37".

  • 4 days ago, # ^ | thanks . I will try to fix out

• 4 days ago, # ^ | 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

  • 3 days ago, # ^ | 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.

• 4 days ago, # ^ | Take a look at Ticket 15738 from CF Stress for a counter example.

  • 4 days ago, # ^ | ← Rev. 4 →   0 Thank you so much bro!!!!! Being depressed I almost started a mission to get the 4992-th testcase using this: if(cas==4992) { cout<<n<<"&"<<cc<<""«s«" "; for(i=0;i<cc;++i) { cout«lll[i]«"&"«rr[i]«""«s«" "; for(i=0;i<cc;++i) { cout«lll[i]«"&"«rr[i]«""; } return; } You saved me !

  • 4 days ago, # ^ | Bro please add stress test for 1702 — E.It's been 6 days

    • 4 days ago, # ^ | I don't add problems on demand. (Not on the free plan at least).

      • 4 days ago, # ^ | On what basis do you add problems?

        • 4 days ago, # ^ | If I feel like it, or when someone pays me to. You can find the details on the pricing page.

}
   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;

• 3 days ago, # ^ | ← Rev. 2 →   0 Try this test: Input: 1 5 2 0 0 0 0 Output: 5

  • 3 days ago, # ^ | Got it. Thanks.

• 4 days ago, # ^ | 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 :)

• 3 days ago, # ^ | In my opinion, after serveral operations, the number of the sum of 0101 and 1010 will not change. The problem says that si−1!=si+1si−1!=si+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=10XOR1=1, 1 XOR 0=11XOR0=1, 0 XOR 0=00XOR0=0, 1 XOR 1=11XOR1=1. I hope this solution can help you.

  • 3 days ago, # ^ | Thanks alot

• 3 days ago, # ^ | 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.

• 3 days ago, # ^ | 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.

  • 3 days ago, # ^ | 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!

• 3 days ago, # ^ | Our solutions are identical, but I find that my vocabulary is not enough when writing editorials.

• 35 hours ago, # ^ | 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);

  • 31 hour(s) ago, # ^ | 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.

    • 22 hours ago, # ^ | That makes it so much more clear, thank you!

• 3 days ago, # ^ | Can anyone explain this?

  • 3 days ago, # ^ | 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 ;)

    • 3 days ago, # ^ | 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=512w=512, or about 512×3.60×109≈2⋅1012512×3.60×109≈2⋅1012 bitwise operations per second on CF server, which theoretically even lets you submit a O(n2)O(n2) algorithm for n=106n=106.

      • 2 days ago, # ^ | Thank you very much for your explanation.

• 3 days ago, # ^ | Actually there is no method to get the testcases.

  • 3 days ago, # ^ | thanks for the info, i think its good if i figure out the mistake on my own