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

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

Join us on Saturday, March 7th, 2015 for the seventh round of COCI!

Click here to see when the coding begins in your timezone!

  • Проголосовать: нравится
  • +30
  • Проголосовать: не нравится

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

I guess you like prime numbers, don't you? :P

I mean the rounds that you announce.

Good luck to everyone!

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

    It seems so. Good thing it's the last round otherwise there would be 3 more unannounced rounds!

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

Let's discuss the problems now. What is the idea behind the 5-th task? I used the O(N^2) in case N<=7000. Otherwise, I do this 2^20 times:

1) Take a random L: K<=L<=N

2) Take a random F: F+L-1<=N

3) T=F+L-1

4) Take the average for the interval [F,T] and compare it to the answer...

Update: WTF?! It got full score :D

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

    I write it using answers binary search,in O(n*log^2 n) ,but it failed,may be it's may mistake in code not in idea (((

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

    Binary-search the answer, rewrite as and use prefix sums + 2 pointers on A[i] - a to check if a is a possible answer.

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

    I was the author of this problem and I apologize, I tried to make test data to break as many bad solutions as possible but it didn't even occur to me that such random solution would find good answers.

    Intended solution was, as Xellos already said, binary search the answer P, subtract P from all elements and check if there exists non-negative sum subsequence of length at least K.

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

      Thanks, ikatanic, Xellos and LashaBukhnikashvili for the explanation :)

      PS: It didn't even occur to me too that it would pass all tests, I expected only 42 points :D

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

      sorry but did you announce that your problem is a common problem of binary search? link

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

        I haven't tried googling it, it surely isn't standard problem for HONI competitors. HONI is intended for Croatian high school trainings and no one got full score on it. As for COCI (which is open-to-everyone HONI mirror) I thought it would be totally fine (maybe it should have been worth less points) because neither I nor other problem setters have seen this (or similar) problem before.

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

    Also something like convex hull trick and ternary search works.

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

      Could you explain this solution with details?

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

        We map every array element to some coordinates like in the following code:

        int x = 0;
        int y = 0;
        vector<pair<int, int> > v;
        v.push_back({0, 0});
        for(int i = 0; i < n; ++i) {
            ++x;
            y += a[i];
            v.push_back({x, y});
        }
        

        Now the average can be seen as the slope between two points. Then we iterate through the vector v and maintain a set of points that form the convex hull of the points that we have visited.

        Now consider that we have the (K-1)th (the length of the subsequence must be at least K as stated in the problem) non-visited array element (or the corresponding point). We know that the consecutive subsequence that starts from there must start from some of the already visited array elements (or point). It can be seen that we cannot get the best average (or slope) by selecting some point that does not lay in the convex hull. Therefore we can use ternary search to find the best average (or slope).

        It seems that there is also somewhat similar solution but which uses two pointers and therefore is O(n), but I don't know it in details.

        EDIT: I hope I'm now a bit easier to undestand...

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

          Nice solution , thank you!

          the tip that I learnt from this is that when ever the problem ask you to maximize a function that contain a fraction consider a convex hull solution.

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

      What is the convex hull trick?

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

    Damn, I managed to write 10^6 with 5 zeroes as upper bound of my binary search, damn :P

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

How to solve C?

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

    My idea is to consider all permutations of the rows. I mean:

    row1

    row2

    row3

    and then

    row1

    row3

    row2

    and so on...

    Now, let's build a graph for each permutation. From element in row i and column j there is an edge to (i,j+1) with weight a[i][j+1] and to (i+1,j+1) with weight a[i+1][j+1]. Of course, if there are no such positions we will not put edges.

    For each permutation run Dijkstra from (1,1). The answer for the current permutation will be in (3,N). At the end, the answer is the minimum of the answers for each permutation.

    Code: http://ideone.com/CMXKqJ

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

      Looking at the official solution the problem setter only usude the first permutation (row 1,2 And 3). You know why?

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

        I have absolutely no idea why, my idea seems to be exactly the same but with all 6 permutations. Can someone explain it, please?

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

          simply the official solution code is not correct!

          I tried it on the sample test cases

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

          It's because that was HONI version of the task (permutation was specified in the task). COCI solutions are up now so you should check them out.

          EDIT: Sorry, actually HONI solution was accidentaly uploaded to COCI, it will be fixed soon.

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

    let see all permutation about this 3 array. first we are picking numbers from first,then from second and then from third: then if you are picking numbers from second array in (l,r) segment, for this ans=sum[1][l]+sum[2][r]-sum[2][l]+sum[3][n]-sum[3][r] (sum[i] its prefix sums in i array).

    if we will choose l from 1 to n-2, all will be const except sum2[r]-sum3[r],this means that we need such r,that sum[2][r]-sum[3][r] will as small as possible,you can write preprocessing for it,its all. sorry for my bad english )) here code.

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

I came up with different N*sqrt N solution for 5th task: If we have an subsequence with average a [L,R], we can add to end of it subsequence [R+1,X] where [R+1,X] has largest average from all subsequences that begin in R+1 and the average is larger than a.(it will increase average of original subsequence). We will do this until there isn´t any subsequence that we can add to end.
To make it faster we will add only subsequences that are larger than sqrt(N), and when there is no subsequence larger than sqrt(n), we will add subsequence smaller than sqrt(N) that will at most increase the average of subsequence.

We can calculate where ends the subsequence larger than sqrt(n) with largest average with similar DP method(from right to left).

Is this solution correct and would it pass?

I am really sorry for my bad english.

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

    Could someone tell if it is correct?

    Please I am not sure that i am able to code it so I would be really happy if someone said if it is good idea(and if it is correct it should be in solutions pdf :-))

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

Last November, There was a task which is almost the same with the 5th one of this COCI at the Turkish National Olympiad In Informatics. Unlikely with the COCI version of this task, Turkish one was required finding the average of the consequtive subsequence whose average is maximum off all the consequtive subsequences whose lengths are between given two integers A and B. The time complexity for this question was O(NlogT). ( T = number range )