Good Luck Coders ;)

since ko_osaga will make virtual participation to day 1 or day 2 of JOI spring camp , so I think there will be a mirrors after the contest.

Unfortunately, there won't. But you can upsolve after the contests.

They traditionally opened judge servers, as far as my memory goes.

And, as my name is called, I'll also advertise it here: https://codeforces.net/blog/entry/66014

Definitely! The team will be selected practically just with the spring camp results.
I will participate in it and very looking forward to it :)

P.S. I, of course, want to compete even with open contestants, so I am really looking forward to seeing many open contest participants and I definitely recommend to participate. It's really a high-quality contest.

They will eventually be on https://contests.ioi-jp.org/joi-sp-2019/index-en.html.

A link to the registration page will appear on this page about 30 minutes before the beginning of the contest.

And the contest begins in about 35 minutes: March 20, 2019 to March 23, 2019 10:00-15:00 +0900 (JST) 01:00-06:00 (UTC/GMT)

Edit: this is going by what is on the contest site, there is discrepancy with the blog...

Can you describe some solutions?

I've solved this contest in analysis mode, and it was really hard to push my solution to get OK (because it makes ~$$$41\,000$$$ queries)

I don't know but I expect that it is 90 minutes after contest (10:30 — 15:30 UTC+9), because such information is written in contest information page.

I've used some __int128 + hack that if you want to make a fraction (A, B) with $$$B > 10^9$$$, just convert it to fraction

((A * 10^9 + B — 1) / B, 10^9).

Break the naan evenly(by happiness) into N pieces for each person.

Call p(i,j) as the position of the jth cut for the ith person The B of p(i,j) should be N*v<=2e8

Repeat j from 1 to N, take the smallest p(i,j) out of the remaining people and stop considering i afterwards

It is easy to see that it works (its just a slight modification to the greedy)

it starts in 13 minutes

It should be OK now.

Could you please tell me what or in a better way, where is the analysis session you mentioned? :D

It was hard but I guess not the hardest. Though hard to explain.

For each query $$$[L, R)$$$ I find $$$i, j$$$ $$$(L \leq i < j < R)$$$ which both can see each other and $$$H_i - H_j$$$ is maximum. (To solve the whole problem reverse the array and run this again)

In this way $$$i$$$-th antenna can communicate with antennas in $$$[i+A_i, i+B_i+1)$$$ so make it two event. Add this antenna at $$$i + A_i$$$ and remove it at $$$i+B_i+1$$$. Set $$$c_i$$$ to $$$h_i$$$ if this antenna is present now and $$$-inf$$$ otherwise. Set $$$d_i$$$ to currently maximum difference value $$$H_j - H_i$$$.

Now sweep from left to right and process events. After processing events till $$$j$$$, the answer for every queries $$$[l,j)$$$ is $$$min(d_l, d_{l+1}, .., d_{j-1})$$$. Also for the $$$j$$$-th antenna and every antenna $$$k$$$ which $$$j - B_j \le k \le j - A_j$$$ update $$$d_k$$$ to $$$max(d_k, c_k - H_j)$$$ (notice that if $$$k$$$-th antenna is not present then $$$c_k$$$ is $$$-inf$$$ and $$$d_k$$$ doesn't change).

We can implement changes to array $$$c$$$ and $$$d$$$ using segment tree with lazy propagation. So it's done in $$$O(nlgn)$$$ time complexity.

I got 74 points in contest, and there was a little typo. I upsolved it.

Let $$$X[i]$$$ be maximum $$$j$$$ that satisfies $$$A[1]+A[2]+...+A[i]+B[1]+B[2]+...+B[j] \le S[i]$$$. Likewise, $$$Y[i]$$$ be maximum $$$j$$$ that satisfies $$$A[1]+A[2]+...+A[j]+B[1]+B[2]+...+B[i] \le T[i]$$$.

Put a blue point in $$$(i, X[i])$$$ with score $$$P[i]$$$ and red point in $$$(Y[j], j)$$$ with score $$$Q[i]$$$.

Order of steps can be represented by a path from $$$(0,0)$$$ to $$$(n,m)$$$ in lattice graph. $$$(i,j)$$$ means you already have done $$$i$$$ steps of IOI Donburi and $$$j$$$ steps of JOI curry.

For a path, the whole score of process is (sum of scores of blue points above or on the path) + (sum of scores of red points below or on the path).

It can solved directly with segment tree and lazy propagation in $$$O((N+M) log (N+M))$$$ time, but there are something to handle, so I tried to make it easier.

For each red point in $$$(x,y)$$$ with score $$$q$$$, make it blue and change its location to $$$(x+1,y-1)$$$ and change its score with $$$-q$$$. After this process, only blue point remains and the problem becomes easier. After calculate answer, you should add $$$q$$$ for each red point. Then you can get the same answer with original problem.

Only blue-point problem can be solved by segment tree. Time complexity : $$$O((N+M) log (N+M))$$$ .

use MO's algorithm

It can be solved by (CDQ) divide-and-conquer.

Sort all students and queries together by one of the 3 parameters. Recursively divide them into halves according to that parameter.

For each sub-problem obtained from above, consider only students in one half, only queries in another half. Re-sort them together by one of the two remaining parameters. Then handle each of them by operations on a segment tree based on the last parameter.

you can use ordered_sets in segment tree.

Interesting solutions. Thanks.

Here is my method :

Represent students as points $$$(x, y)$$$ where $$$x = S_i$$$ and $$$y = T_i$$$.

In subtask 2, we want to know the number of such points in $$$Q$$$ infinite rectangles covering all points $$$(x, y)$$$ with $$$x \geq X_i$$$ and $$$y \geq Y_i$$$. Sort students/points by decreasing $$$S_i$$$. Sort rectangles by decreasing $$$X_i$$$ and process them in this order, adding step by step "new discovered points" in a 1D segment tree on ordinates.

After adding all "new points discovered with $$$x \geq X_i$$$", do a Range Sum Query on $$$[Y_i ; +\infty[$$$ to know the answer for this rectangle. Final complexity is $$$O((N+Q+Y_{max}) \log Y_{max})$$$.

Subtask 3 : Thinking on paper, we see that we're now querying the intersection of an infinite triangle and an infinite rectangle. I count the number of points in the "big triangle" and I substract the number of points in the "little triangle" below the rectangle. I use two segment trees, one on $$$T_i$$$ values, other one on $$$S_i + T_i$$$ values. It needs two different passes with different sorting. There are some rectangles which should be treated as in subtask 2 instead (when $$$Z_i$$$ is useless).

Substask 4 : I used dynamic segment tree, it's slow but it pass the TL.

Code : https://oj.uz/submission/102091

I got a solution:

Lets divide our queries into 2 types : a+b>=c and a+b<=c

1. For type 1(a + b >= c) : we could only consider a and b, thus the answer could be easily found(use sweeping line and BIT or else).
2. For type 2(a + b < c) : consider the image below
   
   \|
   \|
   \|"This area is what we want"
   \
   |\
   ----------------------------------------------- "limit A"
   |\
   |\"limit C"
   "limit B"
   
   and this is equal to area X — area Y
   \
   \
   \"Area X"
   \
   ----------------------------------------------- "limit A"
   \
   \
   \"limit C"
   \"Area Y"|
   \|
   \|
   \|
   |
   |\
   |\"limit C"
   "limit B"
   And it's easy to find Area X and Area Y(same technique as you find the answer for type 1)

Also, transportation is a cool innovation because now we can see, there can be a lot of problems like on distributed code jam at IOI format :)

I assume you are talking about Day 3. Q1: Centroid Decomposition.

Choose a centroid, and assume you pick nodes from subtress of at least 2 children from it, or you pick the node itself.

Then you can do greedy, greedily pick the node that descreases the cost most. By some small-to-large, you can compute the costs in O(size*lg).You then update the answer of [1,size], so solving a subtree is O(size*lg), and overall complexity is O(N*lg^2)

I think you need special handle for E=1, but shouldn't be trouble. For E>=2 we only pick leaves actually, but i don't see how to use that.

Q2: Simple DP.

Note that there exists a optimal solution that does all "set range" before "flip range". Also, all "set range" do not overlap itself, and same for all "flip range".

Consider that you have x "set ranges" and you have to open/close range for y "flip ranges". Then the cost is x+ceil(y/2).

Run DP from left to right, maintain dp[i][j], which is the minimum x+y you can do, for prefix i,

j=0: no "set ranges" are opened

j=1: You have opened a range for "set range to 0" and haven't closed it

j=2: You have opened a range for "set range to 1" and haven't closed it

Then you can do transition, as following:

for(int i=1; i<=n ;i++){
	for(int j=0; j<3 ;j++) dp[i][j]=1e9;
	for(int j=0; j<3 ;j++){
		for(int k=0; k<3 ;k++){
			int cur;
			if(k==0) cur=(a[i]-48)^(dp[i-1][j]&1);
			else cur=(k-1)^(dp[i-1][j]&1);
			dp[i][k]=min(dp[i][k],dp[i-1][j]+(k!=0 && k!=j)*2+(cur!=b[i]-48));
		}
	}
}

I tried the best to explain :)

Sort by $$$C$$$. Let $$$F(i, j)$$$ be a max. possible cost obtained from interval $$$i, j$$$ (paying exactly $$$2(C_j - C_i)$$$ for circular tour). Let $$$opt(i)$$$ be the maximum $$$j$$$ such that $$$F(i, j)$$$ becomes maximum.

You can prove that $$$opt(i) \le opt(i+1)$$$, and you can calculate $$$F(i, j)$$$ in $$$O(\log N)$$$ using persistent segtree, thus you can use D&C optimization to solve the problem in $$$O(N\log^2 N)$$$.

1. Erasing an element also provides your some information. So you don't need to erase everything in the set when you solved $$$[l, r]$$$ and want to solve $$$[l, mid]$$$ and $$$[mid+1, r]$$$.

2. You want to split some set into two halves. If one of them is full, you don't need to make a query to know which set it belongs to. To avoid hacks, random shuffle the set before making queries.

3. Do not set $$$mid = (l+r) / 2$$$, try something like this: $$$mid = l * ratio + r * (1 - ratio)$$$.

My code

With some careful implementations and dirty optimizations, we can make it into about $$$9.705 * 10^5$$$ queries for $$$n=43000$$$ and $$$9.952 * 10^5$$$ queries for $$$n=44000$$$.

My code

Maybe your download was corrupted? It is working fine for me. Try re-downloading.

That problem is from Spring Camp 2018. Anyway, I don’t know :/

RockyB U can submit here btw: https://dunjudge.me/analysis/problems/1555/