You added parentheses that aren't in the statement. It's modulo $$$N$$$, then plus 1, as normal precedence rules say.

Are you sure thats CF logo?

Morphy Chef Designed a Network: CHEFK1 . I think author solution is wrong for this problem . Critical test case: 22 242 .

Ans should be 22 . But my code passed which shows output 21 .

My connections: https://ideone.com/1xUKm4

If you have better answer give me the connection . Not only 22 242 . It does not follow pattern for n=22 ,24,25,28,34,37,38,39,40,42,44,45,46,48,49,50,52,54,55,56,58,59,60,62,6364,65,66,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83 .

My bruteforce code: https://ideone.com/ahag0p

My Accepted code: https://ideone.com/3vklml

DOOFST:

Subtask 1: Everyone hates each other, so everyone has to be in different groups at some point. Divide the bit string in half, left half gets all $$$0$$$, right half gets all $$$1$$$, then recursively divide each half again. You get something like

00001111
00110011
01010101

Subtask 2: In short: it should be a complete k-partite graph for some k.

In not-short: If there is no edge between some pair of people, then these people must belong to the same group every time. Let's "invert" the graph, in every pair where there was an edge, now there's no edge, and vice-versa. Find the connected components in the inverted graph, you get this problem.

After we've found the inverted connected components, let's return to our original graph. If there is any edge that connects two nodes in the same inverted connected component, then answer is $$$-1$$$. Otherwise we can consider each inverted CCs as a single node, every inverted CCs hate each other, so now the problem is literally subtask 1 again.

I couldn't solve DODGERS, but I liked DOOFST a lot. Try to think for a few minutes, before opening each successive hint.

DODGERS: Let's solve subtask 1 first.

For each guest, let's find the closest left and closest right to that guest that they dislike. Now each guest can be represented as an interval $$$[Lguest, Rguest]$$$ in which they'll think the game is fair iff only the guests in that range are invited. We want to know how many guest think the game is fair for each query $$$[L, R]$$$.

Let's think of it another way. Let's think of each query $$$[L, R]$$$ as points $$$(X, Y)$$$ on the 2D plane $$$(X = L$$$ and $$$Y = R)$$$. We have $$$O(N^2)$$$ possible points. For each guest, they will answer YES for a specific set of points. These points form a rectangle. So we have $$$N$$$ YES-rectangles, each corresponds to a guest.

Let's get back to our question: "Given a query $$$[L, R]$$$, how many guest say YES for that query?". We rephrase the question as "Given a point $$$(X, Y)$$$, how many YES-rectangles does this point lie in?".

This is now solvable offline with a line sweep + a range addition/point query data structure in $$$O((N+Q)logN)$$$. Fenwick is very fast.

Subtask 2 is just subtask 1 with persistence.

For DODGERS, shouldn't it be how many intervals, lie completely inside it or lie partially intersecting ?

First let's solve it in O(SKN * logK). We have dp[i][j][k] = including i first elements, we have sum of cost j, and chose k elements. In other words, dp[i][j][k] = sum for ii < i for possible sequences seq of size k with elements that we chose at least once summing up to j and elements we chose 0 times having seq[x] = 0 of (value[ii]^s[ii] / (s[ii]!)). dp[i+1][j+cost] is (the convolution of 1 + (val[i]*x)^1 / 1! + (val[i]*x)^2/ 2! + ... and dp[i][j]) + (dp[i][j+cost]). The answer is sum of dp[i][j<=S][k] * k!. Link

But that wasn't enough for my ntt code to pass, even though it should have been :P

With my ntt being too slow for this problem I managed to optimize it to a slightly better complexity. We can use 2D FFT/NTT to convolute matrices and solve this problem convoluting matrices of groups of size X. So for each group of size X we'll compute all the subsets that it has and put the proper things in the matrix, then we convolute it with what we had before. This has complexity O(2^X*K*(N/X) + (N/X)* SK * logSK). Choosing X as log(S * log(SK)) we can get complexity O(SKN) * O(log(SK) / log(S * log(SK))) and that's slightly better than the previous solution. Link. Actually, I didn't calculate the complexity before getting AC, I just plotted the function of the complexity in google and chose the minimum from there :P

I found that confusing as well. Did not really have the time to for good scores, but the way I understand it is this: if the three registers are always added to the list in a fixed order and in the end we take every third element of the list, that means that really we are just listing all the values of a single register during the run of the program. If an instruction does not change that register, we get consecutive equal values, so in order to get a list of valid triples, the program needs to change the register on at least 2/3 of its instructions, which explains why the fully random generation takes so long.

I don't think I can help with this as long as there isn't a mistake in the description — I just edited what I was given and didn't check if it makes sense or works nicely. Spending hours on generating tests in special problems isn't that rare.