Hey coders, I just want you to don't miss the first contest of this academic year from Croatia. COCI http://hsin.hr/coci/ . You can check the time of it's starting time here http://www.timeanddate.com/worldclock/fixedtime.html?day=17&month=10&year=2015&hour=14&min=0&sec=0&p1=0.

Bad luck for our people, it collides with our National Contest, I think I'll do problems later...

GuralToo GuralToo Guler yuzun mahriban!!!

Time of it's starting time?Exactly

Do anyone here know some other IOI-oriented contests other than COCI and USACO ? thanks in advance !

Being slightly partisan here, but DMOJ will be hosting monthly IOI-oriented contests called

DMOPCs. Also there exists the CEOI and BOI, etc. (google/yandex/baidu search is your friend). See this for a full list.Can I participate online ?

Sure

22 hours left//

tomorrow

Will we get full feedback for our submissions?

No. There was feedback for only samples at the last one I participate in :(

YES!

Is it only me who cannot open the contest page right now? And my solutions are being evaluated more than 10-20 minutes...

It's not just you.

I submitted a solution more than 30 minutes ago and still nothing... Website is completely unavailable o:

I think contest will be canceled.

what are they gonna do with this contest?

It s gonna be a pity if they will cancel the round. The problems seems to be very interesting. They should extend the time :)

But we have problems , what if most of us solves 4 or 5 or all problems in extended time.

why it should be canceled? it doesn't affect the fairness of the contests(unless the website is still unavailable until the end of time), since to there's no time penalty , and everyone should have downloaded all the problems since they are all in one pdf.

Now I get this: "You're not allowed to submit at this time."

Any ideas how I can submit?

UPD: Now I can submit :)

best idea: wait until submitting is open , meanwhile solve other problems

The third task is nice, the fourth is also good, but I can not understand why problemsetter put constrains for n,x <= 10^9. The idea is same as n,x <= 10^5, but now the implementation is boring. If it isn't fair with normal constrains, I am also unfair and I won't implement it.

use maps as if they were normal arrays , it shouldn't make implementation much worse

Oh, I wrote a bruteforce and found a mistake that wouldn't be there with smaller

N. (see: what does a map do when you access a non-existent element?)if you access not existed index, then it will simply create it and give it value 0

My computer says no — at least for pairs.

same here ! i implemented the 25% solution instead of the whole one because i got bored manipulating maps !

C and D were pretty nice! How to solve D? Please, tell me it's not some 2d tree :)

Nah. Notice that for a field to be attacked, the xor of its row and column must be different. It's just map juggling to maintain and update the xors of rows/columns, then you should store the number of rows and of columns with a given xor in another map and the answer is found as

N^{2}minus the number of fields which have equal xor of row and column. And again some map juggling to update those values efficiently.How to do F?

You were faster than me :)

The idea is pretty nice, and my idea for implementation wasn't very long, but for me it was boring. I wish to see some nice idea for update (moving figure). My idea was making some pairs and put it in the set (I am not 100% sure it can be done on that way). Honestly I am not expert for c++ coding and I suppose that exist something better.

I think you can xor current cell and move cell with same value.

Probably you didn't understand me or I don't understand you :)

The problem which I have is:

How to find value x which is located on cell (r, c) and after that move value to cell (r1, c1) ? I see that like array of pair (x, pair (r, c)). And I don't know how to say tell me x , for pair (r,c).

Thank you again for helping me, Xellos! :) Yet another attempt to overkill a task by me :D

1) How to solve F?

2) What time do it usually take to get the results?

F: notice that for each guy we can calculate his possible left and right bounds independently. Take a vertex

`x`

, sort it's children by V[i].Suppose that we want to find all the left bounds for

`x`

. In the beginning, the only left bound is V[x]. Iterate through the children from right to left, starting from the first child`i`

that has V[i] < V[x]. If a child has one of it's right bounds in the position of one of`x`

's left bounds minus 1, we can add all of this child's left bounds to`x`

's left bounds.Hope this isn't too unclear >_<

I'll try to explain in detail. subsequence=consecutive elements.

One observation is:a subsequence that is invited from subtree of x can be seen as leftpart+val[x]+rightpart. So you can do left and right subsequences independently. You can store left[x][i]=1 if you can invite from it's subtree some people with jokes from interval[i,val[x]], right[x][i]=1 for interval[val[x],i].

Now it comes the hard part.Let's solve left parts.If you imagine how a left part could be made out of smaller subsequences,and also that in every subsequences there is surely val[y](y a direct son),you should sort sons by val[y],and start your dynamic with sons from val[x]-1 to 1.

Why it is better than random?Because a son can help to make a left part if we already traversed sons with value > current.Just imagine what I said earlier,how a left part is composed of subsequences.

Now we fix a st[x][i] which ==0 and try to make it.This implies st[current_son][i]==1. Also we fix j (i<j<=val[x]) and if st[x][j]==1 and dr[curr_son][j-1]==1,we can make this left part with left end in i.To imagine it,we add subsequnce of curr_son made from i to j-1 with left part already done from j to val[x].

Complexity(N*VAL_MAX*VAL_MAX),but is better in practice.Memory O(N*VAL_MAX),and it can be stored as bool or bitset.

Right part is similar.Hope I helped:)

My solution for fifth problem TLEed on two tests , my complexity is

~~O(c^2 * (n+q) * log n)~~O(c^2*q*log n) is the intended solution has better complexity? this problem prevented me from getting full scoreUPD:it is the intended complexity my code got full score after some constant improvementsI have full score with almost the same complexity, except I build the segment tree in O(c^2 * n).

And another thing is that in each update I do MOD operation only c times, not c^2.

Oops I forgot that build run in O(n) time :P

On problem E can anyone explain their solution? I thought I had a full solution (in ) but apparently it's 0. Darn why can't we have some more feedback — I got WA on the first query of like every test except one which was WA on 11328th query... — OK errors were reading input in "column-major" rather than "row-major" (what kind of samples were those) and a couple missing mods...

Also, seriously why are A,B==0 (mod 10007) allowed? This added quite a bit of special stuff for division by 0, does anyone's solution not use modular division?

Also darn using an extra set in C TLEs a few tests — CF maxtests in pretests are really nice...

Yes, it is possible to avoid division:

http://ideone.com/nd4dDL

Okay cool I see, impose an ordering and put it on a segtree. Nicer than my approach for sure (but slower).

The other thing I see — input is given a,a,a,b,b,b not a,b,a,b,a,b?! This is why we need pretests... although looks like I have a couple modulo issues as well so not too much lost. :P

PS: Congratulations on a perfect score!

How could you pass the samples if you were reading like a,b,a,b,a,b

Well try the samples... they all work both ways somehow

I almost think they did this on purpose to teach us to read input specifications more carefully...

How long will remain the analysis mode ? Can i submit solutions after that ?