I already get a lot of enjoyment from your wonderful problem, ainta!

And thank you, ecnerwala. You made my day.

BTW, I'm surprised that 9 IOI-participants solved it in only 5 hours, whereas I spent a whole day. Are they Legendary Grandmasters? XD

Yes. Generally,

• We know some values of $$$h_*$$$,
• then we can find the largest unknown $$$h_*$$$.

Repeat $$$N$$$ steps, then all $$$h_i$$$ are revealed.

Using Fenwick tree or Priority queues, the total time complexity is $$$O(N \log N)$$$.

The proof of the second observation is quite hard to explain for me. If $$$(h_1, \cdots, h_n)$$$ satisfies $$$r$$$-conditions, then:

• The top $$$k_1$$$ largest $$$h_*$$$ can be shuffled.
• The next top $$$k_2$$$ largest $$$h_*$$$ can be shuffled.
• ... and so on.

So, if $$$i$$$-th and $$$j$$$-th are incomparable, then we can find a sequence $$$(h_1, \cdots, h_i, \cdots, h_j, \cdots, h_n)$$$, which can be modified to $$$(h_1, \cdots, h_j, \cdots, h_i, \cdots, h_n)$$$ by some shuffle operations.

Therefore, if $$$i$$$-th and $$$j$$$-th are incomparable, and $$$|i-j| \lt K$$$, one of $$$r_i$$$ and $$$r_j$$$ must be increased when we swap $$$i$$$-th and $$$j$$$-th. That's a contradiction.

Let $$$d(i, j) := j-i$$$ if $$$i \lt = j$$$, $$$d(i, j) := N-i+j$$$ otherwise.

Assume $$$N \lt 2K$$$. Let $$$i_1, \cdots, i_t$$$ are the $$$i$$$s, such that $$$r_i = 0$$$. We know that one of $$$i_*$$$ is the index of the largest $$$h$$$.

Let $$$h_{i_1}$$$ be the largest. Then, $$$d(i_1, i_k) \lt K$$$ must hold. If not, then $$$d(i_k, i_1) \lt K$$$, which implies that $$$h_{i_k} \gt h_{i_1}$$$.

Surprisingly, such $$$i_1$$$ is unique, so we can find the largest $$$h$$$.

Problem A is soooo hard... Plz help me, Worteltje

What I briefly found out is:

• N < 2K, then the sequence is unique. We can find the largest one and reduce N.
• If $$$i$$$-th and $$$j$$$-th are incomparable, then (I claim that) there is a sequence $$$(h_1, \cdots, h_n)$$$ so that both $$$(h_1, \cdots, h_i, \cdots, h_j, \cdots , h_n)$$$ and $$$(h_1, \cdots, h_j, \cdots, h_i, \cdots , h_n)$$$ are satisfied $$$r$$$-conditions.
• Thus, if $$$| i-j | \lt K$$$, then $$$i$$$-th and $$$j$$$-th must be comparable.

And, I'm stuck. T.T Could anybody help for key-concepts?

Thank you for setting these wonderful problems. Unlike other geometry probs, E is so beautiful that I was impressed :D

Goal : A point $$$p$$$ and a set of $$$N$$$ points $$$S$$$ are given. We want to compute the number of triangles containing $$$p$$$.

We can easily know that the answer is "$$$N \times (N-1) \times (N-2)/6$$$ — (the number of triangles which do NOT contain $$$p$$$)". If the triangle $$$s_1 s_2 s_3$$$ does not contain $$$p$$$, then there is a straight line $$$l$$$ that splits $$$p$$$ and three points $$$s_1$$$, $$$s_2$$$ and $$$s_3$$$. Thus, we can design the algorithm below:

1. Consider the line $$$l$$$, which passes the point $$$p$$$.

2. Rotate $$$l$$$ about $$$p$$$.

3. When $$$l$$$ touches a point of $$$S$$$, compute the number of points that are on the left side of $$$l$$$.

4. Let $$$k$$$ be the number, then add $$$(k-1) \times (k-2)/2$$$ to the answer.

5. Do the step 2. to 4. until $$$l$$$ is rotated by 360 deg.

The naive algorithm is $$$O(N^2)$$$. But you can do it in $$$O(N lgN)$$$ with sorting points $$$S$$$ about $$$p$$$ — something like ccw-sort

Now, whole the problem can be solved. Just do the steps above about all the $$$N$$$ points. The time complexity is $$$O(N^2 lgN)$$$.

Hi ko_osaga!

Yes, the problem G was correct...

What a beautiful time complexity XD

Please looking forward to my cosplay :D

For the problem D in Div.1, Both ko_osaga (submission) and Konijntje (submission) got accepted. But for the input below, ko_osaga and Konijntje's outputs are different.

<< INPUT >>

b
aabaaaaaabaabbbbaaaaabbbbaaba

<< ko_osaga's output >>

6
1 16
2 1
2 7
13 6
7 15
17 8

<< Konijntje's output >>

7
0 10
9 18
17 3
2 15
11 0
0 6
2 0

Thank you very much! I really appreciate your help.

I explain about my equation.

I'm going to add a new player whose index is the smallest. There have already been s - 1 players. After adding a new player, the number of players should be s.

The first term, cp(s - 1, i) × pⁱ, describe the case when a new player is not in the set of i players who lose to the others. The 'new added player' must win all the i players who are in the set. Thus, the probability is pⁱ.

The second term, cp(s - 1, i - 1) × (1 - p)^s - i, describes the case when a new player is in the set. The 'new added player' must lose to all the s - i players who are not in the set. Thus, the probability is (1 - p)^s - i.

Would you tell me what is wrong?? Why should I add a largest-index-player like the official solution?

I have a question about the problem F.

When we compute cp(s, i), if we think that we add a new player with the largest index, then the following equation holds: cp(s, i) = cp(s - 1, i) × (1 - p)ⁱ + cp(s - 1, i - 1) × p^s - i.

But I thought that I add a new player with the smallest index. The equation below is what I made.

cp(s, i) = cp(s - 1, i) × pⁱ + cp(s - 1, i - 1) × (1 - p)^s - i

I cannot find why I was wrong... I've spent almost two days in order to solve this problem...

Could you tell me what I am doing wrong?

Could you tell me why considering only two problems set is enough (in Problem C)? Is it related to the range of k? If k = 20 then the solution does not work??

I think they have to fix this bug ;(

Following code gives AC

Joi.cpp

#include "Joi.h"

void Joi(int N, int M, int A[], int B[], long long X, int T) {
	for(int i = 0; i < 60; i++) MessageBoard(i, !!(X&(1ll<<i)));
	for(int i = 60; i < N; i++) MessageBoard(i, !!(i&1));
}

Ioi.cpp

#include "Ioi.h"
typedef long long ll;

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	ll ret = 0;
	for(int i = 0; i < 60; i++) ret += (ll)Move(i)<<i;
	return ret;
}