### GuralTOO's blog

By GuralTOO, history, 5 years ago, ,

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.

• +49

 » 5 years ago, # |   0 Bad luck for our people, it collides with our National Contest, I think I'll do problems later...
 » 5 years ago, # |   0 GuralToo GuralToo Guler yuzun mahriban!!!
 » 5 years ago, # | ← Rev. 2 →   +4 Time of it's starting time?
•  » » 5 years ago, # ^ |   +3 Exactly
 » 5 years ago, # |   +4 Do anyone here know some other IOI-oriented contests other than COCI and USACO ? thanks in advance !
•  » » 5 years ago, # ^ | ← Rev. 2 →   +8 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.
 » 5 years ago, # |   0 Can I participate online ?
•  » » 5 years ago, # ^ |   0 Sure
 » 5 years ago, # | ← Rev. 2 →   -11 22 hours left//
•  » » 5 years ago, # ^ |   0 tomorrow
 » 5 years ago, # |   0 Will we get full feedback for our submissions?
•  » » 5 years ago, # ^ |   +11 No. There was feedback for only samples at the last one I participate in :(
•  » » 5 years ago, # ^ |   0 YES!
 » 5 years ago, # |   +18 Is it only me who cannot open the contest page right now? And my solutions are being evaluated more than 10-20 minutes...
•  » » 5 years ago, # ^ |   +9 It's not just you.
 » 5 years ago, # |   +8 I submitted a solution more than 30 minutes ago and still nothing... Website is completely unavailable o:
 » 5 years ago, # |   0 I think contest will be canceled.
 » 5 years ago, # |   0 what are they gonna do with this contest?
 » 5 years ago, # |   +11 It s gonna be a pity if they will cancel the round. The problems seems to be very interesting. They should extend the time :)
•  » » 5 years ago, # ^ | ← Rev. 2 →   +1 But we have problems , what if most of us solves 4 or 5 or all problems in extended time.
 » 5 years ago, # | ← Rev. 2 →   +20 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.
 » 5 years ago, # | ← Rev. 2 →   +7 Now I get this: "You're not allowed to submit at this time."Any ideas how I can submit?UPD: Now I can submit :)
•  » » 5 years ago, # ^ |   0 best idea: wait until submitting is open , meanwhile solve other problems
 » 5 years ago, # |   -11 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.
•  » » 5 years ago, # ^ |   0 use maps as if they were normal arrays , it shouldn't make implementation much worse
•  » » » 5 years ago, # ^ |   0 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?)
•  » » » » 5 years ago, # ^ |   0 if you access not existed index, then it will simply create it and give it value 0
•  » » » » » 5 years ago, # ^ |   0 My computer says no — at least for pairs.
•  » » 5 years ago, # ^ |   0 same here ! i implemented the 25% solution instead of the whole one because i got bored manipulating maps !
 » 5 years ago, # |   +2 C and D were pretty nice! How to solve D? Please, tell me it's not some 2d tree :)
•  » » 5 years ago, # ^ |   0 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.
•  » » » 5 years ago, # ^ |   0 How to do F?
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 5 years ago, # ^ |   +3 I think you can xor current cell and move cell with same value.
•  » » » » » 5 years ago, # ^ |   0 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).
•  » » » 5 years ago, # ^ |   0 Thank you again for helping me, Xellos! :) Yet another attempt to overkill a task by me :D
 » 5 years ago, # |   0 1) How to solve F?2) What time do it usually take to get the results?
•  » » 5 years ago, # ^ |   +7 Due to earlier technical problems the results page will be available tomorrow. Many submissions are still in the judging queue and need to be evaluated.Again, sorry for the inconvenience.
•  » » » 5 years ago, # ^ |   0 The queue was emptied sooner than expected. Results are available now.
•  » » 5 years ago, # ^ |   +3 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 >_<
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 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
 » 5 years ago, # | ← Rev. 2 →   0 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 improvements
•  » » 5 years ago, # ^ |   0 I 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.
•  » » » 5 years ago, # ^ |   0 Oops I forgot that build run in O(n) time :P
 » 5 years ago, # | ← Rev. 2 →   0 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...
•  » » 5 years ago, # ^ |   0 Yes, it is possible to avoid division:http://ideone.com/nd4dDL
•  » » » 5 years ago, # ^ |   0 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. :PPS: Congratulations on a perfect score!
•  » » » » 5 years ago, # ^ |   0 How could you pass the samples if you were reading like a,b,a,b,a,b
•  » » » » » 5 years ago, # ^ |   +5 Well try the samples... they all work both ways somehow
•  » » » » » » 5 years ago, # ^ |   +2 I almost think they did this on purpose to teach us to read input specifications more carefully...
 » 5 years ago, # |   0 How long will remain the analysis mode ? Can i submit solutions after that ?
•  » » 5 years ago, # ^ |   0 Contest is now in the analysis mode, so you can continue submitting solutions.