seems I have solved memory problem..  but I don't know if bitset can fit in time

can O(1e8) fit into 1 sec??

Edited by author 27.09.2018 06:21

memory can be done O(n*sqrt(n)/64)

finally  I came up with N*LG(N) sol,  I nearly spent 4 days on this problem...

I think I can optimize it to O(n) suffix array can bedone by sa_is

Edited by author 30.09.2018 09:13

Hey, I've been spending some time thinking over this problem and I'm really stuck on how to make it work fast enough.

I was wondering if you could point me in the direction I should be looking to solve it.

What I did first was to write a simple bruteforcer and to just verify that that works. It is of course way to slow to get the answer as the input size grows.

My next idea was to create a graph out of the possible solutions and this seems promising, but just the time spent building the graph seems to be to much in itself to get a pass, not to speak of the memory requirements.

Right now I've been looking into suffix trees, but I don't really know how they would help me here, it's just the closest data structure to the problem that I could find.

I really want to solve this on my own, but right now I don't know what topics to research. Could you give me a hint in what direction I should be looking?

My sol involves suffix array and some count tricks.

first of all we initialization  [i,n-1] [0,i] is losing state, and the substring with same

oddity is losing state a different is winning state and count winning state +1 (it is a segment you can use fenwick tree to doit)

then we consider to enum the length of longest common substring, and merge the substring with longest common length of this length,if one of them is winning states ,then all of them are winning states.  how to merge them: using disjoint set, and how to find winning states  we can record substring [x,y] pref[x+y],win[x+y] as previous substring [l,r] with l+r==x+y and find this wining state by differece of odditiy of current substring and pref[x+y].  when merging them delete the node if it is not the root node, (i.e. do it count minus one count the all segments [l,r]  l-x==y-r with same oddity if it is win,different if it is lose. fenwick array can do it) and change the count when root node's winning states is update..


btw in fact we can throwout fenwick just using ordinary array and count sum of prefix of the array as number of its winning states.

I have heard there is O(N) rmq so this problem can be done in O(n)

btw there are many details on implement in my sol so I have spent nearly one week on this problem. maybe there are better sols...

Edited by author 30.09.2018 13:46

Edited by author 30.09.2018 14:01

Hi! I'm the author of the problem, feel free to discuss solution with me in hangouts: adamant.pwn@gmail.com, or (preferrably) telegram: @adamant_pwn. If you want to :)