lperovskaya's blog

Yandex.Algorithm 2014 Elimination stage: round 1
By lperovskaya, 10 years ago, translation, In English

Wow, what a weekend! I hope you all have plenty of energy and solutions for all the problems you will see in coming contest.

Elimination stage of Yandex.Algorithm 2014 will start in eight and a half hours. All qualified participants can see it on the link. Round will last 100 minues, its top 30 participants will earn score points based on Gran-Prix 30 system. Finalists will be chosen based on the total score points earned throughout the elimination stage.

Good luck and hope to see you in Berlin!

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

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

How to solve E ?

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

    Answer is always <=6 (because we can make every number in range 1..63 using values of 1,2,4,8,16,32), so you may set answer to 6 and try to improve it searching over all possible smaller sets of numbers in range 1..50.

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

Let us all contribute to write an editorial for each problem.

I start with problem A.

It is simple brute force time taken 3 ms memory 380 kb.

Make a recursive function which processes ith inpu. calculate new-sum based on current sum and current index. Then permute the digits of newsum and pass it as current sum with i+1 as current index.

My solution link.

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

    B: Sort the ducks according to initial tone, then do DP trying to group two or three adjacent ducks and force them to have same tone. It doesn't make sense to make larger groups as they'll all be formed anyway, i.e. a group of 4 can be no better than 2 pairs.

    C: Four sides a <= b <= c <= d can form a concave polygon if a+b+c>d and a != d. Sort the lengths and try all groups of 4 consecutive lengths.

    D: You don't need to keep track of the actual values of both Wojtek and Tomek, just the current xor between the two values. Then do DP with state (current element, current xor).

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

      For C, you mean a <= b <= c <= d and a!=d right?

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

        Yes, you're absolutely right. Edited.

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

    Why have I got -8?? I thought I had taken an initiative.

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

      Okay. Moral : Dont run after the votes.

      But I had not done it for votes. only problem is that my current contribution is -1 :\

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

In Gym: 2014 Yandex.Algorithm - Elimination Stage, Online Round 1

===

Добавил тренировку: 2014 Yandex.Algorithm - Elimination Stage, Online Round 1

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

    Why can't we see the accepted solutions for the Yandex Rounds in the gym? Making them viewable could be beneficial to all, I think.

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

      Disclaimer: though right now I'm a Yandex employee, I'm not a member of the organizing commitee.

      AFAIK, to do so, Yandex must ask a permission from all the participants to publish their solutions, otherwise such publishment will be a violation of the law about personal data.

      Well, it'd be possible to write in the rules that a participant grants Yandex such a permission, but it hasn't been done and now it can't be changed. That's all.

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

How to solve F?

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

    That's exactly what I want to ask!!! BTW, Here's a short editorial for A-E in Chinese if anyone is interested. CLICK

    → Reply