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

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

Hello, guys!

Do you remember the recent competition (KTU ACM ICPC Qualification Round 2013)? The better prepared and harder version of it (KTU ACM ICPC Qualification Round 2014) is scheduled on Sunday, Sep 28, 2014, at 12:00 PM.

The onsite contest has taken place today and it was very hard for KTU students. I would give it three stars of complexity but maybe a problem or two might be interesting for Div. 1 participants too.

Please, don't participate, if you have participated in the contest onsite.

Enjoy the contest!


Solution / Secret input

Теги gym, ktu
  • Проголосовать: нравится
  • +43
  • Проголосовать: не нравится

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

Kaip užsiregistruoti??

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

    To register: go to "Gyms" section, then choose the contest "KTU ACM ICPC Qualification Round 2014", click "register", then enter, and that's it :)

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

Will there be solutions of the problems?

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

Can you explain a little bit about your solution in the problem I?

My solution is to build new weighted directed graph, each vertex contains two elements, they are two vertices of the current graph. After that, for each meeting place M, I will calculate the expected numbers of steps to go from vertex (A,B) to (M,M) in the new graph by solving a system of equations. My total complexity is O(n^7). With your input, my program runs in 1.77s and get TLE because of the time limit is only 1.75s.

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

    Could you reduce the dimension of matrix by merging equivalent states?

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

Had tests of problem E been changed after contest? I get TLE using multiset, but found many AC solutions which used multiset or segment tree.

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

I could not able to get the points ll d = -Q.top().first; and Q.push(ii(-work[cand], cand)); in the solution to number A problem while applying dijkstra. Why are we taking the negation. May be it's something simple but I really cannot get it and this has taken away a lot of time.

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

    Because C++ priority queue returns maximal, not minimal element when you call top()