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

Автор dreamoon_love_AA, история, 8 лет назад, По-английски

Dear CodeForces,

I added one interesting team contest for preparing ICPC World Final into gym!

Every year National Taiwan University will host selection contest in order to determine which team will go to World Final. This year, I host this contest. Ideas of most problems are came from me. Hope these problems can let everyone feel interesting!

I set the start time of this contest as 13:30 UTC. If you have no time in this time slot, don't be sad. You still can choose any time after that to enjoy the contest.

UPD: Reminder : The contest will start in around 6 hours from now.

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

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

Auto comment: topic has been updated by dreamoon_love_AA (previous revision, new revision, compare).

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

Contest starts in ~2 hours.

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

how to solve E and I?

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

    Roughly speaking, E can be solve by divide and conquer + segment tree with time complexity O(n(logn)2) and there are many similar problem such as ARC064 pF. This problem can also be solved with time complexity O(nlogn). But the detail of implementation is quite hard and I guess the constant in time complexity is large. If you have interesting in such method, you can read this paper.

    I can be solved by connecting leaves from bottom to up greedily.

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

      I have invented a brute_force idea and AC problem E..

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

        In fact, when we were testing problem, peter50216 also give a not clear time complexity algorithm and pass all tests. But I think it will take much time to do that, so I determine to ignore this reality situation >_<

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

          I have generate a test that my code will TLE out of 10s

          n=99998;
          td=bd=0;
          for(i=0;i<n;i++)
          {
              if(i<=n/4)
                 per[i]=n/2-2*i;
              else if(i<=n/4+n/4+n/4)
              {
                 if(i%2==0)
                 {
                    per[i]=n-td;
                    td++;
                 }
                 else
                 {
                   bd++;
                   per[i]=bd*2;
                 }
              }
              else
              {
                 per[i]=n-td;
                 td++;
              }
          }
          
    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      I think the method given in that paper is not correct. It uses a divide and conquer method and claims that the contribution of the "left" to the "right" can be computed in linear time. Let {a1, a2, ..., ak} be the points whose DP values are used to compute point b's DP value (in the naive DP solution of problem E). Let ai + 1 be the "father" of ai for any b and i. The paper claims the "father" relationship induces a forest. But this relationship is not well-defined. Although one point a can have at most one "father" considering all different b's, whether it has a "father" or not differs.

      (This gives a simpler algorithm based on that one in the paper that works in time?)

      UPD: I implemented this algorithm and it works fast. (http://mirror.codeforces.com/gym/101234/submission/24290713) My algo is similar to the one in the paper except for the part for which I used dsu costs only constant time in that paper. Could you guys implement the paper's algo proving my being wrong?

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

I thought that E and I were haredest problems. and A and F were interesting. I solved E with sqrt decomposition and I with Tree DP. O(N (log N)^2) solution of E looks interesting. I think it was a great contest. Thanks for exciting problems!

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

    E can be solved by link cut tree O(n*log(n)^2) if you use divide and conquer and record virtual edge it will be O(n*lg(n)) and will be easier than link cut tree. I hope admin can add some tests and challenge my solution..

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

Is there a reason why the contest is not accessible anymore?

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

wonderful mromlems

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

Could someone tell me how to solve G? I want to solve it with binary search but get TLE on test 3. Thanks a lot!