What about shuffle solutions in F? Just mistake?

Is it possible to add this case to the system tests for F and hopefully a rejudge?

https://pastebin.com/dgWMkY4z

Both the following and possibly many more submissions fail on this case:

https://codeforces.me/contest/1186/submission/56222396

https://codeforces.me/contest/1186/submission/56210105

I want a prove for the incorrectness of the greedy solutions in F. Really puzzled...

It's easy to see that f(c,d) is even if and only if cntb and cntc have same parity
Someone can help to understand this in problem C? I don't see why that is always true

Can anyone elaborate 3rd solution? Cossack Vous and numbers

Can you give a more formal proof od problem D?

(Problem F) For which case will such a solution fail? (Test case-31)

B is missing :p

In problem C one of the tags is FFT, how is FFT applied here?

Problem C submission code. How can i optimize more it is giving TLE on test 7.

Can you explain the solution of B task? It is interesting problem

what is the error in this code for problem c??

include<bits/stdc++.h>

using namespace std; int main() { string a,b; cin>>a>>b; int al=a.length(),bl=b.length(),i,j,x,ans=0; for(i=0;i<=al-bl;i++) { int x=i,count=0; for(j=0;j<bl;j++) if(a[j+x]==b[j]) count++; if(count%2==0) ans++; } cout<<ans<<endl; return 0; }

another solution for C:

let the changes be equal to total position such that b[i]!=b[i+1].

now let cnt stores the total mismatch between first substring of a and b.

do cnt=cnt%2. if cnt is even: ans++

To calculate mismatch between just next substring of a and b: {

Better you draw 1st sample test case in notebook.(think now as we are shifting b to right.)

1.Now position where b[i]!=b[i+1] there will be +1( if previous match become mismatch ) or -1( if previous mismatch become a match ) in value of cnt and in either case cnt value change from odd to even or even to odd.

to keep it simple lets just +1 for those positions because we only concern about odd/even of the cnt.

so overall total +1 in cnt will be by + changes

2.take care about new mismatch and previous mismatch

(new) +1 the cnt if mismatch between last char of b and last char of current substring

(old) +1 the cnt if mismatch between first char of b and first char of current substring

if cnt is even: ans++

}

Link to my submission

how problem C can be solve using fft ?

can someone explain me in simple way in problem C why having same parity gives even no of change?

In problem E, while doing this multiplication, ((fieldx−1)⋅(fieldy−1)−1)⋅n⋅m / 2 it can lead to overflow. Can someone suggest how to handle the overflow? I think it requires some sort of trick.

My solution is here: https://codeforces.me/contest/1186/submission/56266238

It is failing on test 5 due to overflow (at least that's what I think).

Where is author's source code for F?

In problem C, It's easy to see that f(c,d) is even if and only if cntb and cntc have same parity. In other words if cntc≡cntd(mod2) then f(c,d) is even.

what is the meaning of parity here? I have looked up all the comments but cant found any clear explanation.

For problem F, you don't need to "find Euler cycle and do the following steps for each component independently."

Because adding fictive vertex makes the graph connected.

I think I have a good idea of understanding Problem C.

Find out how many different positions of two strings A and B are equivalent to $$$\sum{a_i\bigoplus b_i}$$$

Because it only judges parity, it is equivalent to $$$XOR(a_i)\bigoplus XOR(b_i)$$$

In problem C, I don't understand the explanation for the problem. Please explain the pseudo code for the solution.

I don't understand solution problem D, anybody explain better?,i was seeing some solutions and most of them have this solution

https://codeforces.me/contest/1186/submission/56278052

Can some one explain me last part of editorial E .I mean how author arrived at if bitcnt(a)+bitcnt(b) is an odd number, then the matrix is inversed. Also how do we determine if a field is inverted or not if its coordinates (x,y) are odd,odd or odd,even ?

One important note — (In tutorial of Problem E)in last statement "if bitcnt(a)+bitcnt(b) is an odd number, then the matrix is inversed" , indexing is considered from zero i.e suppose we are referring to first row and second column then that is (0,1). readers might get confused since in problem and in most of the part of tutorial of problem E indexing is considered from 1. Also bit count refers to number of 1's in binary representation of number and not least number of bits required to represent the number in binary.

For Problem $$$E$$$, $$$bitcnt(a)+bitcnt(b)$$$ tells you whether the matrix at position $$$(a,b)$$$ is inverted or not due to the following reason:

Imagine the whole infinite a grid as a big quadrant, which consists of $$$4$$$ quadrants, each of which consists of another $$$4$$$ quadrants, and so on. Then if you started looping on bits from the most to the least significant position (let the current bit in the loop be the $$$i_{th}$$$ bit), then checked the $$$i_{th}$$$ bit in both $$$a$$$ and $$$b$$$. If bits are $$$(0,0)$$$ you go to the top left quadrant, $$$(0,1)$$$ to the top right, $$$(1,0)$$$ to the bottom left, $$$(1,1)$$$ to the bottom right. Then you repeat the process for the quadrant you went to using the $$$(i-1)_{th}$$$ bit and so on. This shows then when you eventually reach your matrix, it will be inverted only if the parity of $$$bitcnt(a)+bitcnt(b)$$$ is odd.

Where is the author's code for problem F???

E problem ， if bitcnt(a)+bitcnt(b) is an odd number, then the matrix is inversed. Who can prove it ？