KrK's blog

Codeforces Gym: KTU ACM ICPC Qualification Round 2014
By KrK, 10 years ago, In English

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

Tags gym, ktu
  • Vote: I like it
  • +43
  • Vote: I do not like it

Comments Comments (14)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Kaip užsiregistruoti??

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

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

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

Will there be solutions of the problems?

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

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

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

    → Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

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

    No tests have been changed during the contest or after it.

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

    i think it is impossible

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

    "My code is too slow, so probably tests are broken"

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

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

    → Reply