### kingofnumbers's blog

By kingofnumbers, 6 years ago, ,

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.

• +56

 » 6 years ago, # |   +14 Russia joined APIO? -4 gold medals :(
•  » » 6 years ago, # ^ |   0 Actually, I'd say +1 or +2 gold medals, in total :DBut yeah, that (and probably more) would get taken by Russia.
•  » » 6 years ago, # ^ |   +8 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.
•  » » » 6 years ago, # ^ |   -47 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
•  » » » » 6 years ago, # ^ |   +12 Haters gonna hate...
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   +6 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.
•  » » » » » 6 years ago, # ^ |   +3 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 ?!
•  » » » » » » 6 years ago, # ^ |   +3 Ok then, where's the fun if you compete only to get a medal?
•  » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   +3 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)
•  » » » » » » » » 6 years ago, # ^ |   +11 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.
•  » » » » » » » » » 6 years ago, # ^ |   0 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
•  » » » » » » » » » 6 years ago, # ^ |   +3 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.
 » 6 years ago, # |   -8 I live in Asia, can I participate??
•  » » 6 years ago, # ^ |   0 if your country is registered at APIO then ask your delegation to participate in APIO.
•  » » » 6 years ago, # ^ |   -8 I live in east part of Russia, so include me into the team, I promise that I'll take first place!
•  » » » » 6 years ago, # ^ |   0 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.
•  » » » » 6 years ago, # ^ |   +17 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.
•  » » » » 6 years ago, # ^ |   +6 I promise that I'll take first place!
 » 6 years ago, # | ← Rev. 2 →   +8 There will be 2 competition days(6 tasks) this year???Past APIOs only have one day and 3 tasks.
•  » » 6 years ago, # ^ |   +8 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.
•  » » 6 years ago, # ^ |   +8 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.
•  » » » 6 years ago, # ^ |   0 Maximum number of submissions per task: 40. Are "Compilation error"s and "Didn't produce output to task.out"s are included?
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +8 Yes. All submissions included.
•  » » » » » 6 years ago, # ^ |   0 Where can I see how many submissions I have left?
•  » » » » » » 6 years ago, # ^ |   +8 Good question. Right now you cannot see. We will fix this today or tomorrow.
•  » » » » » » 6 years ago, # ^ |   0 Now you can see it on submission page.
•  » » » 6 years ago, # ^ |   +5 Appeal session is over. Would you mind publishing final results?
 » 6 years ago, # |   +11 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?
•  » » 6 years ago, # ^ |   +11 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.
•  » » » 6 years ago, # ^ |   +4 Thank you for replying.And would you tell me an outline of the model algorithm?
•  » » » » 6 years ago, # ^ |   +10 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))
•  » » 6 years ago, # ^ |   +3 read this.The idea is to binary search the answer such that the maximal possible is greater than or equal to K.
 » 6 years ago, # |   +3 I think that the practice session could use more problems
 » 6 years ago, # | ← Rev. 2 →   +8 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)
•  » » 6 years ago, # ^ | ← Rev. 4 →   +5 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 :POverall 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)
•  » » » 6 years ago, # ^ |   +13 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 :-) )
•  » » » » 6 years ago, # ^ |   0 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.
•  » » » 6 years ago, # ^ |   0 What is a casebash-y tree ? Can you please explain ?abyssmallThank you
•  » » » » 6 years ago, # ^ |   0 I meant that it was a tree problem and there are a number of cases to consider ("casebash").
•  » » » » » 6 years ago, # ^ |   0 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
•  » » » » » » 6 years ago, # ^ |   0 I edited my original comment with more details for C
•  » » » 6 years ago, # ^ |   0 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 :)
•  » » » » 6 years ago, # ^ |   0 Here is my code for C: http://codepad.org/JuckHc12Its quite messy so idk how helpful it will be.As for IOI the team still hasn't been officially announced.
•  » » » 6 years ago, # ^ |   0 Hi there, abyssmallSorry 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.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Ignore. Bugs.
•  » » » » 6 years ago, # ^ | ← Rev. 4 →   0 Code for B: http://codepad.org/8gW3qli8Hopefully 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.
•  » » » » » 6 years ago, # ^ |   0 Thanks a lot ! abyssmall :)
•  » » » » » 5 years ago, # ^ |   0 Why won't integer division cause divide by zero?
•  » » » » » » 5 years ago, # ^ |   0 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.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +5 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.
•  » » » 6 years ago, # ^ |   0 Yep, your statement about the path needing a blue edge is definitely a difficult observation that I know caused problems for people.
•  » » » 6 years ago, # ^ |   0 How are you checking if the string is a Palindrome ?
•  » » » 6 years ago, # ^ |   0 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.
•  » » » 6 years ago, # ^ |   0 troybarnesWhat 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 ?
•  » » 6 years ago, # ^ |   +10 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.
•  » » » 6 years ago, # ^ |   0 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!
•  » » » 6 years ago, # ^ |   +5 Seems like Vietnam did pretty well on B :) Until now, I know at least 3 fully solved B in the contest :)
•  » » 6 years ago, # ^ |   0 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
•  » » » 6 years ago, # ^ |   +13
•  » » 6 years ago, # ^ |   0 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.
 » 6 years ago, # |   +5 When the results will be available?
 » 6 years ago, # |   +1 Does anyone know, did anyone get full score? I mean 300 points
•  » » 6 years ago, # ^ |   +6 I think someone in Russia or China got 300. In Korea, 273 is the best.
•  » » » 6 years ago, # ^ |   +22 Both KAN and zemen has full score.
 » 6 years ago, # | ← Rev. 7 →   +2 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: gabacabayou 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 programmingdp[i][j] means the best points we can get after splitting i times (getting i+1 parts) with elements from 1 to jlet A be the partial sum of the input seqcence then the dynamic function is compute like thisdp[i][j]= max for all k
•  » » 6 years ago, # ^ |   0 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.
•  » » » 6 years ago, # ^ |   0 thank you it is fixed now.
•  » » 6 years ago, # ^ |   0 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.
•  » » » 6 years ago, # ^ |   0 you are right! I'm so sorry it seems that I'm too hasty.
•  » » 6 years ago, # ^ |   0 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
•  » » » 6 years ago, # ^ |   0 Are you sure you weren't copying my codes ??? :D ?Did you try to solve Beads?
•  » » 6 years ago, # ^ |   +3 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).
 » 6 years ago, # |   +16 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).
•  » » 6 years ago, # ^ |   0 And it is my code of A Problem. http://ideone.com/WSRCV5
•  » » » 6 years ago, # ^ |   0 Could you write a short explanation of your solution? I cant seem to understand. An explanation will be very helpful. Thanks :)
•  » » » » 6 years ago, # ^ |   0 In short,I solved it with SA+LCP too.
•  » » » » 6 years ago, # ^ |   +5 I'm sorry but I'm not good at English writing. So I can't explain my solution more.
•  » » » » » 6 years ago, # ^ |   +8 Its alright. Not a problem :)
 » 6 years ago, # |   +16 Does anyone know when the results will be available?
 » 6 years ago, # |   0 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 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...
•  » » 6 years ago, # ^ |   0 I did exactly the same, 73 points
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 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.
 » 6 years ago, # |   0 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!!!
•  » » 6 years ago, # ^ |   +12 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]
 » 6 years ago, # | ← Rev. 2 →   +3 //82.200.146.22 i can still entire this site and still send a submission , why ?
•  » » 6 years ago, # ^ |   +3 Because it is upsolving.
 » 6 years ago, # |   +5 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?
•  » » 6 years ago, # ^ |   0 How did you got 28 points in C? Can you explain your idea?
•  » » » 6 years ago, # ^ |   +5 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.
•  » » » » 6 years ago, # ^ |   +3 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 :)
•  » » » » » 6 years ago, # ^ |   +13 Yes, I got to this idea but I couldn't code it...
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Maybe because of constant factors ?! Try this test: 10000 1 2 100 2 3 100 ... 9998 9999 100 9999 10000 100 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).
 » 6 years ago, # |   +3 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)
•  » » 6 years ago, # ^ |   0 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.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 in APIO it is not ... see 2012 40 is a bronze :D
•  » » » 6 years ago, # ^ |   +3 we got medals congratz
•  » » » » 6 years ago, # ^ |   +3 Where can I find the results?
•  » » » » 6 years ago, # ^ |   0 How do you know?
•  » » » » 6 years ago, # ^ |   +6 Your supervisor has the resultsI only know that 73+ is a medaland gold is 200+also there are a couple of perfect scores (also don't how many exactly)
•  » » » » » 6 years ago, # ^ |   +3 Thanks.
•  » » » » » 6 years ago, # ^ |   0 Are you sure 73+ is a medal ? Can you tell me the cut off ?
 » 6 years ago, # |   +11 Sorry, where we can find results?
•  » » 6 years ago, # ^ |   +22 Appeal session is still running, so results can't be ready. But I think it'll be open to everybody soon :-)
 » 6 years ago, # |   +27 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)
•  » » 6 years ago, # ^ |   +3 Actually «Contestants with 123 points and more but less than 200 points — silver medals»
 » 6 years ago, # |   +34
•  » » 6 years ago, # ^ |   0 Are you sure that these are the final results ? Because my supervisor is telling that it is not kingofnumbers, Blackjaguar97
•  » » » 6 years ago, # ^ |   0 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)
 » 6 years ago, # |   0 where can i find the statements ?
 » 6 years ago, # |   +5 When will test data come?
•  » » 6 years ago, # ^ |   +3 Here are the test data for A:palindrome and B:sequenceI didnt find the test data for the third problem.Note: the links will download automatically
 » 5 years ago, # |   +10 When will the tasks and the test datas be available?
•  » » 5 years ago, # ^ |   +3 It's now available.