Причем это опенкап, которого не было в птз, его все будут писать.

Is it the time issue?

see this

there are two reds, no cyan, no green, no grey and no white

Are you having Color Blindness :3

kind of a surprise :D

it depends on your rank not on the difficulty of the problemset

I love it,too.But I find it's difficult.

If I'm not wrong the Gran Prix starts just when the CF Round ends...

Maybe because of this
The round will run at the same time with Innopolis University Open, Olympiad in Informatics.

Its Sunday in India..So no School :)

as I said before.

there's no thing called completely justice in this world :(

I face the same problem :(

lol

No, but it's really rare. round #364

sorry

cmp function must not return true on both cases cmp(a, b) and cmp(b, a).
if cmp(a, b) = true then cmp(b, a) must be false.
if cmp(b, a) = true then cmp(a, b) must be false
but it is possible to return both false (which is mean that a is equal to b).

others bug :-"

Mine was

11001 3

Answer is 4.

Binary search

I did Binary Search.

can you explain a bit?

Binary search(O(log(n))) on length of permutation and check till which index there exist a subsequence 'p' in it (in O(n)). Hence resultant complexity is O(n*log(n))

I think It can be done using hashing + BIT or hashing + Seg tree.
Link: String Hashing
If you read this you can link strategy to this problem. Of course, binary search is easy one solution but It would be worth to learn so it can be applied many problems like this( Sometimes it is easier to implement String Hashing than other Solution).
PS: Accuracy of Solution depends on Probability of collisions.

Really cool binary search.

binary search

Take l=0 r=n-1 . DO binary search. Change the first (l+r)/2 elements as say '_' and check if p is a substring of t — http://www.geeksforgeeks.org/given-two-strings-find-first-string-subsequence-second/.

If yes make l=(l+r)/2+1 and ans=(l+r)/2 else r=(l+r)/2-1.

Display ans

binary search ... imagine that you have a query that answer if the current S has a subsequence T. This "function" is: true true true.... false false false.. You just have to find the last occur of true. You have to find the optimal prefix of the array permutation that answer TRUE on this query :) ! I hope it helps you ! Sorry for my bad english!

.

Hey guy stop it please

Usually I'd use a "strict <" in function "cmp". It could be the problem. Just a hint for you to dive in.

However, please do not post your code everywhere, especially in unrelated posts.

share your code using idone or just give the link of your submission :| Dont spam the page

I think so. It cost me too much time.

How to solve it?

edit-Just figured it out.

I don't think so. You can use a map to point a variable to its declaration location in input, ignore the := operator and easily parse a binary string to an integer/boolean array.

problem was quite easy but parsing it was hard.

Notice that each bit for ? can be decided independently. So, for each column of bit, just try 0 and 1 and take the optimal one.

For every bit in every variable, you should know it's value, for when the corresponding bit in ? is 0 and for when the corresponding bit in ? is 1. For example:

a = [[1, 1], [0, 0], [1, 1], [0, 0], [0, 0]]

b = [[1, 1], [0, 1], [1, 1], [0, 1], [0, 1]] (you calculate this using just variable a)

c = [[1, 0], [0, 0], [1, 0], [0, 0], [0, 0]] (you calculate this using just variable b)

E.g. the emphasized array in c means that if ? = "..0..", then c = ".. 1 .."; and if ? = "..1..", then c = "..0..".

Hey man... Don't do that!

(I've learned Chinese for years and the characters this man posted has nothing to do with "Olympics in Informatics in China". Don't waste your time on searching that)

I used DSU on tree technique. Removing character at index p is equivalent to removing all edges at depth p in the trie. The hash of a vertex is the hash of the string formed when I go from the root to this vertex. For each vertex v, I store the hashes of all vertices in its subtree.Then I can easily find out the number of distinct hashes in its subtrees after removing edges from v to its children.

Code

I solved it in , where k = 26, the alphabet. Solution idea is pretty simple  –  "Let's try and merge all child tries of the current node and see what total size we get". You can merge two tries in time proportional to the size of lesser one, and it is well known that in worst case each node will be in mergers.

So, the algorithm:

1. Iterate over all nodes, and also compute their depths in order to update answer for correct value of p.
2. Merge all child tries of current node and compute the size of this merged trie, then add size change to the answer for corresponding p.
3. Roll back the changes and go to the next node.

you are not alone

any ideas? What was the approach?

You have O(M*N*log(N)*len(var)) ~= 1/2 * 10^9. That's a lot to STL

I changed map to unordered_map after the contest and got AC. How do you tell when unordered_map is faster?

It's not the solution that we expected, I don't know how to prove it but it looks like it's correct.

Suppose m is even. Let's call 'step' changing avery LR to UD and then every UD to LR, as done in matthew99's solution. We want to show that eventually all cells become L or R.

A cell is 'stable' if it is L or R and it stays the same after performing an arbitrary number of steps. Suppose by contradiction there is a cell that never become stable, and consider the first one which has this property (it means that all the cells on the left and those placed in some preceding row eventually become stable. We can assume they are already stable, provided a sufficient number of steps has been performed). This cell must be U, and we can also determine the type of many other nearby cells, as shown:

****************
****ULR.........
....DULR........
.....DULR.......
etc...

(asterisks denote stable cells, dots denote unknown cells).

The same pattern must continue in diagonal until the border of the grid is reached. But this is impossible because there's no way to tile the cells above that diagonal using dominos (if you color them like a chessboard, the number of black cells and the number of white cells would be different).

The fact that you got a good rank was because there were only 3000 people , if there were more people it would proportionally increase :P

roz shankar bhagwaan ko ek lota jal chadao, rating badhegi bacha! bum bum bhole!

I passed with map,maybe your code is ...

me either :( and I wonder why map<> got TLE though it takes N * M * 2 * log2(N) which is less than 10^8

unordered_map is O(1)(instead of O(log n) ) on avg. maybe it is crucial here

100 % true. The harder part of problem E was processing the input Strings

and who reads faster

Here, take my downvote

Same here :(

I used the same and I've explained it here.

So let's prove asymptotic O(26 * n).

2 vertex have merged, so they won't be merge again. So my solution works 26 * O(count of merges).

For bitwise operations (like AND, OR and XOR), this sort of optimization problem can be solved independently for each bit. Just evaluate and sum all variables for all (two) possible choices for bit i.