Hello.

APIO 2014 (Asia-Pacific Informatics Olympiad) will take place in 3-4 may 2014 , I wish good luck to all participants.

there is good news, Georgia, Russia, Tajikistan and Turkmenistan have joined APIO starting from this year, which makes getting a medal more challenging :)

Here is a message from APIO 2014 Host committee to our delegation:

Hello from Kazakhstan! We are proud to host APIO 2014 and already have some information for you. First of all, the olympiad will be hosted by one of the best technical universities in Kazakhstan — Kazakh-British Technical University (http://kbtu.kz). Thanks, KBTU! Secondly, here is the official website: http://olympiads.kz/apio2014 (it's still under construction, but some important information is already available). Thirdly, the competition date is fixed at May 3-4 (full schedule is available on the website). And at last, we have 4 new members in this APIO apart from those who joined at IOI 2013. These are: Georgia, Russia, Tajikistan, Turkmenistan.

Russia joined APIO? -4 gold medals :(

Actually, I'd say +1 or +2 gold medals, in total :D

But yeah, that (and probably more) would get taken by Russia.

Why are you so sad? more challenging more fun.

BTW, if you meant by '4' to say all russian particiants, I'm afraid to tell you that you are confused with IOI because last year each country was allowed to participate with 6 participiants in APIO.

however, I think this year the number of medals awarded will be increased.

yeah ... more fun you are just a cocky .... for someone who say that "more challenging more fun" i guess he can win a gold medal at least so he can challenge the Russians ... just pray to get a bronze medal Mr.kingofnumbers the last year you didn't get anything ... so you aren't in a position to say your words

Haters gonna hate...

I don't know why he hates me when I say optimistic words(this is not the first time) , although he is my teammate in IOI this year.

what i was trying to say ... no one can be happy for competing against Russians except Chinese :P i mean where is the "fun" if your chance to get a medal is decreased ?!

Ok then, where's the fun if you compete

onlyto get a medal?Actually our state is different than yours ... we didn't participate in IOI since 2011 "NO VISA" and that guy "king" stayed in the high school for on more year just to try to catch a medal in IOI or APIO (so we can get scholarships) and get out of Syria .... education here is so bad and this is our last year in school so we must get medals (this is our story)

No, I wasn't asking "do you need to get a medal?" or "why do you need to get a medal?".

I asked where the fun is in only competing to get a medal, since you're getting angry at people because they enjoy competitive programming.

NO FUN without competition against others ... competitive programming is the best thing in my life ... "BUT" I think everyone should compete (have fun) against programmers ( programmers that he has a chance to beat them i mean both have kind of close abilities) So then the contest will be great But that kingofnumbers is having fun in competing against Russians ( he said that ) believe me these are just words .....he always says words bigger than him

It's not like if someone's usually better than you, then that person's absolutely always better. Also, people can improve, but hardly without actually believing so. It's important to try, to challenge yourself, to imagine you can reach that level.

I live in Asia, can I participate??

if your country is registered at APIO then ask your delegation to participate in APIO.

I live in east part of Russia, so include me into the team, I promise that I'll take first place!

I don't have permission to include you.

qoute from official APIO website:

How to Enter:Each delegation registers its own competitors for the APIO. If you are a student wishing to compete, please contact your local informatics olympiad organisation.No problem, you just need to complete several simple steps.

Win national olympiad (by the way, its second day is tomorrow! Hope you've already scored 400 yesterday...)

Pass to the summer training camp of Russia IOI team candidates.

.......

Profit! You are able to participate in APIO.

Believe him :D

There will be 2 competition days(6 tasks) this year???Past APIOs only have one day and 3 tasks.

I think it is just one day. But each delegation must choose best time for themselves. That is why it will take place in 3-4 May.

message from APIO 2014 host committee:

however, I couldn't enter the practice session because I haven't received my username and password yet.

Hello. Each site supervisor should have received usernames and passwords for their contestant. Ask your supervisor, or write an email on apio2014@olympiads.kz, with your name and country in it, and I'll submit you contacts of your supervisor.

Are "Compilation error"s and "Didn't produce output to task.out"s are included?

Yes. All submissions included.

Where can I see how many submissions I have left?

Good question. Right now you cannot see. We will fix this today or tomorrow.

Now you can see it on submission page.

Appeal session is over. Would you mind publishing final results?

I tried to solve 2nd problem of APIO practice. (luxury-burrow)

I managed to get 56 points with O(N^2*M*log N*M) algorithm, but I can't get full score.

Can I get full score if I optimize the same algorithm? Or do I have to think up another one?

Intended solution has complexity O(N*M*log(max(A[i]))), so, i don't think that optimizing your solution will do any good, try to come up with another one.

Thank you for replying.

And would you tell me an outline of the model algorithm?

O(N*M*log(N*M)) solution : let's find all distinct numbers in the matrix and put it in the array. Sort it. Binary search the answer, let's name it M, now build the matrix B, so that B[i][j] = 1, only if A[i][j] >= M, and 0 otherwise. We need now to find the rectangle with maximum possible area, filled only with 1's, and check that it's area >= K. It's a standard problem which we can solve in O(N*M) time, which give us total runtime O(N*M*log(N*M))

read this.

The idea is to binary search the answer such that the maximal possible is greater than or equal to K.

I think that the practice session could use more problems

The contest has finished in all the countries. Let's discuss the problems :-)

My solution:

A: Check whether all the substrings is palindrome. And calculate the rolling hash for substring [1,i].

With these datas, we can solve this problem with O(N^2 log N).(47 points)

And I heard that it's possible to get 100 points with SA+LCP, but I don't know details :-(

B: This problem is similar to 321E - Ciel and Gondolas.

So we can solve this problem with the same algorithm, but it's very difficult to avoid TLE and MLE.

I think getting 100 points is impossible...

C: This problem needs the correct observation. And with it, we have only to solve typical DP on tree.

I started imprementation with the wrong observation, so can't get any points :-(

(My score was 47-71-0)

Yeah my friend had an 100% idea for A after the contest involving SA and LCP, as well as a segment tree. I don't know the details. No-one i was with had much idea for A 100% during contest.

For B you can use divide and conquer as you said, but due to the logN factor i don't think this can get 100%. However you can instead use convex hull optimisation, which does get 100.

C was pretty casebash-y due to having to maintain 2 restrictions during a DP on the tree. The 2nd restriction was quite difficult to realise; I and a few friends all coded a solution at the start only using the 1st restriction (each node is a midpoint of at most 1 pair of blue edges), and of course this solution got 0 :P

Overall I thought contest was curiously similar to APIO 2010, with B using convex hull optimisation like Commando, and C being a casebash-y tree problem like Patrol.

EDIT: To expand on problem C, there were 2 restrictions on the edges that you needed to realise. The first one was fairly clear. Blue edges are naturally in pairs due to the way they are constructed. Any node can only be in the middle of at most one pair of edges. The 2nd restriction is much less obvious. The path between any two "middle nodes", that is, nodes which are the middle of a blue edge pair, must go through at least one of the blue edges in the pairs that the nodes are middles of. If the path does not include any of these 4 edges it can be seen that there is no way this tree could have been constructed.

My solution was a recursive DP with 4 possibilities for each node: whether or not the edge to the parent has been used in a pair, along with whether there is a middle node in the subtree with both its blue edges going towards children.

According to troybarnes who posted below, there is a "simple constructive algorithm". I am interested to see it.

My score was (23-100-100)

I think APIO 2010 is similar to APIO 2013, too.

It is quite hard to get 100 points in C, so whoever solved C are likely to get Gold Medal.

(In japan, I've found only one person solved C (yokozuna57). He must be genius :-) )

I did manage to solve C in the end, after more than an hour of pondering I realised the 2nd restriction. I think i was a bit lucky to make no mistakes in working out cases or implementing as I was a bit short on time at that point.

What is a casebash-y tree ? Can you please explain ?abyssmall

Thank you

I meant that it was a tree problem and there are a number of cases to consider ("casebash").

Silly me :P Anyways, so do you know if the full solution of this problem ? If yes, could you post it ?

Or could you explain to me the solution of the problem? Thank you abyssmall

I edited my original comment with more details for C

Nice, Can I get your code ? I have problems with implementations of such tree-Dp abyssmall BTW, are you going to IOI this year ?

Thank you so much for your help. And please give me your code if you can :)

Here is my code for C: http://codepad.org/JuckHc12

Its quite messy so idk how helpful it will be.

As for IOI the team still hasn't been officially announced.

Hi there, abyssmall

Sorry again, Can I see your code of problem B ? I am coding convex hull DP for the first time and I am having a lot of difficulty.

Thank you. It would be a lot of help. Your code for the last problem : Problem A was pretty helpful.

Ignore. Bugs.

Code for B: http://codepad.org/8gW3qli8

Hopefully this helps.

The hull is treated as a stack while being built. The function ins inserts a new line. Lines that are no longer on the hull should be popped. To check whether a line is no longer on the hull x-intercepts are compared. Integer division is used because if the fractions were multiplied out it could overflow. Using integer division seems dodgy but I think it works because all queries of the hull are integers so being off by a fractional amount doesn't matter.

Thanks a lot ! abyssmall :)

Why won't integer division cause divide by zero?

It appears that there will be division by 0 if we find a line in the existing convex hull with equal gradient to the line being inserted. However this will never happen.

Lines are inserted in order of increasing gradient. The first IF in ins() checks if the last line in convex hull has equal gradient to inserted line, and special cases this. If this is not the case all existing lines have lower gradient so division by 0 does not occur.

A: This can be solved in O(n log n + SA(n)) where SA(n) is the time needed to construct the suffix array, by preprocessing to get constant time range LCP queries and then binary searching from all LCP positions. (This becomes equivalent to solving the largest area rectangle in histogram problem, which can be done in O(n) time using a stack, which means this can be solved in O(n) time total)

B: This can be solved in O(nk) with the "standard" convex hull DP trick using a monotone queue. It seems like a lot of standard DP optimisations work, to varying degrees.

C: There is a simple constructive algorithm for this, after finding the right observations. Crucially, the path between any two vertices that have been created using a split operation must have a blue edge on one of its ends. I imagine this tripped up a lot of people.

Yep, your statement about the path needing a blue edge is definitely a difficult observation that I know caused problems for people.

How are you checking if the string is a Palindrome ?

Hi, Could you tell me how you figure out the max length of a palindrome in less than O(n^2) time complexity. Thanks in advance.

troybarnes

What will you binary search from all the LCP positions ? I mean, do you want to find the length of the largest palindrome that starts from i ? In that case, ho to do it ?

I solved B in less than 1 hour. But within last 4 hours, i couldn't solve much. So i have (23.100.0) score.

How did you solve it? can you give explanation of your solution, and if you don't mind can you post your code anywhere. Thanks!

Seems like Vietnam did pretty well on B :) Until now, I know at least 3 fully solved B in the contest :)

Hi HIR180, Can you provide me with your code of A ? I am pretty bad at using hashing, so some help would be really great :)

Thanks

https://ideone.com/vBb2Jy

It is about dp optimization (though I didn't get it) To avoid MLE, notice that 20M long long ints not enough, but we can use only O(n) because only last number of K is counted in dp process. And to print the solution just use int, and 20M ints fits ML.

When the results will be available?

Does anyone know, did anyone get

full score? I mean300 pointsI think someone in Russia or China got 300. In Korea, 273 is the best.

Both KAN and zemen has full score.

The contest has been finished.

let me discuss the solution of problems briefly:

palindrome:first thing we need to support fast answering for this kind of queries:

given two numbers L and R you should tell how many times the substring str[L..R] occure is string str ( str is the input string)

this can be done in O(log n) per query using suffix tree or maybe something else.

second step is to search for palindromes in the string, we can do this by fixing the middle points then continue extending from left and right until the string is not palindrome anymore (note that the middle point of odd-length palindromes is a letter and for even length is between two letters) for example:

string: gabacaba

you want to search for palindromes that have the letter 'b' in index 2 to be the middle we start by 'b' obovouisly it's palindrome then 'aba' it is, then 'gabac' it isn't so we stop and continue the same thing with other middle points.

this is O(N^2) how can we do better?

~~instead of extending letter by letter we can use binary search and hashes to find the palindrome with maximal length in each middle point, but we have a problem , what if the optimial answer is a palindrome which isn't maximal length among palindromes with the same middle point?~~~~actually , it's enough to check the maximal length palindrome for each middle point because the optimial choice is always a palindrome that is maximal length for some middle point because otherwise we can get a longer palindrome with the same number of occurrences.~~~~time complexity O(N log N) which I think will get 100 points~~sequence:first observation that after we choose the K+1 parts it doesn't mattar the order of splitting it will give he same number of points , it's only mattar of choosing best K postion of splitting

I've noticed this during the contest but I had no idea about the proof.

this observation will lead immediately to very standard O(N^2 K) dynamic programming

dp[i][j] means the best points we can get after splitting i times (getting i+1 parts) with elements from 1 to j

let A be the partial sum of the input seqcence then the dynamic function is compute like this

dp[i][j]= max for all k<j (dp[i-1][k] + (A[j]-A[k])*A[k])

we can imporve the time complexity by using convex hull trick , this will make complexity O(NK) which is enough to get 100 points

if are familiar with convex hull trick you will find it easy how to apply it with this problem if you not you can read about it here

beads:we can imagine the problem like that we have a tree each edge is red initially and we aslo have two types of nodes the first is red which is created by Append operation the second is blue which is created by Insert operation , blue nodes can change exactly two of adjencent edge to blue if this node is connected by at least one red node using those two blue edges.

this is solved by dynamic programming , first root the tree at some node then

dp[i][0] best solution for i'th node subtree and node i is red

dp[i][1] best solution for i'th node subtree and node i is blue and it changed two red child edges to blue (child edge is an edge leading to one of node i children)

dp[i][2] best solution for i'th node subtree and node i is blue and it changed the parent edge and one of red child edges (leading to a red child node) to blue

dp[i][3] best solution for i'th node subtree and node i is blue and it changed the parent edge and one of red child edges (leading to a blue child node) to blue (in this case the parent of node i must be red)

time complexity O(n)

those are my ideas I couldn't get 100 points for the first problem because I don't know how to build suffix tree in O(n)

and for second problem it seems my codes have bugs so I got 0 points for it :(

Your reduction of beads to changing edges from red or blue is incorrect. The method by which the tree is constructed places another restriction on how the pairs of blue edges may be placed. See my bigger comment above for details on the other restriction.

thank you it is fixed now.

in problem palindrome in this test "abcbadbcbd", if you only check maximal palindrome with each middle then the answer is 5: abcba or dbcbd, but a better answer is 6: "bcb" with 2 occurences.

you are right! I'm so sorry it seems that I'm too hasty.

I got wrong answer on test 3 for many times and at last I found out that if answer is 0, my program fails to print a solution because I set initial value for best answer as 0. When I changed it to -1 it accepted. Maybe is that problem

Are you sure you weren't copying my codes ??? :D ?

Did you try to solve Beads?

Here is the proof of second problem's assume that order of merging subsets doesnt change anything :

Let set A = {a,b} and B = {d,e}

Then merge(A,B) = (a + b) * (d + e) which means a * d + a * e + b * d + b * e.

It is obvious that when every merge operation happened, We will have products of each pair whose the elements of pair is not belong to same set.

So if we choose sets Ai.

Let their sum Si.

Answer is (square(sum of all elements) — sum of each square(Si)) / 2

So we have to minimize sum of each square(Si).

I got 100 point in A problem in 70 minutes after starting the competition.(SA+LCP+UnionFind) But I spend a lot of time at C problem ,and I couldn't get any point in C problem. My Score is 111 point(100+11+0).

And it is my code of A Problem. http://ideone.com/WSRCV5

Could you write a short explanation of your solution? I cant seem to understand. An explanation will be very helpful. Thanks :)

In short,I solved it with SA+LCP too.

I'm sorry but I'm not good at English writing. So I can't explain my solution more.

Its alright. Not a problem :)

Does anyone know when the results will be available?

I only got 73 points (23+50+0) I either don't know Manacher algo or how to build suffix tree (I couldn't get a solution just with SA) then I used

`map<string,int>`

and got 23pts! One participant near me used pascal and I watched him submitting again and again but always tle on subtask 2 , and only 8 pts...I did exactly the same, 73 points

I originally got only 8 points in A, as I got MLE. Luckily remembered to use map, which gave me an extra 15 points. I say 23 + 50 + 0 is not bad for my first APIO. In Malaysia a lot of people got either 23 or 8 because forgot to use long long to store the solution for B.

I didn't know about convex hull trick before. After contest I read it but still can't find that equation of convex hull trick for problem B(( can anyone explain it or just give the equation. Thanks!!!

`dp[i][j] = {k : max(dp[i - 1][k] + sum[k] * (sum[j] - sum[k]))}`

`dp[i][j] = {k : max(dp[i - 1][k] - sum[k] * sum[k] + sum[k] * sum[j])}`

`y = a * x + b`

, where`a = sum[k]`

,`b = dp[i - 1][k] - sum[k] * sum[k]`

,`x = sum[j]`

,`y = dp[i][j]`

//82.200.146.22 i can still entire this site and still send a submission , why ?

Because it is upsolving.

I got 125 points(47+50+28).

O(N^2)(about 10^8) passed in A, O(KN^2)(about 2*10^8) passed in B, but O(N^2)(about 10^8) didn't pass.

What time complexity is expected in getting 57 points in C?

How did you got 28 points in C? Can you explain your idea?

Just doing O(N) DP on tree N times(with changing root).

Root is the first node we have, and add chains of length two.

When your dp already calculated for one root you can simply change root for its neighbour in the tree in O(1). That's my O(N) solution :)

Yes, I got to this idea but I couldn't code it...

Maybe because of constant factors ?! Try this test:

My solution got 28 too. I was expecting 57 points but my solution ran in ~10sec in the above test. And I think it is because of constant factors :|

BTW My score is 125 too (47+50+28).

The APIO committee has a tough decision to make, should they give medals to the ones who scored 73 or not... I'm guessing that's why the results aren't ready yet (I say they should :D :D :D)

I got 73 too :D based on previous years they should give a bronze medal to us, but also I think 73 is too low for a medal.

in APIO it is not ... see 2012 40 is a bronze :D

we got medals congratz

Where can I find the results?

How do you know?

Your supervisor has the results

I only know that 73+ is a medal

and gold is 200+

also there are a couple of perfect scores (also don't how many exactly)

Thanks.

Are you sure 73+ is a medal ? Can you tell me the cut off ?

Sorry, where we can find results?

Appeal session is still running, so results can't be ready. But I think it'll be open to everybody soon :-)

Contestants with 200 points and more — gold medals (15 contestants) Contestants with 122 points and more but less than 200 points — silver medals (33 contestants) Contestants with 73 points and more but less than 122 points — bronze medals (53 contestants)

Actually «Contestants with

123points and more but less than 200 points — silver medals»results

Are you sure that these are the final results ? Because my supervisor is telling that it is not kingofnumbers, Blackjaguar97

Yes sure .... if you see my comment our supervisor told us that he was mailed the same speech in email (then i copied it here)

where can i find the statements ?

When will test data come?

Here are the test data for A:palindrome and B:sequence

I didnt find the test data for the third problem.

Note:

the links will download automaticallyWhen will the tasks and the test datas be available?

It's now available.