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) > 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)

and problems need clarification too!

Smh, the issue has been already raised almost 10 times before your comment.

I repeat my comment, but anyway : "You can see my greedy solution (but i cannot prove it). Answer my comment if you have questions. " 54046042

make $$$nxt_i = i + 1$$$ for each $$$i$$$ $$$(nxt_i = -1)$$$

Problem D is Windy Path (Problem L) from the 2016 ACM-ICPC Pacific Northwest Regional, with slightly higher bounds.

I think traversing convex hull and recalculating it after removing a point each time should do the trick.

Lemma: Given any point $$$P$$$ on the convex hull, there always exists a solution that starts at $$$P$$$.

Proof: We use induction (with the algorithm below).

Clearly we can do it for $$$N = 2$$$. For general $$$N$$$, let $$$X$$$ and $$$Y$$$ be the points adjacent to $$$P$$$ on the convex hull. Because the entire set of points lie on one side of both the lines $$$\overleftrightarrow{PX}$$$ and $$$\overleftrightarrow{PY}$$$, we choose $$$X$$$ to be our next point if the first direction is to turn left, otherwise $$$Y$$$ if we want to turn right. Then we can remove $$$P$$$ from the set of points and continue by induction on $$$N - 1$$$ points, as $$$X$$$ and $$$Y$$$ will still remain on the convex hull after removing a point.

Time complexity is $$$O(N^2)$$$. You don't need to find the entire hull; you can find $$$X$$$ and $$$Y$$$ in linear time using one step of gift wrapping.

I think olny the last one accepted in pre test.

the first sumbissions are skipped, only the last one is valid.

I did terribly, but I still think it was a good contest. Although CF going down all the time is really annoying, there are m1/m2/m3 sites that work pretty consistently. Also div2c/div1a wasn't that unclear. They explained anything that might be confusing under the samples.

Learn Russian :)

div2c was rather clear
but there are some noobs who cant read

This is how I solved it. First of all, notice that we can rewrite the $$$k$$$-extension condition for a pair $$$(i,j)$$$ to the following:

The important observation is that the right hand side of that equation does not depend on $$$k$$$, so for every pair we have an upper bound to the value of $$$k$$$.

Since this must hold for every pair $$$(i,j)$$$ such that $$$1 \leq i,j \leq n$$$ and $$$ i \neq j$$$, we conclude that an upper bound for $$$k$$$ is $$$\underset{ 1\leq i\neq j \leq n }{\min} \frac{\min(a_i,a_j) }{|i-j|}$$$, since $$$k$$$ should be less than all those upper-bounds in order to be a $$$k$$$-extension. Moreover, by definition we have that all $$$k$$$ that are less or equal than that number work. By choosing the biggest $$$k$$$ as possible (which is the smallest upper bound) we have our answer.

Now that we know what the answer is, the remaining question is how to calculate it efficiently. An idea to do this is to find a small amount of candidates for those pairs and calculate the upper bound only for those pairs. To do this you can prove that the pair that attains such minimum must necessarily be paired with either $$$a_1$$$ or $$$a_n$$$, this gives us only $$$2n$$$ candidates and we can simply try all of them.

Maybe I am wrong as I am from Phone, but it seems for 9, 5 it would give 101010111, which has shortest unique 3

Had the same idea, but realized it would fail for larger n values...

чтобы ТЛлили все решение не за O(n) / O(n log n)
имхо

Ну или для того, чтобы все поучились чистить инфу для каждого отдельного теста

D was not that difficult. If you can brute force, you will easily find the pattern.

However, if you are talking about clarity in problem specification, I agree 100%

In this task we just need to check, that topsorted-order of vertices is correct.

The minimum value of N and M is 2.

I think that case is not valid, n and m must be at least 2

for every item in the array, the value of k for that specific item = value/distance, where distance is maximum distance possible i.e either from 1st or from the nth item, now from all these values of k the minimum one is the answer. Pseudo code : i from 1 to n k=min(k,a[i]/max(n-i,i-1) print(k)

Edit nvm I read it wrong

as tfg said 0{1068}1 i completely overlooked that mybad