Блог пользователя kingofnumbers

Автор kingofnumbers, 10 лет назад, По-английски

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
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Russia joined APIO? -4 gold medals :(

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится -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

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +12 Проголосовать: не нравится

        Haters gonna hate...

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
          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.

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится +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 ?!

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

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

            • »
              »
              »
              »
              »
              »
              »
              10 лет назад, # ^ |
              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)

              • »
                »
                »
                »
                »
                »
                »
                »
                10 лет назад, # ^ |
                  Проголосовать: нравится +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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  10 лет назад, # ^ |
                    Проголосовать: нравится 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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  10 лет назад, # ^ |
                    Проголосовать: нравится +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.

»
10 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

I live in Asia, can I participate??

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится

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

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 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.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +17 Проголосовать: не нравится

        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.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится
        I promise that I'll take first place!

        Believe him :D

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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

»
10 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
10 лет назад, # |
  Проголосовать: нравится +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?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      Thank you for replying.

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

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +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))

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    read this.

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

»
10 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I think that the practice session could use more problems

»
10 лет назад, # |
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)

  • »
    »
    10 лет назад, # ^ |
    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 :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)

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +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 :-) )

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 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.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      Thank you

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Hi there, xxTastyHypeBeast666xx

      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.

      • »
        »
        »
        »
        10 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Ignore. Bugs.

      • »
        »
        »
        »
        10 лет назад, # ^ |
        Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Thanks a lot ! xxTastyHypeBeast666xx :)

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Why won't integer division cause divide by zero?

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится 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.

  • »
    »
    10 лет назад, # ^ |
    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.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How are you checking if the string is a Palindrome ?

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 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.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 ?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 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!

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 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.

»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

When the results will be available?

»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
10 лет назад, # |
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: 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 :(

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 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.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 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.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      Did you try to solve Beads?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +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).

»
10 лет назад, # |
  Проголосовать: нравится +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).

»
10 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Does anyone know when the results will be available?

»
10 лет назад, # |
  Проголосовать: нравится 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<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...

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I did exactly the same, 73 points

  • »
    »
    10 лет назад, # ^ |
    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.

»
10 лет назад, # |
  Проголосовать: нравится 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!!!

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +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]

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится +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?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +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.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +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 :)

  • »
    »
    10 лет назад, # ^ |
    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).

»
10 лет назад, # |
  Проголосовать: нравится +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)

»
10 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Sorry, where we can find results?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +22 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится +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)

»
10 лет назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится
»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

When will test data come?

»
10 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

When will the tasks and the test datas be available?

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For APIO Palindrome, there's a simple solution without palindrome tree or other complicated stuffs. First some things which are probably obvious:

1) Check if interval is palindromic. [rolling hash]

2) Find number of occurrences of substring in string [suffix array]

So now it reduces to finding all palindromic distinct substrings, then finding their occurences, and so on. Finding all palindromic substrings works like this: first fix the middle element(s) and then binary search how far out we can go whilst maintaining it as a palindrome. For instance, if we have aaabacac and fix the 'b', then we can expand out to length 3 (aba). If we fix the last a, we can expand out to cac. And so forth. So now we have a bunch of relatively long palindrome. But of course this does not comprise of all palindromes. To find all palindromes, we can compress our long palindromes by removing first & last characters. As we compress one by one, eventually, we will reach a palindrome we have already seen — we can stop there.

Code