Only contest can keep us busy during quarantine. :)

Lands up solving none , Better luck next time Bro.

You do not get points for hacking. You only get one problem less solved if you get hacked.

So, if you hack somebody with same number of solved problems, you raise by one position in the ranking, because the other one falls down.

D was boring too.

and that is why we never focus on ourselves and lose ratings.

Don't focus on your friends rating , focus on problems to solve as you can... and if there new ideas for you try to learn it and keep that in your mind or write it in your note book that will make your thinking high not just your rating. Good Luck for you in this contest :)

Will you stop commenting this in every contest blog?

Exactly! those college/school hours are boring and gruesome.

Does it actually matter? would anyone prepare differently for a different number of problems?

Well We don't know if we will be alive To participate That Corona Contest

Practise. Practise. Practise. Try to solve problems of higher difficulty. Well, I was stuck as a newbie for quite a while. But after some practice, I managed to become a pupil. Initially, I used to solve 1 problem a contest, rarely 2, sometimes none. But now, after a decent amount of practice, I am able to solve at least 2 per contest. Just don't give up.

then upsolve the tougher ones. That's actually what makes you capable of solving them in-contest.

Two biggest differences are the 12 hour open hacking phase and the score distribution (every problem carries the same weight in educational rounds).

• Ranking:

Compared with normal rounds, edu(educational) round don't have a "score distribution"

Only two factors affect the ranking:"Problem solved" and "Penalty"

That means, solving 2 problems is always better than solving 1 problem

However, in normal rounds, problem F worths more points than problem A+B

• Hacks:

1.In the normal rounds,you can only hack if following conditions hold:

• You solved the problem,and you locked it

• The victim and you are in the same room

• The contest is not ended yet

However, in edu rounds, you can hack anyone in the open-hack phase(even if you didn't participate the contest), and you don't need to solve the problem."Room" doesn't exist in edu rounds.

2.In edu rounds, you can copy the code and test it locally, which means you can preview whether or not the solution will fail.

However, in normal rounds, it's forbidden to copy the code.

3.In normal rounds,a successful hack gives you 100 points and an unsuccessful cost you 50 points.

In edu rounds, hacks changes nothing to your penalty. The only difference is the victim loses a problem

• System test:

In normal rounds, system test begins shortly after the contest.All solution will be rejudged with pretests, maintests prepared by authors and successful hacks, if there are.

In edu rounds, system test begins after the open-hack phase. All solution will be rejudged by pretests and successful hacks.There's no "maintest"

Good luck for you! Maybe you can even be a specialist or an expert after this round!

13522 participaters <3

Effect of quarantine due to coronavirus.

Could you elaborate, please?

WeakObservationForces

D is hard to understand too.

I tried hard to find solution for C for 2*(n+m) moves.

That was not fault of statement language, but lengthy statement misguides sometimes to get obvious things wrong. Luckily I noticed later and was able to solve it.

I found problem C pretty clear. Rather than, problem D was more difficult to understand.

Exactly. I'd prefer:

• $$$\text{U} : (x, y) \to (x, y + 1)$$$

• $$$\text{D} : (x, y) \to (x, y - 1)$$$

• $$$\text{L} : (x, y) \to (x - 1, y)$$$

• $$$\text{R} : (x, y) \to (x + 1, y)$$$

:P

I'm so confused that I asked the author like this :p

(row, column) is standard when talking about matrices.

Well there is always a confusion for grids and 2d matrices. For mathematicians, it is more standard to use co-ordinate system, and for computer scientists it is more natural to think about indices / enumeration of the matrix / grid, which brings us to what it was in the question.

Doing CP, I think I have been swayed towards the computer science way, and found the directions straightforward. Maybe they should have added the line ( which is usually always there ), "Rows are numbered from 1 to n, from top to bottom, and Columns are numbered from 1 to m, from left to right".

The sample testcases for Problem C is good enough, so I believe explaining which is x and which is y is not important. Remember, only complain about the statement if the sample testcase is just as bad!

Same thing with problem E.

Solve for each bit separately, multiply results.

To solve for one bit, I did a linear DP setting 0s from left to right and counting ways to do so.

Essentially you only have two restrictions to deal with:

• First of all, for given position P you can't put 0 there if it is a part of some 1-segment.
• In case you decide to put 0 there, the previous 0 can't be too far to the left so you don't have some 0-segment being completely between those two 0s.

No inclusion-exclusion, but let's look at each bit separately.

Consider some fixed bit, we have some ranges $$$l \ldots r$$$ where this bit must be constantly 1 and some other ranges where this bit must have at least one zero. Let's delete the ranges of the first type and shrink the array. Now we have some ranges and in each range we must have at least one zero (if some of these ranges became empty after the shrink, answer to the problem is 0).

Now let $$$\mathrm{dp}[k]$$$ be the number of ways to fill the array up to $$$k$$$ such that there is a zero at $$$k$$$ and all the constraints that have the right endpoint $$$<k$$$ are satisfied.

I had a multiplication instead an addition and unfortunately I solved the problem 5 minutes after the contest ended.

It is a combinatorial problem.

Let's say we want to find the answer for block_size = i. This block will contain the same digits (lets name them with letter "a"). Because block_size can't be larger we want the adjacent digits to be different (lets name them with letter "b"). Now the picture is this: xxxbaa...aabxxx (x are the empty cells for now) You can have 10 possible values for "a". Total ways for a and b are 10 * 9. The rest cells can be anything, so we have 10^(N-i-2) ways to set them a value. Now for that fixed picture, ways are equal to 10 * 9 * 10^(N-i-2). But in how many ways we can fix a block of size "i" having two adjacent empty cells ? This can be done in N — i — 1 ways, so we multiply by that as well. Finally we need to add up (this is where I used multiplication by accident) the corner case where we have only one adjacent cell.

Here is my source-code: https://codeforces.net/contest/1327/submission/74125507

I used dynamic programming.

First, let's consider a block of size n. Then there will only be 10 ways to fit them. I will represent the block as X.

• X (10)

Then, if we consider a block of size n-1, There will be 180 ways to fit them.

• X? (10 * 9) 9 -> because it cannot be the same as X
• ?X (90)

Then, n-2, there are 2610 ways

• X?? (90 * 10) X? + ?
• ?X? (90 * 9) ?X + ?
• ??X (900)

You can see that the configuration ending with ? can be computed from the previous block size and the configuration ending with X can be computed naively.

So, here is the dp.

$$$dp_{n, s} = \begin{matrix} 10 * dp_{n+1, 0} + 9 * dp_{n+1, 1} & if : s=0\\ 10 * dp_{n+1, 1} & if : s=1 \end{matrix}$$$

s = 0 is for configurations ending with ?, and s = 1 is for configurations ending with X.

This doesn't work specifically for n-1, because the first ? (for ?X) is counted as 9 instead of 10, so make that a base case and use the dp starting for n-2.

we could use FFT to solve this problem let f be [1,9,90,900...],and g=f*f，then 10*g[n-i] will be the answer for the i th term

If you draw a directed graph with edges $$$(v, p_v)$$$, then each its component will contain one cycle. When we raise our permutation to the power $$$k$$$, an edge from $$$v$$$ will start pointing at a vertex $$$k$$$ steps away. The initial permutation is OK if and only if we have a unicolored loop.

Now, note that, for some loop of length $$$L$$$, if we raise our permutation to the power $$$m$$$ that $$$gcd(L, m) = G \ne 1$$$, we will be able to jump along this loop in such a way that we will only visit every $$$G$$$-th vertex, which reduces the number of vertices in our path and, hopefully, makes it unicolored.

For example, if we have a loop of length $$$36$$$ and raise our permutation to the power $$$9$$$, then, starting at $$$s$$$, we will visit only $$$(s + 9k) \mod 36$$$-th vertices of a loop. Our big loop as though breaks into $$$9$$$ small loops of length $$$4$$$. We can travel along each of them and check if any one becomes unicolored.

Now do it for every divisor of the length (since GCD of $$$k$$$ and some other number can be only a divisor of $$$k$$$) of every loop found. It wiil not TL as the number of divisors of a number less than $$$2 \cdot 10^5$$$ doesn't exceed $$$200$$$, and each such procedure takes linear time.

You do not need graph theory at all. Each permutation is the product of cycles. https://en.wikipedia.org/wiki/Cyclic_permutation

In each cycle a permutation p^k is like stepping through the cycle k times. So we need to find minimum k so that we start somewhere in the cycle, step by k while maintaining a color (looping around if needed), and eventually returning to our starting point.

For the last example our cycles are (1 7 3 5) (2 4 6 8). Our cycle colors are (5 8 6 7) (3 4 5 4).

In this case we only consider k that divides cycle length C. To see why consider repeatedly adding k mod C which is what we are doing. We end up stepping through all multiples of gcd(k,C). This gcd is less than k if k does not divide C so k was not optimal.

In general we have [Lagrange's Theorem](https://en.wikipedia.org/wiki/Lagrange%27s_theorem_(group_theory)) For this case we consider (cyclic) subgroups of cyclic groups (one for each cycle).

Push all points to 1 corner then iterate them over every grid of the board .it's no more than 2nm

Since the number of actions is quite big, you can collect all chips in one cell and then just visit all cells.

go to most up-left(1,1).then travel through all the squares and go to the most under-right(n,m).it is always smaller equal than 2*n*m

You can first use $$$n + m - 2$$$ operations to push all of the stuffs to the right-down corner.

Then travel the whole board with $$$n - 1$$$ $$$\text{U}$$$, $$$1$$$ $$$\text{R}$$$, (repeat it with $$$m - 1$$$ times).

Total times of operations will be $$$nm + n + m - 2$$$, and it will be sure less than $$$2nm$$$.

Hope it helps :P

You can always solve the problem in <= 2*n*m steps if you follow these steps.

1. Gather every chip to the top-left place. It should take (n-1)+(m-1) steps max.

2. Now move these chips together through the matrix in a spiral order. This should take n*m steps max.

Totals steps taken = (n+m-2) + n*m which will never exceed 2*n*m steps.

Both n and k should be of same parity and k*k<=n.

First of all, the sum of the first $$$k$$$ odd numbers is $$$k^2$$$.

Then, if $$$n$$$ is greater than $$$k^2$$$ and the remainder $$$k$$$ and $$$n$$$ have under modulo $$$2$$$ are the same, then it is sure that we can figure out a proper solution.

Otherwise, there's no solution.

Hope my explanation helps :P

let us assume odd number are 2a1-1,2a2-1,2a3-1,....2ak-1

as per equation sum up all n= 2*(a1+a2+a3+...ak) -k;

so a1+a2+a3...ak = n+k/2;

first check if n+k is divisible by 2 or not , if so then for all distinct a1!=a2!=a3..!=ak ,minimum sum of first k distinct positive number is k*(k+1)/2; if this sum is smaller than or equal to (n+k)/2 ,then ans is yes ,else no

Could you please elaborate a bit?

https://codeforces.net/blog/entry/75082?#comment-592022

Short answer cout<<((((n-=k*k)<0)||(n&1))?"NO":"YES");

Details answer

n -= k * k; // 1 + 3 + 5 + ... + 2 * k — 1 = k * k
if (n < 0) // if n < smallest sum of first k odd number
   cout << "NO";
else if (n % 2 == 0) // we can chose first (k &mdash; 1) odd number than choose last as n &mdash; sum
   cout << "YES";
else
   cout << "NO";

When you overcomplicate a simple question and become a part of the league of geniosities

I'm going to bookmark it now!!!!! AryaPawn orz

Since all colors are different, we need p[i] = i, smallest k for which this happens is 3.

It should be 3

answer is 3. p^3 = {1,2,3}. SO now you have 3 infinite cycles.

I spend lot of time on E, thinking of things like multinomials, but that would straight up blow the complexity. Also tried generating function, but gave up. Can you give a hint? Thanks!

Really? B was just a comprehension question. Masked in an annoyingly huge statement, was the real problem: perform the greedy mapping as described, and just check at the end if any princess and kingdom pair is unassigned. Implementation is trivial.

E was not easy at all. The only reason I solved E is because I wrote a brute-force and observed the pattern for small values. I still have no idea why the pattern is there.