Hello everybody,

I like participating in Marathon-type competitions and in the near future I will participate in a few more. However I feel like my solutions are always not good enough. I've been to a lecture of Psyho where he explained some approaches. I know in theory things like Beam Search, Simulated Annealing, Hill climbing. However when I face a marathon task I really have a hard time to choose which one to use and more importantly, how exactly to construct it.

Take a simple NP-Hard problem as the Travelling Salesman. I have no clue how to solve it using any of the above techniques, and I would probably end up using some randomized short backtracks, which would end up with a horrible score.

I would be very grateful if someone could give me some tips, and perhaps explain some not-too-hard approach for the Travelling Salesman problem, so I can learn from that.

Thanks in advance! :)

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.

So Day 1 passed and the problems aren't online. As they were quite tough I decided to put them here and see the community's solutions. I don't have the english papers and I don't have much time to write so I will just describe them shortly and try to include the most useful information.

Problem 1 — Diameter

You are given a weighted tree of N nodes and a number K. You must perform a K-partitioning. That is you must choose K non-empty, non-intersecting subsets of nodes that cover all nodes. Each subset is called a partition. A diameter of a partition is the longest distance between a pair of nodes in the partition. A partition doesn't have to be connected, so distance is defined as the distance in the initial tree. A diameter of partitioning is the longest diameter of all partitions. Your task is to find the minimum possible diameter of K-partitioning.

Constraints:

1<=N<=260,000

1<=K<=N

1<=weight of edges of tree<=1,000

Subtask 1 (10 points) : K=1

Subtask 2 (15 points) : K=2

Subtask 3 (30 points) : N<=110,000

Subtask 4 (45 points) : no additional constraints

Time Limit : 1s

Memory Limit : 256MB

Example

Input:

5 2

1 2 1

1 3 1

2 4 1

2 5 1

Output:

2

Input format is : n,m then n-1 lines "a b c" denoting an edge from a to b with weight c.

My solution

During the competition I couldn't find any polynomial-time complexity solution, so I simply solved the K=1 subtask in which you obviously have to find the diameter of the original tree which is a trivial problem.

P.S. Binary search for the answer possibly?

Problem 2 — Hittites

You are given N codes in the form of strings of lower-case latin letters. You need to calculate the amount of different strings of length K that have at least one of the given codes as a substring. Print the amount modulo 10^9+7.

Constraints:

Subtask 1 (13 points):

1<=K<=5

1<=N<=10

Subtask 2 (19 points):

1<=K<=5,000

1<=N<=26

Length of each code is exactly 1.

Subtask 3 (29 points):

1<=K<=5,000

N=1

Sum of lengths of the N codes is at most 2,000.

Subtask 4 (39 points):

1<=K<=5,000

1<=N<=2,000

Sum of lengths of the N codes is at most 2,000.

Time Limit = 3s

Memory Limit = 256MB

Example

Input:

3 2

aa

dbe

Output:

52

Input format is : n, followed by n lines with one string on each — the codes.

My solution

I managed to solve this problem for full points. Here is my solution. It goes as the Aho-Corrasick algorithm. We build a trie and calculate the failure function on each node. Then for each node and for each letter on it we calculate a "reach" function. That is, where we would end up if we are in this node and this letter is added. Then I mark all nodes that lead to a successful word, that is those nodes in which if we end up — then we had some word as a substring. Finally I do DP-like calculations on K iterations. On each iteration each node that isn't marked for each letter adds its value to the node it reaches according to the "reach" function. In the beginning the root is 1 and all others are 0. Finally I sum the values of all nodes that aren't marked after the k-th iteration and this is the amount of words that don't have any of the listed words as their substring. The answer is then 26^k — (number of words that don't have listed words as their substring).

Solution complexity is : O(26*L*K), where L is the total length of all strings. This manages to pass under 3 seconds.

Problem 3 — Princes

There are three princes A,B and C. The king has N diamonds and wants to distribute them among the princes. The i-th diamond has value of 2^(i-1), so the values of the diamonds are 2^0, 2^1, 2^2...2^(N-1).

In the beginning princes don't have any diamonds and in N steps the king chooses a diamond and a prince and gives the diamond to the prince. Let Aj,Bj and Cj be the corresponding values to the total value of the diamonds the princes have after the j-th iteration. Since A is the eldest and C is the youngest, the inequality Aj>=Bj>=Cj for all 1<=j<=N must hold.

Each process of distributing in which the equality holds for all j is called "fair". Denote number of a diamond by dj and the prince it's given to by pj. The process of distributing is coded by the vector "_p1d1 p2d2 ... pNdN_". Find the K-th fair distribution if they are sorted lexicographically.

When comparing two distributions lexicographically their elements are compared from left to right. An element is a pair of a prince and a diamon. For each element first the princes are compared (A<B<C) and then the numbers (1<2<3..<N).

For example the process "Give diamond 3 to A, give diamond 2 to B, give diamond 4 to A, give diamond 1 to C" is coded by "A3 B2 A4 C1".

Example of comparing is that the vector "A3 A4 A1 B2" is smaller than "A3 B2 A4 C1".

The first vector of length 4 is "A1 A2 A3 A4", the second is "A1 A2 A4 A3" and so on.

Constraints:

Subtask 1 (11 points)

1<=N<=20

1<=K<=10^18

Subtask 2 (17 points)

1<=N<=50

1<=K<=10^200

Subtask 3 (31 points)

1<=N<=100

1<=K<=10^19

Subtask 4 (41 points)

1<=N<=100

1<=K<=10^300

Time Limit = 3s

Memory Limit = 256MB

Example

Input : 3 1

Output : A1 A2 A3

Input : 3 3

Output : A1 A3 B2

Input : 4 9 Output : A1 A4 A2 B3

Input format : n,k

Note: During the competition it turned out the tests were wrong. They were fixed and the competition was extended by 45 minutes. However I have reasons to believe the new tests may not be correct either.

My solution

I implemented a DP and a simple approach I won't explain now due to lack of time, however I managed to get it to pass only for cases in which I could use unsigned long long, that is subtasks 1 and 3, therefore i got 42 points.

So in total I got 152 points which is 6th place. I'd love to hear some solutions about diameter as it is the only task whose solution I have no clue of.

Hello everybody,

I am going to participate in this year's IOI in Taiwan. During the competition we will be provided a laptop with a few editors and compilers, and Ubuntu. Here are some more details.

At home I use the latest version of CodeBlocks editor under Windows and I'm really used to it. A lovely feature it has is that when I simply type :

{

the editor automaticly types :

{
    //blank shifted line (comment for vizualization only)
}

However, when I tested the IOI environment in VirtualBox, I couldn't find the option to make CodeBlocks do that. When I typed "{" it simply turned it in "{}". The weird thing is that when I installed CodeBlocks on my laptop (Windows again), it automatically started doing the shifting, without any settings.

It may sound like I'm being very pretentious here, but it simply will improve my coding speed and comfort when coding, so I'd be very grateful if someone can tell me how exactly can I change the CodeBlocks' settings so it can do the auto-shifting and completion as described above.

Thank you in advance! :)

Hello everybody,

For a while now I've been using the wonderful opportunity Codeforces provides — making contests in Gym. My contests are private and I use them mostly to test problems I solve, since locally testing (especially on Windows) is very inaccurate.

The wizard that helps you upload everything is very comfortable, however I couldn't find a way to upload my checker on some problems that may require one. By default, a checker that ignores whitespaces and expects solution and output file to be identical is created, however that is not always the checker I want to use. There is an option to add a checker, but I couldn't find anywhere an explanation of what should be the syntax of the checker. I tried writing a few checkers, looking at the default one's code, but all I got were errors.

I was wondering if someone can point me to a link I've missed, or maybe explain what should be the syntax of checkers for problems in Codeforces.

Thank you in advance!

Hello everybody,

Recently I participated in day 1 of CEOI unofficially online (invitation-only) and even though I performed poorly, after the competition we discussed the solutions of all problems. Except one. Here is the problem, any ideas would be very helpful! I will also include the results we found while trying to solve it below. Here is the problem, shortened because the real statement was quite long. I also changed a little bit the idea of the way of the testing to make it more clear, since what matters is the idea.

A and B want to break into a top-secret laboratory. The security system asks a question. The question 1<=q<=N is represented by a number. They are sure that the question the system will ask will be x or y. The answer to question x is "yes" and the answer to question y is "no". When the question was asked, A and B were separated, and unfortunately only A remembered the questions x and y, while B was the one next to the door ready to answer. Now A must shout exactly one number h (1<=h) and encode in it all the information B needs to answer the question. Help them by writing the following two programs :

1) for given values N,x,y return a number h that is the number A shouted.

2) for given values N,q,h return true for "yes" or false for "no", if q is the question and h is the number A shouted to B.

The second program will always receive an h that was produced by your first program.

Score is as follows : for h>=21 — 0 points

for h=20 — 27 points

for h=19 — 30 points

for h=18 — 33 points

for h=17 — 37 points

for h=16 — 42 points

for h=15 — 50 points

for h=14 — 60 points

for h=13 — 75 points

for h<=12 — 100 points

where h is the largest value your first program produced in any of the tests.

Constraints : 1<=N<=920 and your program can be run on 2,000,000 tests (all possible inputs, obviously).

Time Limit : 7s Memory Limit : 256MB

Example

The first program encode(N,x,y) was called a few times, and returns the following values:

encode(5,1,2) = 12

encode(5,4,5) = 2

encode(5,1,2) = 12

encode(5,3,5) = 4

encode(5,4,5) = 2

encode(5,5,2) = 1

Then the second function decode(N,q,h) should return :

decode(5,1,12) = true

decode(5,4,2) = true

decode(5,2,12) = false

decode(5,3,4) = true

decode(5,5,2) = false

decode(5,2,1) = false

During the compeition almost all of us found a solution for h=20, I managed to solve it for h=16 and Hristo Venev managed to get h=14. However none of us managed to get any idea for h=13 or full score. Any ideas will be appreciated!

Thanks in advance !

Hello everybody,

Recently I was solving a problem with queries on a tree and I stumbled upon Heavy-Light Decomposition. I read this article and understood the concept, then coded the solution itself. However, I noticed that for the proposed problem in the article — Dynamic distance query, they say it could be solved in O(logn) per query, while I can't see how to improve the O(log^2) bound. The article says

"It might seem that we have to ascend logarithmically many heavy paths each of which takes logarithmic time, but this is not the case; only the first one, if we start out on it, has to take logarithmic time to query; for the others, which we skip over in their entirety, we can just look up a variable indicating the sum of all weights on that path"

However I don't think this is true. When going up the tree you don't have to necesserily skip entire paths, it might turn out that each heavy path you stumble upon, you start from somewhere in the middle of it, and therefore have to perform a query in the corresponding segment tree. I was wondering if I am missing something or the article isn't entirely correct?

Thanks in advance!

Hello everybody,

I was solving last year's IOI problem Game. In short, you are given an initially empty grid and the problem consists of answering queries "Update element in cell x,y" and "Get GCD of all elements in rectangle x1,y1~x2,y2". Note that the grid is huge (10^9 x 10^9)

If it is solved using 2D segment tree it is pretty straightforward, however reading Bruce Merry's post about it, he suggest that there is more efficient (though harder to code) implementation using balanced binary trees. Obviously 2D segment tree would take O(logR*logC) time and memory per query (R,C are the sizes of the grid), however according to his post you can do it in O(logNu*logNu) time per query (Nu is the number of update operations) and significantly less memory.

I can code and understand how to do it in 1D using balanced binary tree, but I can't seem to find a correct way to extend it into higher dimensions. Can anyone explain how would the given problem be solved using balanced binary trees (not segment trees) ?

Thank you in advance,

Enchom

Hello! As the tasks are not uploaded on the official website of BOI2013 and I couldn't find them around the web (sorry if they are already posted), i decided to post them myself, as i was a participant in the competition itself. Unfortunately I lost the English papers for day 1 and had to translate the Bulgarian versions, please excuse my English in the day 1 statements. Also I have no scanner so i had to type myself the whole tasks in word, so I hope there aren't any mistakes :).

Day 1 tasks:

Mastermind

Old computer

Resting residence

Day 2 tasks:

Ancient cryptography [10s time limit, around 2GB memory limit]

The codebook [around 1.5s-2s time limit]

The Kebab eating contest [around 0.5~1s time limit]

Here are my solutions/ideas to the problems, do not read if you plan to solve them yourself.

Mastermind

To anyone who has played Bulls and Cows as a kid that shouldn't be a very difficult task. It is with relative scoring so you can pretty much play greedily. The solution is to keep all currently possible codes. Once you get a question, you iterate over all possible answers you can give, and check what codes actually correspond to those answers, then you give the answer that will result in the most codes remaining. The algorithm is good enough to get full score.

Old computer

The idea is simple, we want to choose a maximum set P of those pairs a[i],b[i], in some order such that a[p1]<a[p2]<a[p3]... and b[p1]<b[p2]<b[p3]. Well the simplest way to do that would be to sort the pairs in increasing order of a, and then get the Longest Increasing Subsequence in b. However we must sort them in increasing order of a AND decreasing order of b secondary, to avoid taking a few pairs with the same a.

Complexity of the algorithm is O(m*LOGm). If (as it happened for some people), this time limits in subtask 3, where m<=4,000,000 , then you can write a separate O(n^2) solution for it.

Resting residence

Biggest problem in this task is understanding the statement perfectly. So well, we can assume that every time you move through an edge, you receive "one magic point", that you can later use to rotate a pentagon without using energy (because it will be equivalent to rotating it while you were taking those "magic points"). Also you are able to do a "combo move" by rotating a neighbour and immediately moving to it. Such moves take only 1 energy and don't give you a magic point. Now how to solve the problem? Well we can "expand" our graph, creating a state [current vertex][rotation of current vertex][magic points left]. With some thinking we can realize what edges would come out of each vertex and actually construct such graph of size around N*5*N. After that we can simply use Djikstra to compute the path to N, note that it will be a good optimization to break as soon as we find the best path to N and not wait until Djikstra finishes, since the optimal path will hardly ever be too long.

Ancient cryptography

Now if you have heard of Aho–Corasick, then probably that was the first thing in your head. I had only heard the algorithm at the time of the competition and didn't know how to implement it, so I panicked a little bit thinking it might be the only solution, however fast enough I came up with a good idea that the constraints allowed.

We can observe, that in the largest subtask 5, w<=15 and in the others w is usually a relatively small number too. So we don't have many different lengths. So how to use that? Well what we can do is actually use a hash on all words in the dictionary, and put them in sets separated by their length. Then what we can do is we can iterate from w to 1 and check for every possible length if there is word with that length. We can do that by simply doing a "rolling hash" over our large string and checking if the current hash is the same as some word from the dictionary with the corresponding length after every roll.

The total complexity is O(w*x*logm). 10s should be enough.

Note: Of course, if you can implement Aho-Corasick, that would be a way better solution :)

The codebook

Now obvious solution is O(N!), however that would work only on the first two subtasks. First, note that basically what you have to find is (P-1)*B+Q-th lexicographical correct(according to their rules) permutation. Let's create a graph. The nodes will be the values of A and there will be an edge between vertices i and j, if and only if GCD(A[i],A[j])>=K. So, one can easily notice that every correct permutation corresponds to a Hamiltonian Path in our graph. Well, finding such a path is NP-complete problem which can be solved in O(2^N*N). We can do exactly that here, we will use DP with state [bitmask of used vertices][current vertex] that will give us the amount of Hamiltonian Paths that can be created from that state. It is now not that difficult to get the (P-1)*B+Q-th lexicographical path, which would be the answer to the problem.

The total complexity is O(2^N*N). Surprisingly there is a chance that recursive implementation is too slow, so iterative would be the safest way.

The Kebab eating competition

Well, as every experienced contestant would guess, we will process everything chronologically. So what we need is a structure that supports the following 2 queries :

1. Add a restaurant that serves sandwiches with A kebabs (called when restaurant is opened)
2. Return the sum of the B largest numbers (obviously optimal buying, called when a competitor can buy)

Well, it turns out that those queries aren't difficult at all. One competitor from my team solved it using AVL trees, another solved it using Treap, and i solved it using Segment Tree (simplest in my opinion). My idea was that simply a node in my Segment Tree would hold the amount of restaurants in its segment, and their sum. I process the queries the following way:

1. I increase the A-th leaf's restaurants with 1, and its sum with A, and update the path to the root.
2. I start from the root, if the right child has more restaurants than money i have, i go there recursively. Else i get the sum of the right child's tree (i buy all the sandwiches there), remove the money i had to pay (the amount of restaurants) and go recursively to the left child.

The total complexity of the algorithm is O( (n+m)*LOGmax_size ), and since size[i]<=20,000, then max_size=20,000 and the algorithm is obviously fast enough to solve the problem :)

Sorry if my solutions are unclear or there is a mistake in some of the statements, i tried my best :)