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).

**Tasks analysis: C**

Any ideas why?

Here's the code: http://pastebin.com/79PFDzrG

Too bad, that would've been the difference between qualifying and not qualifying :/

What I did was a dp[position][didMistake] for each number.

i'th person who arrives for first action its optimal for him to go to windowi mod k1. And the same for actions two and three. Then simulate this. (I did this way, don't know about others...)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.

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

O(n^{2}log(n)) C++ solutions have managed to pass system tests. We are sorry for that. Planned asymptotic isO(n^{2}), but there isO(n) solution.O(n) solution?O(N^2 log N)solutions in problem D's status? Like this one with id 464685:#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));

}

}

}

}

N^{2}logn, butN^{2}. And it have very small constant, so it passed.N log Nso totallyN^2 log N. Am I wrong?EDIT: Hehe!! Of course I'm wrong!! Sorry :D

O(N^2 log N)? I think it's justO(N^2)This kind of problems should generate data with defferent monotonicity to beat various brute force approaches.

linear time insertion and removal of elements at the beginning or in the middle."^{9}primitive copy operations. Modern processors are fast enough to handle this amount of work in 4 seconds.^{9}simple operations took more time!