So, day 2 passed and the tasks were quite good again. I'm quite sad that I couldn't get the gold but it was a nice competition.
Problem 1 — Ephesus
You are given a string of N letters. Let's observe a k-partitioning of this string, that is we divide it in k parts (numbered 1, 2, ... k), and each of those parts is a substring of the string. The first part starts from the beginning of the string, the second starts immediately after the end of the first and so on. Every letter of the text is in exactly one of those parts and each part has at least one letter, that is the parts are non-intersecting, not empty and all of them together exhaust the given string.
Now you are asking the question "How many are the different k-partitions such that the k parts are strictly increasing in lexicographical order", that is the parts are such that the first is the smallest lexicographically, the second is the next smallest and so on. Let Xk be the answer for k. This problem is even harder : you must calculate the sum k*Xk with k being the values 1,2..N. That is you must calculate — (1*X1)+(2*X2)+...+(N*XN).
Example
Let the string be mcyyak.
Then for k=1, xk=1; for k=2, xk=2 (_mc yyak_ and mcy yak); for k=3, xk=1 (_mc y yak_); for k=4, xk=0; for k=5,xk=0; for k=6,xk=0. So the answer is 1*1+2*2+3*1+4*0+5*0+6*0=8
Output the answer modulo 10^9+7.
Constraints
Subtask 1 (5 points):
N<=3
Subtask 2 (16 points):
N<=700
Subtask 3 (36 points):
N<=5,000
Subtask 4 (43 points):
N<=10,000
Time Limit = 3s
Memory Limit = 1024MB
Test
Input:
mcyyak
Output:
8
My solution
Sadly I thought this would be the hardest problem and left it last, having only like 40minutes for it. I ended up with just 5 points and didn't manage to get any better solution. The real solution is some kind of DP in O(N^2) that I believe uses LCP and some tricks for fast summing and calculations.
Problem 2 — Fairy Chimneys
There is a graph with N vertices. There are edges between some of the vertices. However, edges (bridges) are quite weak so once you go through an edge it is broken and can't be used further. The value of a vertex is the amount of vertices you can reach and go back to the initial vertex.
There are Q queries of two types:
Add "a x y" : Builds a bridge connecting x,y. Query "q x" : asks for the value of vertex x.
Given N and Q queries your task is to find the answers of all queries.
Example
Let N=5. Suppose we have the following connections — "a 1 2" ; "a 1 3" ; "a 1 4" ; "a 2 4" ; "a 4 5". Then let's look at a few queries. Suppose we get "q 1". The answer would be 3, since the vertex 1 can reach vertices 1,2 and 4. The query "q 3" would be 1, since 3 can reach only itself (using no bridge). Then suppose we have "a 3 2". Now the query "q 3" would give us 4 since vertex 1 can now reach 1,2,3 and 4.
Constraints
Subtask 1 (14 points):
1<=N<=1,000
1<=Q<=5,000
Subtask 2 (18 points):
1<=N<=5,000
1<=Q<=500,000
Subtask 3 (23 points):
1<=N<=50,000
1<=Q<=500,000
Subtask 4 (10 points)
1<=N<=1,000,000
1<=Q<=5,000,000
All queries of type "q" start after all bridges are built.
Subtask 5 (35 points)
1<=N<=1,000,000
1<=Q<=5,000,000
Time Limit : 3s
Memory Limit : 256MB
Test
Input:
5 9
a 1 2
a 1 3
a 1 4
a 2 4
a 4 5
q 1
q 3
a 3 2
q 3
Output:
3
1
4
My solution
It took my about 4 hours to solve this problem, my solution includes a few union finds, merging many vertices into one, keeping trees of connected components and my complexity is in total I believe a little bit better than O(NlogN), however in theoretical worst-case I think my solution may perform as O(N^2). During the competition I could make it worst-case O(NlogN), however I conjectured that it's really difficult to make such test that would make me solution perform badly, so I decided to try it and it got full score in 2~2.5s. I don't know the intended solution of the problem, however only me and one other person have full score on the problem.
Problem 3 — Mediterranean
The path between Antalya and Iskenderun is a long straight line with adjacent cities between 1km. There are N passengers and the i-th passenger wants to get on a bus at city Bi and get off the bus at city Ei. A bus travelling from city D to city A can take passenger i only and only if D<=Bi<Ei<=A.
You are given the cities N people will get on and get off the bus and the routes of M buses. Your task is to find the maximum number of people can each bus can take. The task is online. You are first given the pairs of cities of the N passengers. Then for each of the buses you are given two numbers d and a. The bus travels from city d+shift to a+shift. In the beginning shift is 0, and after each query shift takes the value of the answer of the query.
Example
Take N=5. Let the pairs <Bi,Ei> of passengers are : <2, 8>, <4, 5>, <0, 6>, <1, 7>, <3, 9>. A bus travelling from city 3 to city 7 can take only one passenger (<4,5>), and a bus travelling from city 0 to city 6 can take two passengers. (<0,6>, <4,5>).
Constraints
All Bi and Ei are unique.
Subtask 1 (9 points):
1<=N,M<=5,000
0<=Bi<Ei<=400,000
0<=d+shift<a+shift<=400,000
Subtask 2 (23 points) [not sure about this subtask]:
1<=N,M<=50,000
0<=Bi<Ei<=10^9
0<=d+shift<a+shift<=10^9
Subtask 3 (32 points):
1<=N,M<=200,000
0<=Bi<Ei<=10^9
0<=d+shift<a+shift<=10^9
Subtask 4 (36 points):
1<=N,M<=500,000
0<=Bi<Ei<=10^9
0<=d+shift<a+shift<=10^9
Time Limit = 3s Memory Limit = 256MB
Test
Input:
5
2 8
4 5
0 6
1 7
3 9
5
3 7
-1 5
-1 7
-2 1
3 7
Output:
1
2
4
1
1
My solution
In my opinion this was the easiest problem in BOI2014. It took me about 30-40 minutes to solve it and implement it. Let's imagine that we keep an array F, and when a passenger <B,E> comes we say that F[B]=E. Now suppose a bus from L to R comes. What we actually want to find is the amount of numbers in F on indices between L and R that have value equal or less than R. Obviously that would give us the correct answer. Now this observation is enough for all except the last subtask since there is a known tree solution that works in O(log^2 N) per query for the described types of queries. To improve it we can use the fact that we do not have updates. Suppose we have sorted all people in increasing end of their interval, that is in increasing E. Now instead of saying that F[B]=E, we will simply do F[B]++, that is increase F[B] by 1. However we will do that in a persistent segment tree that keeps sums of intervals. Now suppose a bus from L to R comes. Well then we will simply find the version of the persistent tree where only all passengers with ending less than or equal to R have been added (there will be such since we add them in increasing order of their end). We can do that by binary in O(logN). Now in that tree we will simply do a sum query in [L,R] and that is our answer. Complexity is O(logN) per query, so O(MlogN) in total. To avoid using 10^9 memory you have to either compress the input or use dynamic tree (create only vertices that you use). I used dynamic tree and passed in 247MB.
So I got a total of 205 points on the second day, but sadly I was about 50 points short from the golds, and will most likely be the first silver medalist.
P.S. They extended the golds and luckily I got gold.
I can has contest added to Gym? When the test data are available... if they're available...
That would be nice.
in Problem 2 — Fairy Chimneys, can you enter the vertex more than once ?
I guess you could but it is easily proven that you have no reason to, it could only make your situaton worse.
1 — 2
2 — 3
3 — 1
2 — 4
4 — 5
5 — 2
in this graph the best path is 1 2 4 5 2 3 1. not 1 2 3 1.
Oh yeah, you are right, sorry :)
Hey Encho! Congratulations for the gold!
Speaking about the problem Fairy Chimneys, I was the other person to get 100 points on that problem and I think I had the intended solution. It took me around 30-40 minutes and only one submission to get from reading the problem to getting 100 points — I don't know how I did it so fast when (almost) no one else could do it in 5 hours. Anyway, here's my solution:
The solution is essentially offline: Start by placing the added edges one by one in order, and maintaining the union-find structure along the way. The edges which connect vertices which were already connected are not added. This way, in the end you will get an undirected forest.
Let's now assume (for simplicity) that the forest consists of exactly one connected component — a tree we will call T.
We will make another pass through all edges in that order and will now maintain the 2-edge connected components. Imagine that we now start with the tree T. Now we will add all the edges, in that order. If a new edge (u,v) is a tree edge (belongs to T), do nothing — since it is in T, it is the first edge to connect some two (1-edge) components of the graph and will not affect the 2-edge CCs. Otherwise, we should find a path through the tree from u to v, and merge all the nodes along the way into one 2-edge CC. This can also be done with the standard union-find data structure. It's not hard to see that if we can directly find the path from u to v without traversing any other edges, each edge of the tree T will be "merged" only once and this would give us the complexity of, I believe, O((m + n)α(n)). The problem now is to efficiently (in O(pathL)) find the path connecting u and v. It turns out this is not as hard as it seems:
First, assign one point as the root of T. Then, for each node x calculate the distance d[x] from the root and the parent p[x]. Now, in order to find a path from u to v, look at d[u] and d[v]. If d[u] > d[v] then let u := p[u], and v := p[v] otherwise. When u becomes the same node as v, you've found the path. Since some edges "disappear" from the tree, you'd think that we need to update the distances, but it turns out you can always just use the original distances calculated by using the entire tree T.
If, in the end, the forest consists of many trees, just do the same for every tree — you can do this because you know that these trees won't interact.
Solving this problem in just a little more than half an hour gave me a huge push towards the top of the rankings on the second day, and a lot of time for other two problems.