Yandex.Algorithm 2011 - Round1
By frost_nova, 14 years ago, translation, In English

We are glad to welcome all contestants of a qualifying contest "Yandex.Algorithm 2011 - Round 1".

Today's round authors are Vitaly Goldshteyn, Ignat Kolesnichenko, Stanislav Pak and Denis Yarets. All we are employees or interns of Yandex. We really appreciate Artem Rakhov, Maria Belova and Mike Mirzayanov who helped us to prepare the contest. We hope that our tasks will be quite interesting and you will get much fun solving them.

As you may know top 200 contestants after this round will be able to continue fighting for spots in the final round.

Please pay attention that as well as during the previous qualifying round Codeforces functionality will be a little cut down for the time of the competition. Do not worry, all will return into place after the end of the round.

Round will be rated for the official participants, and for those who failed to qualify and participate out of competition (unofficial).

Good luck and high rating for everyone!

Tasks analysis: C
  • Vote: I like it
  • +116
  • Vote: I do not like it

14 years ago, # |
  Vote: I like it +15 Vote: I do not like it
Good luck & Have fun!!
→ Reply
14 years ago, # |
  Vote: I like it +14 Vote: I do not like it
Today I learned Yandex really likes trees! (And so do I, so I enjoyed today's problem set.)
→ Reply
14 years ago, # |
  Vote: I like it +15 Vote: I do not like it
I liked watching the top 5 challenging each others at the last few minutes! Especially RAVEman and tourist! :)
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I wrote a test case generator for hacking for the first time (for Problem C), but I got an "integer 0 out of range [1, 1000000000]" error.

Any ideas why?

Here's the code: http://pastebin.com/79PFDzrG
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it
    The problem statement says "positive integer", so you need to change from '                        System.out.println(i);' to '                        System.out.println(i+1);' in line 24
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Thanks!

      Too bad, that would've been the difference between qualifying and not qualifying :/
      → Reply
  • 14 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    In the last loop, you print out "0", which is not allowed (any positive integer).
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Does anybody know the pretest 4 for problem C?
What I did was a dp[position][didMistake] for each number.
→ Reply
14 years ago, # |
  Vote: I like it -8 Vote: I do not like it
No one can beat tourist! Hard luck RAVEman.
→ Reply
14 years ago, # |
  Vote: I like it +44 Vote: I do not like it
Very fast system test! in 13 minutes only :)
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    Along ago we were to wait 1 hour for system test! Thanks CF for these improvements.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it -18 Vote: I do not like it
    How did u solve B?? It looked ample hard to me... U rock dude :)
    → Reply
14 years ago, # |
  Vote: I like it +61 Vote: I do not like it
I was very lucky. 20 seconds before the end of the contest I've solved only A, but I qualified!
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Why did you not try B,C,D? 
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it
      B and D looked very hard for me. I thought A + C is not enough to qualify, so I decided to solve E.
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it
        Congratulation!

        In my opinion, today's problem is a little strange.
        And the statements is too long, I have to read it more than once to get the right meaning.

        → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Problem B seemed interesting though i couldnt solve it. Can anyone share the idea?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I just simulated using 5 deques.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Prove that the i'th person who arrives for first action its optimal for him to go to window i mod k1. And the same for actions two and three. Then simulate this. (I did this way, don't know about others...)
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
For each window, you save when a person can reach it the first time. This is the maximum of the time the person arrived (or did go to the window before) plus the time it takes for that window and the time the kth person before him finished plus the time it takes for that window.
→ Reply
14 years ago, # |
  Vote: I like it +9 Vote: I do not like it
Is everyone going to post their solutions for B ? :) They all look the same and it's not interesting.

I think C and D are much more interesting to discuss.

In D I used  N*Sqrt(N) algorithm which looked obvious to me. The most popular approach was cartesian tree.  Some others used Interval trees.

I think C was harder than D. I looked at some passed codes and they look like O(N^2), but I am not sure.


→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    I made a solution for C using Fenwick Tree and I haven't seen any solution like mine :D
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      In C I also can't find the solution similar to mine :)  I saw some easier solutions.

      Still, D allowed much more different solutions and therefore, it was easier than C in my opinion.

      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I've got a segment tree solution for problem D. It's an offline algorithm, I find all values which I can have. Then I sort and take the unique elements. This is the reference array for my segment tree. The actual array for the segment tree is a boolean valued array, which represents if the i-th element exists in the set or not.
        I run a dp/segment tree kind of query from the root for each sum query. I compute the number of elements in the left subtree (using another count dp/segtree). The the offset for the right subtree is (parentOffset + left)%5
        In this way I get the list of all elements in log(n)

        For every update, I start at the leaf and proceed towards the root, unsetting all the dp values.

        I liked this idea, it was going around in my head for a while, finally implemented it today :) 
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Our idea is same,I also use segment tree and I got Accepted using 280ms in Final Test.I like this problem:)
          → Reply
14 years ago, # |
  Vote: I like it +6 Vote: I do not like it
Problem E may be too easy.
Just a little bit tight time limit.
An easy o(n^2 log n) solution with small time constant can pass ...
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Yes, it may happen because of necessity to double a working time of a reference solution written in Java, that is why a few optimized O(n2 log(n)) C++ solutions have managed to pass system tests. We are sorry for that. Planned asymptotic is O(n2), but there is O(n) solution.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Could you share the idea of O(n) solution?
      → Reply
14 years ago, # |
  Vote: I like it -12 Vote: I do not like it
Increase the number of programmers qualifying for the second round if u can 200 seems too less.... :-|
→ Reply
14 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

Why there are passed O(N^2 log N) solutions in problem D's status? Like this one with id 464685:

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

#define long long long

#ifdef DEBUG
#define WATCH(x) (cerr << #x << '=' << (x) << endl)
#define TRACE(x) (cerr << (x) << endl)
#else
#define WATCH(x) /*()*/
#define TRACE(x) /*()*/
#endif

vector<int> v;
int n;
int main() {
    cin >> n;
    v.reserve(n);
    for(int i = 0; i < n; ++i) {
        string s; cin >> s;
        if (s == "sum") {
            int l = v.size();
            long sum = 0;
            for(int i = 2; i < l; i += 5) {
                sum += v[i];
            }
            cout << sum << endl;
        } else {
            int x; cin >> x;
            if (s == "add") {              
                v.insert(lower_bound(v.begin(), v.end(), x), x);
            } else { // s == "del"
                v.erase(lower_bound(v.begin(), v.end(), x));
            }
        }
    }
}

→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it
    It's not N2logn, but N2. And it have very small constant, so it passed.

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

      The use of lower_bound function makes the del and add N log N so totally N^2 log N. Am I wrong?
      EDIT: Hehe!! Of course I'm wrong!! Sorry :D
      → Reply
  • 14 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    why it's O(N^2 log N)? I think it's just O(N^2) 
    → Reply
  • 14 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    Because all the test cases are sorted or just random numbers
    I am sure this solution will fail if a test case like this one exists

    100000
    add 100000
    add 99999
    .
    .
    .
    add 2
    add 1

    Too bad there are no hacks during practice!
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Agree with you. The testdata looks weak.
      This kind of problems should generate data with defferent monotonicity to beat various brute force approaches.
      → Reply
    • 14 years ago, # ^ |
      ← Rev. 2   Vote: I like it -7 Vote: I do not like it

      It will work ~2 times slowlier. But TL is 4 seconds, so that this solution could pass.
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it
        This is so weird! I am very curious to know what is happening!

        "A vector is a Sequence that supports random access to elements, constant time insertion and removal of elements at the end, and linear time insertion and removal of elements at the beginning or in the middle."
        source: http://www.sgi.com/tech/stl/Vector.html

        Do you have an explanation?
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          There are about 5· 109 primitive copy operations. Modern processors are fast enough to handle this amount of work in 4 seconds.
          → Reply
          • 13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            Check the links, doing 5.109 simple operations took more time!
            → Reply
            • 13 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              Are you know that ideone and codeforces have different servers? Try to run your code here.
              → Reply
              • 13 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it
                More or less the same result, the simple nested loop run slower (3780 ms) than the vector (3050 ms).

                I expected that inserting elements at the beginning of a vector and shifting the whole vector content would be slower than a simple nested loop but the result was a surprise!
                → Reply
                • 13 years ago, # ^ |
                    Vote: I like it +3 Vote: I do not like it
                  I suppose this is because memmove which vector<int> uses for shifting is thoroughly optimized.
                  → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I've tested this solution on such case, it works for ~3 seconds. However, I was surprised that there is no similar case in official tests.
        → Reply
  • 14 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it
    #define long long long
    :D
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I found a small bug on codeforces: top-rated on the top page looks a bit old. http://gyazo.com/9c850d39ab001b012816baaf52becd9a.png
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Does smb have problems with registration outside the Round 2?
→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

E was quite actually nice problem. Nice concept. Thanks for the round.

→ Reply