kingofnumbers's blog

By kingofnumbers, 6 years ago, In English,

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.

 
 
 
 
  • Vote: I like it
  • +56
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Russia joined APIO? -4 gold medals :(

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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, # ^ |
        Vote: I like it -47 Vote: I do not like it

      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, # ^ |
          Vote: I like it +12 Vote: I do not like it

        Haters gonna hate...

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          Rev. 2   Vote: I like it +6 Vote: I do not like it

          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, # ^ |
            Vote: I like it +3 Vote: I do not like it

          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, # ^ |
              Vote: I like it +3 Vote: I do not like it

            Ok then, where's the fun if you compete only to get a medal?

            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
              Rev. 2   Vote: I like it +3 Vote: I do not like it

              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, # ^ |
                  Vote: I like it +11 Vote: I do not like it

                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, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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, # ^ |
                    Vote: I like it +3 Vote: I do not like it

                  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, # |
  Vote: I like it -8 Vote: I do not like it

I live in Asia, can I participate??

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

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

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # ^ |
          Vote: I like it +17 Vote: I do not like it

        No problem, you just need to complete several simple steps.

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

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

        3. .......

        4. Profit! You are able to participate in APIO.

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it
        I promise that I'll take first place!

        Believe him :D

»
6 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

message from APIO 2014 host committee:

The practice session is online. Contest system address is https://82.200.146.22.

Your browser may complain about untrusted connection — this is ok.

Task statements for the practice session are provided via web interface. Tasks were taken from IZhO 2014 — the international contest that took place in Almaty, in January 2014 (http://izho.kz)

Practice session will be online until May 1. It's possible that we will have short downtimes, so don't worry if the website is not answering, just return in a few minutes.

Each contestant has limits similar to ones that will be used on the real contest:

Maximum number of submissions per task: 40.

Minimum interval between submissions for one task: 60 seconds.

Maximum number of user tests per task: 10.

Minimum interval between user tests for one task: 60 seconds.

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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   Vote: I like it +8 Vote: I do not like it

        Yes. All submissions included.

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Where can I see how many submissions I have left?

          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Now you can see it on submission page.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Thank you for replying.

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

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        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, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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, # |
  Vote: I like it +3 Vote: I do not like it

I think that the practice session could use more problems

»
6 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

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   Vote: I like it +5 Vote: I do not like it

    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)

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      Thank you

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I edited my original comment with more details for C

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        6 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Ignore. Bugs.

      • »
        »
        »
        »
        6 years ago, # ^ |
        Rev. 4   Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks a lot ! abyssmall :)

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Why won't integer division cause divide by zero?

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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   Vote: I like it +5 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How are you checking if the string is a Palindrome ?

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 ?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like 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.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
        Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it +5 Vote: I do not like it

When the results will be available?

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Does anyone know, did anyone get full score? I mean 300 points

»
6 years ago, # |
Rev. 7   Vote: I like it +2 Vote: I do not like it

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 :(

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like 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.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      Did you try to solve Beads?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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, # |
  Vote: I like it +16 Vote: I do not like it

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, # |
  Vote: I like it +16 Vote: I do not like it

Does anyone know when the results will be available?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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...

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did exactly the same, 73 points

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it +12 Vote: I do not like it

    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   Vote: I like it +3 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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, # ^ |
            Vote: I like it +13 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it +3 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      we got medals congratz

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Where can I find the results?

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How do you know?

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        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)

»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Sorry, where we can find results?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +27 Vote: I do not like it

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, # |
  Vote: I like it +34 Vote: I do not like it
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

where can i find the statements ?

»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

When will test data come?

»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

When will the tasks and the test datas be available?