eatmore's blog

Yandex.Algorithm 2015 Qualification Round
By eatmore, 9 years ago, translation, In English

Yandex.Algorithm 2015 Qualification Round begins soon. It is the last chance for those who didn't participate in the warm-up round or haven't solved at least one problem to advance to the elimination rounds, which will take place on May 24th and 30th and on June 6th.

The round will last 100 minutes and will be a virtual contest: each participant will be able to choose start time in the period between May 16th 21:00 and May 17th 21:00 UTC. This means that some participants may potentially be competing until 22:40 UTC, so please don't discuss the problems until that time. To advance to the elimination round, it is necessary to solve at least one problem.

  • Vote: I like it
  • +66
  • Vote: I do not like it

Comments Comments (16)
| Write comment?
»
9 years ago, # |
← Rev. 2   Vote: I like it +25 Vote: I do not like it

I started the contest, but problem statements seem to be unavailable. Instead of problem statements, there is just text "Problem statement is unavailable".

edit: All problem statements are now available in english.

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

    Same here. I can only read problem D and F but only in russian...

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

    i am also facing same problem and my time counting already started

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

      Yeah me too, but the clock doesn't stops ticking.

      → Reply
»
9 years ago, # |
  Vote: I like it -49 Vote: I do not like it

WESLEY SNEIJDER & GALATASARAY! CHAMPIONS

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +44 Vote: I do not like it

To advance to the elimination round, it is necessary to solve at least one problem.

Is it also sufficient to advance by solving only one problem?

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

My first submission stayed with the "waiting" status for about half an hour and I had a stupid bug that I had to wait half an hour to correct. I hope this doesn't happen in the Elimination rounds.

Also, the scoreboard was not live but updated every few minutes. I could not see my new position immediately after getting a problem Accepted.

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

How can I change my country (in the standings etc)? It says that I'm from USA and I can't find how to change it. I haven't put "USA" to anywhere.

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

What's the solution for "Optimal Playlist"?

My Unaccepted Solution:

f(x) -> returns if graph with edges that cost at most x can make a playlist.

  • It converts the graph into a DAG by shrinking SCCs. Then it uses a modified version of Kahn's algorithm to check if there are more than one vertex with a in-degree of 0 at any state. If there are, it means that we can't make a playlist.

It uses binary search to find the least x such that f(x) is true, which is the answer.

My Implementation

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

    That is incorrect because of this test case: (the edges)
    1 2
    1 3
    there isnt a walk that goes to 2 and three so yeah ofc you'll get werong answer

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

      Can you elaborate a little bit? I think my algorithm works for this case.

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

        give me a walk that crosses vertex number 2 and vertex number 3 it is impossible because you can't get out from either 2 or 3

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          ← Rev. 3   Vote: I like it 0 Vote: I do not like it

          I know. it's impossible according to my algorithm too. It first removes 1 because it has a in-degree of 0. With the removal of 1st vertex, both vertices (2 and 3) start to have 0 in-degree. Since there are more than one vertex that has a in-degree of 0, there isn't any walk that visits every vertex at least once.

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

            Oh Lol sorry i didn't know Kahn's algorithm, anyway i think if you check if the i'th component is connected to the i+1'th it get's accepted

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

    You need to clear adj2 after every call to f().

    → Reply