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.me/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 \lt 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 \lt 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