It might be a good idea to limit the number of participants so that codeforces would work well (around 10000). Div 2 people will participate more rarely on average, say once a week instead of twice, but without long queues. The only effect on div 1 is reducing queues.

For a given n:

t = floor( ( -1 + sqrt( 1 + 24*n ) ) / 6 )

then the tallest tower that can be built from n is : 2 + ( (t-1)*(3t+4) )/2

keep subtracting this from n and recalculating 't' and tallest tower as long as n > 1

a much easier to understand formula is (trng(n)*3)-n where trng is the nth triangular number. Notice that there are 1, 3, 6, 10... triangles in the structure and each triangle requires 3 cards. Then we subtract n cards, as we do not need cards at the bottom.

i know a better approach to find the formula

for a height h there will be 2*h no. of cards at the base there will be total of (h-1)*((h-1)+1)/2 no. of triangles now just run a loop till n<2 https://codeforces.net/contest/1345/submission/79162987 link to my submission

In this problem, when you take 2*3 grid you see that you can not solve that puzzle, therefore you can not solve similar grids which has higher dimensions than 2. That means, if either row or column is 1 it can be sokved and if both are 2 it can be solved. Otherwise not. I hope now you understand.
Sorry for my bad english..

consider a subset of rooms, from room 0 to n-1. let n = 5. CASE 1 let's assume a0 = 0, a1 = 1, a2 = 2, a3 =3, a4 = 4. Now, the guest in room 0 will go to -> 0 + a0 = 0 similarly guest in room 1 will go to -> 1 + 1 = 2 room 2 -> 2 + 2 = 4; room 3 -> 3 + 3 = 6; room 4 -> 4 + 4 = 8;

room 5 -> 5 + 0 = 5; room 6 -> 6 + 1 = 7; room 7 -> 7 + 2 = 9; room 8 -> 8 + 3 = 11; room 9 -> 9 + 4 = 13; .... and so on.

No guests get the repeating room {explained later}

CASE 2 let's consider a0 = 5, a1 = 7, a2 = 5, a3 = 8, a4 = 6; for room 0 -> 0 + 5 = 5; room 1 -> 1 + 7 = 8; room 2 -> 2 + 5 = 7; room 3 -> 3 + 8 = 11; room 4 -> 4 + 6 = 10;

room 5 -> 5 + 5 = 10; {gets repeating room} ******

in both cases, we can observe an arithmetic progression is forming . after every n__

Now if we observe both the cases, we can see that if, for a particular value of 'i' b/w 0 to n-1 if there exists a j, such that aj + j lies in the arithmetic progression of (ai + i), it implies that there will be a collision. This is because, a time will come when becomes (aj + j),

for example in case 2,

for i = 0 we can see that ai = 5 and i = 0; so the first term of the arithmetic progression is ai + i = 5 + 0 = 5; now we'll check for j = 1 to n-1, whether there is such a j for which aj + j lies in the arithmetic progression of ai + i with difference = n; so for j = 4, aj = 6, and aj + j = 10; so aj + j clearly lies in the arithmetic progression of ai + i ( 5 + 1*5 = 5) {ai + i + (x-1)*n = xth;}

this way we have to check for every i, that, whether there is a number which is in ap with ai + i and diff = n; this will take O(n*n). To optimize it we can just check whether there are more than one such numbers such that (ai+i)% n == (aj+j) % n because ai + i + (x-1)*n = aj + j; taking modulo both sides we'll end up with (ai+i)% n == (aj+j) % n and hence O(n).

Consider the number line divided into segments of size n i.e [-1*(n) -2 -1] [0 1 2 ...n-1] [n n+1 n+2...2*n — 1] so now when you add to i + a(imodn) each i converts to some j which will be a index of one of these segments definitely.. What i am trying to say is that.. For example 1)n==3 Consider applying shuffling operation of segment [0..2] and we have a1,a2,a3 such that after shuffling 0->3,1->7,2->11 now 3 is actually at 0th position in its segment [3,4,5] 7 at 1st in [6,7,8] and 11 at 2nd position in [9,10,11] so in this example above we can see that each element results into an unique positions ,whatever be the segment it settles

So for such kind of example always the answer is YES!!

But consider this example

2) n==3 and we have a1,a2,a3 such that 0->3,1->6,2->11 so now 11 is still the 2nd position but 3,6 both are ones at 0th position Therefore such array a will result in generation of elements in which no 1st position element is ever created but the 1st position elements get converted to 0th position So Vacancy will be definitely created.. So for such kind of example the answer is NO!! * HOPE YOU UNDERSTAND..

I know it's late but I think this is easier (it might help someone)
We know that a collision occur if for some $$$0 \leq i,j \leq n-1 $$$ where $$$ i \neq j$$$, the following condition holds true
$$$ i + k_1n + a_i = j + k_2n + a_j$$$ because $$$x+yn \equiv x \mod n$$$ where $$$0 \leq x \leq n-1$$$
Now, $$$i+a_i-j-a_j = (k_2-k_1)n$$$
$$$ \implies i+a_i-j-a_j \equiv 0 \mod n$$$
$$$\implies i+a_i \equiv j+a_j \mod n$$$

k refers to any integer and not any index of the array

The shuffle is k + (a_k mod n). So, for example, if a_1 = 12 for n = 7, room 1 will go to room 1 + (12 mod 7) which is room 6. Room 8 will also go to 8 + (a_1 mod 7) since 8 = 1 mod 7, so room 8 will go to room 8 + (12 mod 7) which is room 13. In general, room 1 + kn will go to room 1 + kn + (a_1 mod 7) = 1 + kn + 5 = 6 + kn. Hope this was helpful.

Yes, but notice that he is taking $$$0 \leq i < n$$$ so we have $$$i$$$ $$$mod$$$ $$$n = i$$$. The same goes for $$$j$$$.

Same with me. Solved A,B,C within 20 minutes. I had a significant increase in rating even if I hadn't solved any other problem.

Topological sorting isn't needed in this problem. The idea is, look at the numbers from a_1 to a_N in order. When you get to an index k, how do we know if we can put an A there? It's only possible if a_k is "not comparable" to any other a_i where i<k. So my solution is whenever we process an index i, we do two dfs traversals — one to mark all indices j where a_i<a_j, and one to mark all j where a_j<a_i.

This way, when we get to a_k, we checked if it was marked in one of the two ways. If it was marked, we have to put an E at k. If it wasn't marked, we put an A. In either situation, we do the two traversals.

In order to keep track of this, I kept two "seen" arrays — one array to mark seen vertices when going "up" the graph, and one for going down. As a result the solution was very clean.

I also checked for cycles in the same traversal, but you don't need to do that if it's too confusing — you can do it in a separate pass.

Read the problem statement carefully. There are infinite rooms.

try f.second+1 < m

Suppose I have a graph with two nodes and an edge $$$2\to 1$$$. Node $$$2$$$ has indegree $$$0$$$, yet the statement $$$\exists x_1,\forall x_2, x_2 < x_1$$$ is false.

Hacked it with testcase:

1
200000
0 0 0 0 0 ...

The problem is that, x3 < x2 Now you have fixed x2, (As There exists x2 comes first in order) , so not all x3 holds x3 < x2.

A requirement for universality is that the variable is only comparable with larger-indexed variables. It is mentioned in the 2nd paragraph of editorial.

The requirement for a variable x(i) to be universal is that, In the directed acyclic graph, No node x(j) with j < i can reach x(i) and x(i) also cant reach such x(j). In other words, all nodes reachable from x(i) and reachable to x(i) should have higher labels.

To check that, we do DP and find minimum below and minimum above in reversed graph.

Could you please explain the idea behind this question?

I get two warnings when compiling that, both which might lead to undefined behavior (I got the answer 6 when running it on my computer). One is that size is ambiguous (size is a std function you included) and the second is that k isn't initialized. I compile with -Wall -Werror -Wpedantic (and I have it so Vim + YouCompleteMe highlights such errors).

please some one reply

What's your meaning, The 3*3 grid is all colored white?

actually k is included in R.because we have infinite room.once we reorganize the position,we are able to let the k pos guest move to k+a[k mod n] position

Fixed your code the number you module is negative,which may cause problems

Like this? 79238791.

I guess the problem is toAdd + j can't be negative, which makes the statements behind that meaningless.

Check this out. Link

I also WA on pretest5 in contest. When I look other's AC code, I am wonder about test 15. In my program I get

3
AEAEA

Look at pretest 3, and 1 2 is can be ignored. I wonder why test15's answer is like

2
AEAEE

yes i have the same question

We can put a south pole magnet in any black cell. Out of the white cells, we can only put south pole magnets at intersections of completely white rows with completely white columns. If a row (or column) contains at least one black cell and we put a south pole magnet in one of its white cells, then the south pole magnet will be able to pull a north pole magnet from the black cell to the white area at some point, since each black cell must be reachable by a north pole magnet by the problem requirement. While all white cells must be unreachable by north pole magnets in any possible sequence of moves.

Because North pole can't occupy white cell, and North pole can reach the cell which be occupied by South pole if they are in same Column or Row.

Consider this situation.

If you fill all cells with South pole and put a North pole in the centre cell, you cannot satisfy rule 3.

Actually pretest 2 is a good example and you should check it out.

because a sequence of operations must exist for every black cell such that it ends up being occupied by a north magnet

I'm assuming you are familiar with the application of dynamic programming on DAG. First, you need to find a topological sort of the graph (it exists only if the graph doesn't contain any cycle). Now do a forward traversal on the topological sort and for every value 'i' calculate the minimum value of the node that appeared on a path that ends at vertex 'i' (while moving forward). This can be calculated easily by DP. Now do a backward traversal on the topological sort (also reverse the edges) and separately calculate the minimum value of the node that appeared on a path that ends at vertex 'i' (while moving backward). Now for each node, you have the minimum value of the node that is somehow connected to this node. If this minimum value is less than the value of the node then you cannot assign a universal quantifier to the node (let's say a node is 2 and the min value is 1, then either x1 < x2 or x2 < x1. In either case you cannot assign A to 2), otherwise you can assign the universal quantifier to this node. See 79647809

what if n = 3, i = 1, a[i] = 2?

In C++ (-1%5) will be -1.

That is why you have to compute ((-1%5) + 5)%5 which will give 4 as output.

More on it here

I think you have not considered the case where some rows and columns might be empty

3 5
##...
.....
...##

I think you have not considered the case where some rows and columns might be empty

3 6
##....
......
....##

guest 1: $$$1 + a_{1 \bmod 2} = 1 + a_1 = 1 + 1 = 2$$$

guest 2: $$$2 + a_{2 \bmod 2} = 2 + a_0 = 2 + 0 = 2$$$

Amazing buddy it helped so much to solve this problem :) Keep going on like this for every difficult problem . thanks for this

Change return -1 to return 0. Exit code is whatever the main function returns. If it does not return 0, then it becomes a runtime error.