good luck :)

I was the fifth person to register for the round.

I am wondering why the first four didn't comment.

Congratulations man, you have achieved a lot at these young age. You can now join avengers

I decided to test rather than participate because it's too early for me...

O_o

O_o

McDic orz

O_o

Who do you want to give the round to and how is it possible to give a round to someone?

:(

Ah, I see you are a man of culture as well.

Or maybe you failed and raised to International Master.

You (barely) avoided! Congrats!

tester

Get asked.

contribute

Click "Propose a contest/problems".

I usually follow https://kontests.net/ which keeps me updated on running/future contests on most platforms.

I want to ask it too.

Is it rated? Yes, It is RATED for all.

Yes, how many problems in round?

oho!,where no update.

Three problems in Div1.

I am back...

That wouldn't work all the time, just most of the time, which seems to be your problem. If a problemsetter can't be online the whole evening because there's something else planned before/after, choosing a slightly different time could be necessary.

How much are you betting?

Yeah I did the same thing

Or with 190E - Контрнаступление, if you are old enough :)

I think it's also similar to 1228D - Три множества from McDic's last round xd.

rip

All of the integers are all of the integers. If it was in each box, there would be an additional qualifier "in each box". Later, it's mentioned that "all $$$a_{i, j}$$$ are distinct" in a separate paragraph and there's no distinction made between $$$i$$$ and $$$j$$$.

It took me a while to notice that they're distinct, but it's correct the way it's written.

Yeah, it could've been clearer, sorry.

If n has more than 1 prime factor ans is 1. Else ans is the only prime factor n has.

I was doing a dp on processed boxes: added to dp[mask] a number left "unused" if we perform non-cyclic reordering on the boxes in the mask (i.e. normal reordering without one transfer). But I was lost somewhere in building an answer from dp transitions :/

If the sum of all numbers is not divisible by $$$k$$$, then the answer is No.

Otherwise, let $$$S$$$ be the sum of all numbers. The sum of integers in each box must be $$$S/k$$$

Suppose the first box sum is $$$S_i$$$. If we decide to take some integer $$$c$$$ out of it, then obviously its sum will be $$$S_i - c$$$, and we need to put the number $$$S/k - S_i + c$$$. Given that all $$$c_i$$$ will be distinct, then this required number should be in at most one box.

Now, if the required number is $$$d$$$ and its taken from some other $$$j$$$ box, then we should find where $$$S/k - S_j + d$$$ is. We will take $$$d$$$ out of that box and solve the same problem. This will lead us to a cycle, until we reach the box $$$i$$$. Obviously, if some integer is not found within all the boxes, or we have to take an integer from a box that has already been modified, then it's not possible.

Given that $$$1\leq k\leq15$$$, we can apply a bitmask dp. We will take any box that has not been modified and try to take every possible integer out of it and apply the process explained above. Once we obtain the cycle, we repeat the dp with the other boxes that have not been modified (i.e. don't belong to the cycle).

My solution for D is different. It will be available on editorial.

I managed to debug and simplify my solution and I think this problem is really beautiful: 64426704

Let's call the set of $$$K+1$$$ numbers added in one step a block, and set of $$$K$$$ consecutive blocks a superblock. Each block contains $$$K$$$ low values (those are the $$$u_i$$$), and $$$1$$$ sum.

Now comes the guesservation: the $$$i$$$-th superblock contains $$$K^2$$$ low values from interval $$$[i*(K^2+1)+1, (i+1)*(K^2+1)]$$$, e.g. there is exactly one number missing. When we find this missing number, we can easily find the sum of any block within this superblock (because it consists of at most two arithmetic sequences).

As the sums are increasing, it is obvious that the number missing in the $$$i$$$-th superblock is the sum of the $$$i$$$-th block. The $$$i$$$-th block belongs to $$$i/K$$$-th superblock, so we can solve this recursively with the initial condition that the sum of $$$0$$$-th block is $$$K*(K+1)/2$$$.

The algorithm is as follows: we find the superblock to which $$$N$$$ would belong if it was a low value (it's $$$\frac{N-1}{K^2+1}$$$), let's call this $$$x$$$. If sum of the $$$x$$$-th block is $$$N$$$, then the answer is $$$(x+1) * (K+1)$$$, otherwise we can find the answer because we know what is the missing number in our superblock.

The complexity is $$$\mathcal O(\log N / \log K)$$$ per test case.

check at n = 6 the answer should be 1

for 6 answer is 1. your solution prints 2.

The answer isn't always the smallest prime divisor of n. Take the case n = 6, for example. If we paint tile 1 black, then tile 3 and tile 4 have to be black. Since tile 4 is black, tile 2 and tile 6 are black, and since tile 3 is black, tile 5 is also black. So all tiles have to be the same colour.

The correct answer is finding the gcd of all non-unity divisors of n.

try n = 6.

1,3,5 should be the same 2,4,6 should be the same 1,4 should be the same

therefore all should be equal.

Your code says 2.

It is really a wonderful problem! I did find the pattern but have no time to code — a sad story.

Yeah

It passed and I feel so sad, but if it hadnt passed, I would have been sad also. Bad day T^T

It relates but I am not sure how.

Yes it does, when there are more than 1 factor, then they happen to meet at some number, which is not 0 modulo the first factor; hence a imbalance and causes a chaos which leads to everyone having same color.

When 1 factor: No chaos. So number of colors same as the factor.

It is exactly the same thing.

okay, im wrong

You have many changes. Just use the compare feature.

I think that restoring the answer is very easy to implement in this problem. Also, here it's much better for the checker: if somehow participant finds the answer while author's solution has bug and doesn't, there is way to find this out only if we return answer, too.

Btw, never saw you posting a comment with positive feedback about problems on CF, but saw a lot of negative. Are all problems on CF so bad?

A number n with a prime factor around 10^9 but this prime factor is not n itself.

It was in cf round 120

I think there's an (important) difference — there you have all the light edges, here you have all the heavy edges. Since counting connected components over the light-edge graph is relevant, there you can just DFS the graph itself, here you have to DFS the anti-graph formed (which is a harder problem because the antigraph may have upto n(n-1)/2 edges so you need some tricks).

No this is question opposite of Div2D

If each letter occurs even number of times in total the answer is possible.

Now, iterate over string. If $$$s1_i$$$ is not equal to $$$s2_i$$$, you find an element in either string that is equal to $$$s1_i$$$ ( and by the first condition you are guaranteed that such an element exists), and bring it to $$$s2_i$$$, either by swapping directly if it is in $$$s_1$$$, or by swapping using an intermediary element (if it is in $$$s_2$$$).

Submission: 64389826

I performed worser but I’m not sad

I came up with a similiar idea to a similiar problem before XD 34872588
Its worst case time complexity is $$$O((N+M) \log N)$$$. ( $$$O(N+M)$$$ data structure (set,vector access) operations, to be precise).
I have claimed it here, but I didn't wrote the proof down QAQ.

This inner loop from your code is the only nontrivial part in time complexity analysis because all other parts are obviosly $$$O((N+M)\log N)$$$. To know its time complexity, we just need to count how many times we access $$$cur$$$.

for (int w : cur)
    if (!g[u].count(w))
    {
        to_del.push_back(w);
    }

Case 1. When g[u].count(w) == 0, $$$w$$$ is then removed from $$$cur$$$. The number of accesses from this case is $$$O(N)$$$.

Case 2. When g[u].count(w) == 1, an edge $$$(u,w)$$$ exists. Since each $$$u$$$ is taken out exactly once from the queue and we loop through $$$cur$$$ exactly once for each $$$u$$$. We have an injection from an access to an edge. Therefore, the number of accesses from this case is bounded by the number of edges $$$O(M)$$$.

So the total number of accesses to $$$cur$$$ is $$$O(N+M)$$$.
Correct me if I am wrong :)

Even I am facing the same problem.

You cannot mark j as visited before checking all edges of j. For example, imagine a graph of size 4 with the following 0-edges (not 1, it is easier to write only the 0-edges):

1 3
2 4
3 4

When visiting 1 you set 3 as visited, when visiting 2 you set 4 as visited, then you will never consider the edge 3-4.

Your algorithm answers 2 instead of 1.

Instead of looping through every possible edge, I did a BFS checking only the edges reaching unvisited vertices, this way you can avoid trying all the edges. When you try the edge (a,b) you will have 2 cases.

Case 1: it is of weight 0, therefore you add b to the queue and never try any edge reaching b, in this case number of unvisited vertices decreases by 1.

Case 2: it is of weight 1 and you will do nothing and try b again later, in this case the number of remaining edges of weight 1 decreases by 1.

Therefore you either decrease the number of unvisited vertices or the number of remaining edges of weight 1, so it is in the order of 2*10^5 operations.

The same thing in C and AC in D, -157. Love CF scoring distribution.

I ran your code for $$$K=2$$$ and $$$T=100000$$$ random values of $$$N$$$. You store values of 24 million states in the hashmap and call your "solve()" function one hundred million times. I've experienced some problems where the number of tests was unnecessarily high (232C - Графы Доу in particular), but this sounds too inefficient. In comparison, my solution has a clean non-branching recursion with no memoisation required.

"after years"

This has happened before, I remember Radewoosh and Um_nik at the top. But it's never lasted long ;)

Don't worry — he'l be coming back for as long as he lives.

Exactly 2000

Waiting for that since eternity :(

Div1 B is somehow the same as 190E and 920E , well, the code is the same at least.