Orz

memset0 can AK IOI!

No, the information in your nick is false.

But why? The latest Mathforces was quite good!

I guess he will consider, if you give him some RAMADAN special biryani xD

It's hard if not impossible to consider the prayer time. Because the prayer time in every country are not same and people from all over the world participate here. And every minute is a prayer time in somewhere in the world. So when do you suggest to schedule the contest?

Moreover, this platform have people from many religion, culture and region. The platform must not run by considering any religion, culture or region. The platform should be secularist and International.

Hope is a good thing.

I completely agree with you. Hope there will be some problems like find the equation of Euler line $$$\dots$$$

Have I misunderstood you? Do you want Mathforces?

Fortunately it won't affect div1 much.

[deleted]

This is not my contest. I just test these problems for the correctness.

good schedule for CSKA and Zenit fans

Maybe we can finally switch to using dynamic cloud providers instead of fixed hardware in the ITMO basement?

Sorry about the technical issues, it seems some misconfiguration happened in process while I jump between servers. I work hard to diagnose and fix it.

The notice about the micro-sites (green information bar in the header) appeared about 1 hour before the contest. Also I remind it in the official Telegram channel. Am I right that m1/m2/m3 work good without technical issues? I think it means if you follow recommendations you was able to read and solve the problems without any timeouts.

.

Then why didn't you register in advance? It is not that the site has been down for the whole time it has been able to register.

Thank you. I was sure that I saw this problem in some contest but couldn't remember the exact contest.

The bounds is not important. I'm sure that almost people have the same solution for both.

Can you please explain why it was so hard to understand? It got two clarifications and I could not understand why.

Hint: Solve the problem assuming there are no missing values, after that it will be easy to extend it to the general case.

You can see my greedy solution (but i cannot prove it). Answer my comment if you have questions. 54046042

Build a graph for relative order of p : if p[i] < p[j], there is an edge from i to j

If there is a valid topsort order, there is the answer

We build an edge from i+1..next[i]-1 to i and an edge from i to next[i].

However, there are O(n^2) edges.

To solve the problem, use segment tree to represent a range of nodes build two edges from [l..r] to [l..mid] and [mid+1..r] so there will only be O(n) number of nodes (not more than 4*n)

EDIT: Hope I won't get TLE on systest :C

EDIT2: Accepted :D

Couldn't get an AC in the contest. I used a greedy algorithm.
Let us try filling the array smallest to largest.
We can observe that if next[i] = j, than for any x, i < x < j , next[i] <= j.
Also, permutation[x] < permutation[i] < permutation[j] . We can just fill the subarray (i+1 to j-1) first, and then fill i.
We can then go on working on array starting from j.

int small = 1, flg = 0;
void solve(int st, int en) {

	if(st > en || flg)
		return;
	if(nex[st] == -1)
	{
		ans[st] = small++;
		solve(st+1, en);
		return;
	}
	if((nex[st] > (en + 1)) || (nex[st] <= st))
	{
		flg = 1; // determines invalid case
		return;
	}
	solve(st+1, nex[st]-1);
	ans[st] = small++;
	solve(nex[st],en);
}

When? I think this would cause huge inflation.

That would lead to rating inflation.

This has never happened before

Why? The only upside is that it would make everyone "feel good".

Try to write a brute force and observe patterns. ;)

The key is the number z = (n — k) / 2.

You build a string with [z zeros, a one, z zeros, a one, ...]

e.g. n = 14, k = 10, 00100100100100

You can repeat the pattern 0000...001 over and over up to n length.

The number of zeros in the repeating pattern is (n-k)/2.

I am actually surprised why there has not been more solves. Makes me doubt the solution

Say you are given $$$n$$$ and $$$k$$$. Set $$$d = \frac{n-k}{2}$$$, $$$l0 = floor(\frac{d+2}{2})$$$, $$$l1 = floor(\frac{d+1}{2})$$$. Now the string of $$$l0$$$ zeroes, $$$l1$$$ ones, repeat works. The special case is $$$k=1$$$, in which case you can only have one 0 or 1, and can use 0111... as your string.

This works, since the string is cyclic with length $$$l0 + l1 = d+1$$$, and the start-point x (zero-indexed) of some substring mod $$$d+1$$$ uniquely determines its content, and the content for all residues is different. Therefore WLOG $$$x \leq d$$$. Let $$$s$$$ be the length of the substring. We must also have $$$x + s + (d+1) \gt n$$$, since otherwise the string occurs again $$$d+1$$$  characters later. So now we have: $$$s \geq n - x - d \geq n - 2d = n - (n-k) = k$$$

Completing the proof.

Submission: 54040228 (function count is unused, I just used it to test the code)