Short and concise problem statements ✓
NO BACKGROUND STORIES ✓
Useful samples ✓
Quick Editorial with well documented implementations ✓
Super interesting problems ✓
Strong pretests (I hope so, please don't let me down) ✓
RATED FOR ALL ✓
No queueforces ✓
P.S: It seems pretests turned out to be a bit short (as warned in the announcement), never mind though
CONCLUSION: A perfect contest after a long time, Thanks Monogon!

I think the time limit of Div.2D is too tight. I got the right solution when it was only 30 second before the contest was finished, but disappointedly got a TLE. My TLE Code

For C2, I basically took Solution 2 for C1 and then added a custom data structure to make operations (modifying a prefix) done in O(1) time. Basically, you maintain the left and right indices of the original string and also keep booleans indicating if the string is reversed and if the string is flipped.

Can someone further explain how to optimise the 2nd solution for C1 with a segment tree?

couldn't solve but really loved the problems Div2 C1, C2 and D.

My rating hovers at 1800 and I took a leap in div 2 to try Problem E.

It seems that my approach is the same as the answer, but my implementation is wrong :(

I also could not find a case that fails my implementation during the contest.

No regrets, other than failing to see the trick in solving D2C2

Anyone with a randomized solution for C2?

bye bye CM :(

I never thought that writing 'first' & 'second' instead of some random names would have been so helpful.

In D2-C2, how exactly will we keep track of the first bit?
Won't it depend on a lot of other bits?

Instead, we can observe that after making the last k bits correct with our procedure, the prefix of s of length n−k will correspond to some segment of the original string s, except it will be possibly flipped (inverted and reversed). So, we need only keep track of the starting index of this segment, and a flag for whether it is flipped. Complexity is O(n).

I was trying to implement this. Anyone help me how to implement this.

Here is my solution for D, which works in O(n). I wasn't sure about greedy part of it, but it passed all of the tests. 87566235

Can anyone prove/explain why this trick works? I knew it since school, but I forgot how it works.

Video explanations if you are interested after you give Monogon contribution.

Loved this round!

fourth approach for C2:

Use deque and insert all indexes from 0 to n-1. Then start popping from end. If value is not equal then we need to pop from front. Also keep track of number of inversions done.

Solution

My Linear Solution For Problem C

• Lets $$$a[head..tail]$$$ correspond to $$$b[0..tail - head)$$$

• If $$$a[tail] = b.back()$$$ then we move $$$tail \rightarrow head$$$

If $$$head > tail$$$ then $$$tail = tail + 1$$$

If $$$head < tail$$$ then $$$tail = tail - 1$$$

• If $$$a[tail] \neq b.back()$$$ then we must reverse

If $$$a[head] = b.back()$$$ then after reversing it will be different, so we have to flip it

Then we can reverse in $$$O(1)$$$ by swapping $$$head \leftrightarrow tail$$$

But becareful when we reverse it two times when the size is equal to one

int query()
{
    int n;
    cin >> n;

    string a, b;
    cin >> a >> b;

    vector<int> operation;
    for (int head = 0, tail = n - 1, flag = 0; !b.empty(); b.pop_back())
    {
        if ((a[tail] ^ flag) != b.back())
        {
            if ((a[head] ^ flag) == b.back() && head != tail)
                operation.push_back(1);
 
            flag = !flag;
            swap(head, tail);
            operation.push_back(b.size());
        }
        if (head >= tail) tail++; else tail--;
    }
 
    cout << operation.size() << ' ';
    for (int x : operation) cout << x << ' ';
    cout << endl;
    return 0;
}

hello friends, it might happen that this post of mine may get downvoted a lot, but I need to share something very important.

I loved the problems very much and even passed the protests for problems A, B and C1 and it was very disappointing to know that my solutions for B and C1 failed, maybe due to weak pretests.

I would appreciate it if I can get a fair knowledge regarding this and implore the codeforces community to make better pretest, it was very disheartening for me.

P.S: I do accept my incompetence, I just wanted better pretest so that if I knew i could have improved upon that. Again, awesome round authors.

I solved C2 (Hard Version) with Doubly ended queue.
Here is my submission: 87597675

dp solution for B 87559531

In problem C hard version I used an O(n) deterministic brute force method.

I solved easy version with the following observation:

if I have a string ....0000000 (k zeros) and I want to change it to ....1111111 (k ones) I can apply {n=current length, k, n}. Then the last k bits are OK and the first n-k bits don't change. (And don't forget to n-=k after this operation) (P.S. and if the current last bit are the same, just skip)

So if k always > 2, we can do the task in 2n operations. The sad thing is that k could possibly(?) always be 1.

If k is 1(suppose current length is n, this bit would be a[n-1]), if n = 1, just apply {1} to flip. If n>1, we detect one more bit(a[n-2]). If a[n-2] == b[n-2](Suppose, 01 and 11), apply {n, 1, n}. So we used 3 steps to deal with 2 bits in this case. But when a[n-2]!b[n-2] (say 01 and 10), the optimal operation is n, 1, 2, 1, n, which is 5 steps. Not good enough.

So again we detect one more bit(a[n-3]), if a[n-3] == b[n-3], just do {n, 1, 2, 1, n} s, 5 steps for 3 bits, enough. If a[n-3] != b[n-3], there are two cases: (1) a[n-3] == a[n-2] (say 110 and 001}, use {n, 1, n, n-1, 2, n-1}, 6 steps for 3 bits (2) a[n-3] != a[n-2] (say 010 and 101}, use {n, 3, n}, 3 steps for 3 bits

So the task can be done in 2n operations

So dumb lol

my python code for problem D passed pretests but got tle in system tests. now the same code i submitted in PyPy it got accepted. But how? Why did python show TLE? My happiness of solving 5 problems for the first time was ruined in 15mins. :(((((((

Monogon In games like the one given in problem $$$B$$$ , how to prove that there always exist a fixed answer (i.e how to prove that result of the game is fixed from beginning itself if they both play optimally).Proof in the editorial assumes this .

Question E (Mastermind) reminded me of the question "Bulls and Cows"

I had a different solution for C2, and used two pointers (left=0 and right=n-1), where left and right could be beginning/end of the remaining segment, and only advance in one direction (which was determined by the nubmer of flips). For example, if you start with abcdef, and you fix the last bit by flipping, now you have fedcba, and now you need to compare 'b' to 'f' (so the right pointer stayed on 'f', but the left, which was 'a', moved to 'b').

My Video solution for Problem B. Hope you Like It.

In problem D, after couting the lengths of all the continous blocks as in the editorial, i checked whether it can form a sub-set sum that equals to n by brute force (run in exponential time) but i used some optimizing tricks here, that is, according to pigeon hole principle, if the total number of continous blocks is greater than or equal to n, then we can always form a subset with sum = n, so there is no needs to check subset sum in these cases, and while running brute-force, if i encounter a subset that sum up to n, then i stop the algorithm immediately .Anyway, i passed the system test though i thought i could get a tle if the test cases were strict enough.

How to solve div-2 D in O(n root n). Thanks in advance.

Can someone explain what is wrong with the following approach for div1 C(Mastermind):- Let "nc" be the color which has not occurred. Let's first sort the sequence and keep track of corresponding index in original array.Let's try to first color (y-x) indexes which can be done by swapping color of first((y-x)/2) with last (y-x)/2 indexes if colors of cells to be swapped are different,if (y-x)is odd we will make one index equal to color "nc", else we cannot find a solution(I chose first and last (y-x)/2 because if possible they only can be of different color) . After that we will left with some indexes in middle, then we can color x indexes from the remaining indexes in same color and leftover indexes in color "nc". But, i am getting wrong answer in testcase 38 of test 2. Link to submission:- https://mirror.codeforces.com/contest/1381/submission/87596300

I had the following solution to Div1D. Unfortunately I did not manage to implement it correctly in time, but I am still curious if this is the correct approach.

Does this work? If not, what is a counterexample?

For anyone looking for a fun DP approach for Problem B. Here is the code, basically dp[i] signifies if a player starting from the ith index of the array can win. In order to solve the problem for any index i, you check if the you can force a loss from (i+1) index by taking all the stones at ith index or if you can't do that check if you have more than 2 stones at index i, if so, leave 1 stone so that you can win from the (i+1)th index. If none of this works, then the person starting at the ith index cannot win.

/* package codechef; // don't place package name! */
import java.io.BufferedReader; 
import java.io.IOException; 
import java.io.InputStreamReader; 
import java.util.StringTokenizer; 
import java.util.*;
 
public class HelloWorld{
    public static void main(String[] args) throws IOException 
    { 
  
        Scanner input = new Scanner(System.in);
        input.nextInt();
        while(input.hasNext()){
            int n=input.nextInt();
            boolean[] dp=new boolean[n];
            dp[n-1]=true;
            int[] l=new int[n];
            for(int i=0;i<n;i++){
                l[i]=input.nextInt();
            }
            for(int i=n-2;i>=0;i--){
                if(dp[i+1]==false){
                    dp[i]=true;
                    continue;
                }
                if(l[i]>=2){
                    dp[i]=true;
                    continue;
                }
                dp[i]=false;
            }
            System.out.println(dp[0]?"First":"Second");
        }
    }
}

Nice Contest!

is this the only solution for 1382B ?
like is there any technique or algorithm for problem like this..?
just curious..

thank you for the round..

Is the score of c2 too low? I found that problem D is a relatively simple dp, but there is not enough time to solve it. It takes a lot of time to solve c2, but the score of c2 is only 1000 points

What is wrong in my this code (for C1)-> Codeforces is saying a is not converted into b but here is my code: https://mirror.codeforces.com/contest/1382/submission/87603260 Uncomment last two lines and run to see that a is onverted to b . Someone please explain!

can someone explain to me problem B of div2. especially this test case 6 1 1 2 1 2 2 why is the answer First??

Thanks For the good problems. I really enjoyed the contest. First time I am able to solve the 5th question in Div 2. It's really nice feeling.

In problem div2D/div1B I saw some submissions using bitset. How to solve it using bitset?

I want to notify you that omaik786 is also my account . I want to grow two accounts at the same time . If handling two channels is not appropriate , notify me . I won't continue the 2nd account

In Solution 1 of C2, how is it possible to convert string 010 to 000 in 3 operations??

I love how Monogon has given 2-3 solutions for every problem

Thought about question C2 but wouldn't flipping for randomization also (takes steps) make it come close to the 3*n mark? P.S-Please explain a bit more about this randomization concept if you can,please.

4 years later we will see comments crying out for implementation

Almost same code gets once runtime error and once AC in Div1C.

AC CODE vs RUNTIME ERROR . Can anyone check please ? This is very weird.

.

I think I have a deterministic solution for С2 with ratio 5/3 operations per bit.

Here is my code:

https://mirror.codeforces.com/contest/1382/submission/87592131

The main idea is: you scan both strings from the end to the beginning, taking suffixes of length 2 (or 3) making these suffixes alike. If suffixes of length 1 are equal, we just go on. For example (converting suffix 00 to suffix 01): - ......00 -> filp the whole string - 11..... -> filp prefix of length 1 - 01..... -> filp the whole string - ......01

We filp the whole string only two times in each case, in the beginning and in the end, so dots part remains unchanged.

The most operations-consuming case is, for example, when you want to convert suffix 001 to 010. It takes 5 operations per 3 bits. So overall complexity in operations is 5/3 operations per bit. Here is how you deal with this case:

• ....001 -> flip the whole string
• 011... -> filp prefix of length 1
• 111... -> flip prefix of length 2
• 001... -> flip prefix of length 1
• 101... -> flip the whole string
• .....010

Simple approach for C1 and C2, make the first string all 0s,make it 2nd string from there. as handling all 0s or all 1s is O (n)

"If you find a deterministic solution with a strictly lower ratio than 2 operations per bit, we would love to hear about it!"

Monogon,

if last bit of a is equal last bit of b,we can erase it(decrease length to 1)

else let's try to do last 2 bits of a equal last 2 bit's of b

1)reverse string a

2)if we can do at most 1 operation to do first 2 bits of a reversed 2 last bits of b,do it and after that reverse all string a(decrease length to 2)

if we failed in it our last bits of a and b is 01,10 or 10,01

3) in this case try to decrease length of s by 3 doing <=3 operations,and after that reverse a

in addition: decrease to 1(case 1):0 operations

decrease to 2(case 2):<=3 operations

decrease to 3(case 3):<=5 operations

we are doing at most (5*n/3) operations

i missed some cases in explanations you can see it in my code code:

https://mirror.codeforces.com/contest/1381/submission/87606984

my solution seems like:reverse string a,trying to do something with first <=3 first bits,reverse string a

All the problems were interesting and statements were simple and straight..thanks Monogon!!

how we can use the randomization in third problem div2(1382C2) to reduce time complexity as mentioned in tutorial

Nor that anyone is interested but still ...

I have another approach for div2B , we start from the end and will use a boolean win and set it to 1. whoever selects the last pile will select the full pile and win. now moving from end

when w = 1 (next move is of the winner) if v[i] > 1 the winner should select v[i] — 1 and leave 1 for the looser so that he would have won in the next step and if v[i] = 1 we change the move to looser and set w = 0 as looser would have maken this move

when w = 0 (next move is of losses) we will just set w = 1 because last move would have been of a winner

if we end up at w = 1 then the first person won otherwise the second person won.

bool w = 1;
for (int i = n - 2; i >= 0; --i) {
        if (w) {
	        if (v[i] == 1){
			w = 0;
		}else {
		        w = 1;
		}
       }else{
		w = 1;
	}
}
if (w) first
else second

code : 87607154

Can someone pls explain Div2 C2 Solution 2 from editorial , I know the N^2 solution...

I have 2 questions about Div. 2E/Div. 1C:

1. How to prove that we can get at least 2f-(n-x) forced matches?
2. Why are (n-x)/2 rotations of indices optimal ?

UPD: Never mind, I got answers by myself, if anybody has same questions, ask me and I will explain :)

Can someone provide a sample code for Div2C2/Div1A2 that uses the solution 2 mentioned in the editorial for the problem?

I was unable to find out the reason behind MLE on test case 2 of this submission of problem 1382C1 - Prefix Flip (Easy Version). I've tried for a long to find out this. Can someone please tell me what is wrong with the code? My Submission -> 87609365

In My solution of C1 I followed the second approach mentioned in the tutorial. But my code is getting runtime error. I am still not able to figure out the problem. It would be really helpful if someone can debug my solution.

contest was awesome but the score distribution was not good div2 C2 was harder than B

Why does the following submission: 87526271 for Div. 2 A fail the test case: 1 1 1 1 2