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).
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 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.
#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));
}
}
}
}
EDIT: Hehe!! Of course I'm wrong!! Sorry :D
This kind of problems should generate data with defferent monotonicity to beat various brute force approaches.
E was quite actually nice problem. Nice concept. Thanks for the round.