Yandex.Algorithm 2011 Qualification 2
By NALP, 14 years ago, translation, In English

I'm glad to welcome all fans of programming!

The second qualifying round Yandex.Algorithm will take place today, and it was prepared for you by Artem Rakhov, Michael Mirzayanov and me.

Please pay attention that as well as during the previous qualifying round Codeforces's functionality will be a little cut down for the period of the competition. Don't worry, all will return into place after the round termination.

I remind the best 500 participants pass in Yandex. Algorithm 2011 Round 1 which will take place on May, 20th at 19.00

Good luck!

UPD: the contest is over, congratulations to the winner - tourist!

I recall this competition was a qualifying round, and the best 500 will take part in Yandex.Algorithm Round 1!

Today two participants were the most lucky - Hossein_Hima and ss.nurboolean, - they have taken 499-500 places together with result 978 scores.

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

Comments Comments (47)
| Write comment?
14 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Almost 2200 registrants :P Grats :) Hope the server will stand it :)
→ Reply
  • 4 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Lol! reading this comment in 2020, it feels funny, how much CF has grown even a DIV3 contest has more than 12000 official participants

    → Reply
14 years ago, # |
  Vote: I like it +35 Vote: I do not like it
n=2 is awesome. :)
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it
    +13 challenges. Why can't I challenge myself? :)
    → Reply
    • 14 years ago, # ^ |
      ← Rev. 3   Vote: I like it +3 Vote: I do not like it

      Thanks to n=2 and my greed for hacks and now my rating will drop exponentially!    :(

      EDIT: but my contributions may increase...
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Somebody hacked mine.. and so i noticed the n = 2 case :D
        → Reply
  • 14 years ago, # ^ |
    ← Rev. 3   Vote: I like it +7 Vote: I do not like it

    Isn't you comment considered as cheating?
    EDIT: Sorry I thought it was posted before the end of contest. Really sorry...
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it
    I am so greatful I was hacked.
    → Reply
14 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it
If you already have qualified, you may take part as out of competition participant (informal). Anyway the contest will be rated for you.


Does this mean the contest is rated for the informal people?
→ Reply
14 years ago, # |
  Vote: I like it +4 Vote: I do not like it
For mathematical reasons, for problem C I would like to know what is the maximum number of days, if the weight of each edge is one. I think this number cannot become to large, but I would like to have some upper limit.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it
    limit = n because every daysomebody arrive to capital
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      It's not so obvious! Somebody can linger in some verteces
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it -13 Vote: I do not like it
        В каждую вершину, у которой хотя бы k, потомков пришло не менее k составов.
        База для k=0 очевидно.
        Пусть пришли еще не все потомки, тогда из какого-то поддерева пришли не все потомки, тогда в вершину поддереве там пришло не меньше (k-1) за k-1 ход+1 была. Значит там что-то есть=> Оттуда что-то приедет.

        Sorry, can't translate it
        → Reply
    • 14 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it
      Ah yes, that's a very critical observation. I cannot deduce that during the competition :D
      → Reply
  • 14 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    Isn't it n-1? 
    → Reply
  • 14 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    Edit: sorry, this is wrong.

    Let d be the maximum distance from the capital to a people. Let x be the number of people whose distance from the capital is d. "x + d" is initially at most n, and each day this value always decreases.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Tragedy. I wasted my first 60 mins.
→ Reply
14 years ago, # |
  Vote: I like it +16 Vote: I do not like it
My java solution in problem C TLEd and an identical C++ solution passed, this is really annoying :S
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    time limit for C seems to be strict.... I used C++ STL and it got TLE :(
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
How can I know whether I have qualified?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    You should be in first 500 in one of the 2 qual rounds (don't mark out of competition in second round).
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    You qualified if you in top500
    → Reply
  • 14 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    If your position not bigger than 500. 

    BTW, 663>500 so you did not qualified. Sorry.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    If you are in first 500, without those out-of-competition - Congradulations! :)
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it
    What a pity ...  : (
    → Reply
14 years ago, # |
  Vote: I like it +23 Vote: I do not like it
when will be the ratings updated?
→ Reply
14 years ago, # |
  Vote: I like it +36 Vote: I do not like it
When will the rating be updated? 
I won't go to sleep until my rating changes ...
It's 3 in the morning in CHINA +_+...
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
How Solve Problem B ?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Find any set by intersection 1st union with others.
    After that check all unions that intersect this set & write out union wthout this set

    Don't forger to if n=2
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    Let's a[i][j] := amount of strings(in input) where i and j are exists.
    In case n > 2 a[i][j] = n-1 if and only if i and j were from one set. Find a for all 1 <= i, j <= 200, and you can find answer easy!
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    for each number from 1 to 200 calc FIRST and SECOND
    FIRST - input line in which was first occurence of this number
    SECOND - input line in which second occurence of this number

    two number belong to one answer where they have equal FIRST,SECOND pair
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    simple :)

    1. u have not used points  used[1..200] all set to 0//not used 

    2. read n - amount of sets,set must out sets o=n;

    3 while readind n*(n-1)/2 pairs of sets do this:{ line number is j

    set setA=empty; setB= empty;

      read k-amount of points 

       for all k points p in this line j do {

        if used[p]<0 continue;

        if   used[p] ==0 {is notused mark used[p]=j//it means that number p  fist time in j line}

        else if used [p]>0 {it means that in j line we get set   

          with  p points in 2nd time so we can solve what set has p point 

         if (A.empty||used[A.top]==used[p])A.push(p)   else B.push(p)

    }//end for k points in j line

    if(not empty A){out(A);mark all p in A used[p]*=-1;o--} 

    if(not empty B){out(B);mark all p in B used[p]*=-1;o--}

    }//end for j lines of n*(n-1)/2 lines of pairs sets

    test if (o>0){//o==2

    cose we have last readed line like k a1 a2 .... ak

    we make hand made out like

    line1: 2

    line2: 1 a1

    line3: k-1 a2 ... ak

    }

    thats all 

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

      loose time cose this solution solv not only problem B but problems where not all pairs n*(n-1)/2, but that where each sets no less 2 times so this can solv:

      4

      4 1 11  2 22

      4 1 11  3 33

      4 2 22 4 44

      4 4 44  5 55

      4 5 55  6 66

      4 6 66 3 33

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

    It's al MUCH MUCH simpler.

    Read the first of n*(n-1)/2 union. Remember the first element of it - F.

    Then read all other unions and save only containing this F.

    We will get n-1 unions U1, ..., Un.

    Then intersect U1 and U2, we will get A0, that contains F.

    After that subtracting A0 from every Ui, we will get Ai.

    And A0, ..., An-1 are the answers. :)

    If I'm not mistaking, it could be realized with complexity O(n*m) where m is the number of different elements, so about const*200*200 solution.

    And don't forget about 2.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      I don't think that your solution is simple. It's better to build a graph with M verticies (up to 200 verticies). Where each vertex is assigned an unique value of Ai.
      For any edge (u, v) of such graph we should count its weight as the number of times the values u and v appeared in one union. If this number is smaller than N - 1 we should ignore this edge in our further solution. And than it's very simple to find all the connected components. Solution requires O(M2) time and O(M2) memory.
      Of course, we should carefully deal with N = 2 again.
      → Reply
14 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You count also out of competition participants. There is exactly 500 advancers from this round and the border is 978 points.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can anyone explain how to solve E ?
→ Reply
  • 14 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    First, sum the areas of the shadows from all windows, and then subtract the areas counted twice.
    For the first part, note that you may count each window (and both lightbulbs) separately, and each window gives a trapezoid shadow.
    For the second part, you will each time only need to intersect two such trapezoids -- one from the upper bulb and one from the lower. It may look even easier if noticed that you may intersect triangles, not trapezoids.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I noticed n=2 when I read the B again, and then I almost Hack all others in my room.
However, the origin set in B could be 19900, and I announced 200....
→ Reply
14 years ago, # |
  Vote: I like it +13 Vote: I do not like it
I thought that problem D was really pretty, how did you guys do? I did a O(n^2) memoization dp[i][j], where 'i' and 'j' were the first two guys at the queue, because if you notice, the third guy's index will always be j+1, and realizing that can give you a simple memo coding.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Will be a posibility to compete out-of-competition, for those who are not qualified?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Yes.
    And it will be rated for out of competition participants too
    → Reply