That number must have only 2,3,5 or 7 as prime divisors. Make 4 dimensional state (num2, num3, num5, num7) and solve it with dinamic programming.

If I solved A small, can I send my solution to A small again to test the A big before submiting to big tests?

I had to turn language to Russian. You could write the same post on English language. Nobody told me anything. You could email for example. What is the mean of turning off the registration? please at least turn it on!

Our team advanced to round 2 and I have no idea where is the original round 2.

Guys, How did you solve "The Array Challenge(Easy)" and "Summing The AGP" hard parts?

1-1

http://codeforces.me/blog/entry/4004#comment-184036

I did the same, but took 50 instead of 10.I think 20 is enough, but took 50 for insurance.

Guys, how did you solve 4th problem?

Remove all expired time and change 6 min to 15 min ;)

I upvoted you for your avatar!

When is the final ? On Bayan site I saw that final is in 8 days, but organizers posted here that they would tell us at least 50 days earlier. Did any finalist received the final contest date notification ?

Can our team participate unofficially by internet?

Are you painting mountain? :)

It's okay as long as no girl is a winner.

http://www.wikihow.com/Check-if-a-Number-Is-Prime

Thanks both of you very much.

can you tell me exactly what should I write in the code for GCC compiler to increase the stack size?

1 — 2

2 — 3

3 — 1

2 — 4

4 — 5

5 — 2

in this graph the best path is 1 2 4 5 2 3 1. not 1 2 3 1.

in Problem 2 — Fairy Chimneys, can you enter the vertex more than once ?

Can anybody explain the solution of problem E ?

or you can wait for the run for 2-3 minutes.

fix it -_-

I cant submit my code . Please fix it.

nope.

Looks like somebody important rang and said he was late to register.

Finally understood 221 Div1C solution , my fault . But still don't know how to solve GoodBye E even in O(N^2) :(

The solution of problem E wasn't not clear for me after reading that comment too . I have read it before writing this post .

I can find out the solution after analyzing the codes , if I spend much time . Tutorial exists to use time effectively .

If they are writing tutorials such , that I must try hard to understand it myself , just don't call that post tutorial and everything will be okay .

Thank you very much . I have one more question . Why BFS works and DFS doesn't work? When we add another information , which changes the distance between vertices , why BFS will still work ?

In Div 1 C , how can we pass from one state to another state in BFS ? Can somebody explain this or I must analyse codes ? Authors should write more detailed tutorial .

great !

Yes , I know time will be the same , but those bitmasks was needed on opencup contest , where 64 bits didn't passed (WA) , 32 passed , so I am asking what is wrong with 64 bit integers .

In Problem "356D — Bags and Coins" , can we write masks in unsigned long long , so we can solve the problem in n*s/64 operations ?

thank you , nice solution :)

Can you write in short divide&conquer solution ?

still waiting for D tutorial ...

you should check 3 things:

1. Any 3 points is on 1 line

2. Any two points coincides

3. Any two not adjacent side of QUADRILATERAL intersects (I don't mean their continuation) , AB intersects CD or BC intersects AD

If any from this 3 happens its not QUADRILATERAL else it is

thank you , I once read that topic , but I couldn't understand it , I think I got it now :)

Can you link me any tutorial of persistent segment tree ?

for each C and D array you must make the pair of the number with it's position and sort it. Then for the permutation of the positions you must build the segment tree , where in each node there is a sorted vector and in the vector all the numbers are which are below that node.if the query is [L,R] you must find (R-L+2)/2 th number such that its position is in segment [L,R] . Now for each Query you must go down from the root of segment tree . check how many numbers are from the segment [L,R] (with binary search) in the left child , if it is less then (R-L+2)/2 go to the right , if not go to the left . you'll find the median in the leaf. running time is NlogN(for building) + QlogN^2(queries) . I think QlogN^2 can be improved to QlogN , this method is written here http://e-maxx.ru/algo/segment_tree in this part "Поиск наименьшего числа, больше либо равного заданного, в указанном отрезке. Ускорение с помощью техники "частичного каскадирования""

Thats my code http://pastebin.com/ATi5Uqjq

thank you very much :)

include

include

using namespace std;

struct treap{

int x, value, maxValue;

double y;

treap *l, *r;

treap(int x, int value): x(x), y(rand()), value(value), maxValue(value), l(NULL), r(NULL) {}

treap():l(NULL), r(NULL){}

void Recalc(){

    if (!this)
        return;

    this->maxValue = this->value;
    if (this->l && this->l->maxValue > this->maxValue)
        this->maxValue = this->l->maxValue;
    if (this->r && this->r->maxValue > this->maxValue)
        this->maxValue = this->r->maxValue;
}

};

void split(treap * t, int x, treap* &l, treap* &r){ if (!t){ l = NULL; r = NULL; return; }

if (t->x > x){
    r = t;

    split(r->l, x, l, r->l);
} else {
    l = t;
    split(l->r, x, l->r, r);
}
r->Recalc();
l->Recalc();

}

void merge(treap* l, treap* r, treap* &t){

if (!l || !r){
    t = !l ? r : l;
    return;
}

if (l->y > r->y){
    t = l;
    merge(l->r, r, l->r);
} else {
    t = r;
    merge(l, r->l, r->l);
}
t->Recalc();

}

int max(int x, int y, treap* t){

treap *l = new treap(), *m = new treap(), *r = new treap();
split(t, x — 1, l, r);
split(r, y, m, r);
int result = m->maxValue;
merge(l, m, l);
merge(m, r, t);
return result;

}

void insert(int x, int value, treap* &t){

if (!t){
    t = new treap(x, value);

    return;
}

treap *l = new treap(), *m = new treap(x, value), *r = new treap();
split(t, x, l, r);
merge(l, m, m);
merge(m, r, t);

}

int main() { srand((int)time(0)); treap* t = NULL; int n, m;

cin >> n >> m;

for (int i = 0; i < n; i++){
    int x, v;
    cin >> x >> v;
    insert(x, v, t);
}

for (int i = 0; i < m; i++){
    int x, y;
    cin >> x >> y;
    cout << max(x, y, t) << endl;
}

return 0;

}

this is full code.

I understood everything in this code , but I have question in the second code. what "this" means in void recalc() ?

this is the second example from Cartesian tree

struct treap{

int x, value, maxValue;

double y;

treap *l, *r;

treap(int x, int value): x(x), y(rand()), value(value), maxValue(value), l(NULL), r(NULL) {}


treap():l(NULL), r(NULL){}

void Recalc(){
    if (!this)
        return;

    this->maxValue = this->value;
    if (this->l && this->l->maxValue > this->maxValue)
        this->maxValue = this->l->maxValue;
    if (this->r && this->r->maxValue > this->maxValue)
        this->maxValue = this->r->maxValue;
}

};

Dynamic interval tree in 2D was on IOI 2013 .

yes, Dynamic interval tree is exactly what I want to write . I once wrote it with arrays in 1D , and now I want to write with pointers in 2D .

for example : struct vertex { vertex * l, * r; int sum;

vertex (int val)
    : l(NULL), r(NULL), sum(val)
{ }

vertex (vertex * l, vertex * r)
    : l(l), r(r), sum(0)
{
    if (l)  sum += l->sum;
    if (r)  sum += r->sum;
}

};

I cant understand after "struct vertex { vertex * l, * r; int sum; "

its a code at the end of this page http://e-maxx.ru/algo/segment_tree and also don't know what " new " function does in that code.

I said till now... I know that they have much stronger teams -_-

haha only georgian team has all members' ranks higher or equal to yellow

Team of Georgia :

svanidz1 Nikoloz Svanidze Bronze

jskhirtladze Jimmy Skhirtladze Bronze

guliashvili Giorgi Guliashvili No participation

TMandzu Tornike Mandzulashvili No medal

I participated in contest unofficially and my rating didn't update.

what about system test ?

"A little bonus: top 200 official Championship contestants will receive t-shirts!" why only official ? give top 200 contestants from both official and unofficial.

WRITE PROBLEM E TUTORIAL !!!

someone explain the solution of problem E please ;)

I expected more detailed tutorial ...

thanks

I have changed my handle last year ^_^

design not disaine :D

.

haha , I got it now ,nice way :)

How can we realise segment tree such , that we can count number of non-zero elements in LogN time , also we need to increase all elements by 1 on interval or decrease by 1 also in LogN time.

It will be nice if somebody will make Div 1 contest before the new year.

I bet you were thinking on a very hard way at first :)

In Problem E: lets save for each hole the answer , number of jumps after ball leaves this hole and the last hole for it. Then for each query we have answer in o(1) and for each update of strength we can look the hole which will be after this hole . ((new strength)+i) and rewrite its answer to this hole and increase the first answer (number of jumps ) by 1 and second answer (last hole) will be same. This is o(M) solution . Any mistake ?

You dont say :)

Same as you

Very unusual contest

looks like Div 1 system test exploded .

This can be done in o(N+M) time. You are always looking for sum on [r+1..n+1] so you can easyly change it in o(1) when you step to next i.Sum will decrease by cnt[i].and you will go to i+1.Looks like you will get LogN for binary search to transform V[i], K[i] into L[i],R[i].

Does it consists of sorting queries or you can get the answer for arbitrary query in o(logN) time ?

which data structure should we use to find the number of different strings on a segment in problem E?

REGISTERED!!!

all contestmakers are offline :(

we want to register , watching others writing contest isn't very attractive :))

I have the same problem.

Nice problem set.

why contest isn't rated for Div 1 ? will it be a bit easier ?

I hope problems will be as good as contest number :)

lol :D :D how did that code pass tests ?

Any idea how to solve problem D. Dispute ?

thanks :)

waiting for Boring Partition tutorial , its boring process :D

At first read the statement and then ask the questions.

thanks , i found out now . Firstly i thought flow was going from each string to the main source. :)

in problem E. Build String , we should write min cost flow algorithm , but what will be in the role of nodes ? From which node to which are we finding flow ?

Wow , very fast judging :D

Very slow judge :(

faster judge is good news :D

Its not very nice :D

I wonder what is the solution of E. Anybody write in short please.

Waiting for interesting and useful Contest.

I got report on my email about this round and there was writen that contest was held by rules of codeforces not dynamic scoring.

I had nearly same solution. Its one of the way of implementation of topological sort.

does it have another solution besides topological sort ?

thank you , its very good explanation.

when the Problem's Analysis will be placed ?

will the scoring be as usually or dynamic ?

Is the contest rated ?

good luck everybody