COCI - Codeforces

9 лет назад, # ^ |

Exactly

→ Ответить

baal-hammon

9 лет назад, # |

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

→ Ответить

maximaxi

9 лет назад, # ^ |

← Rev. 2 →

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.

→ Ответить

Silver_

9 лет назад, # |

Can I participate online ?

→ Ответить

9 лет назад, # ^ |

Sure

→ Ответить

9 лет назад, # |

← Rev. 2 →

-11

22 hours left//

→ Ответить

9 лет назад, # ^ |

tomorrow

→ Ответить

tweety

9 лет назад, # |

Will we get full feedback for our submissions?

→ Ответить

Bugday

9 лет назад, # ^ |

+11

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

→ Ответить

9 лет назад, # |

+18

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

→ Ответить

FatalEagle

9 лет назад, # ^ |

It's not just you.

→ Ответить

carlotheboss

9 лет назад, # |

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

→ Ответить

Infused

9 лет назад, # |

what are they gonna do with this contest?

→ Ответить

Mast3rmind

9 лет назад, # |

+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 :)

→ Ответить

Infused

9 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

9 лет назад, # |

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

→ Ответить

9 лет назад, # |

← Rev. 2 →

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

Any ideas how I can submit?

UPD: Now I can submit :)

→ Ответить

9 лет назад, # ^ |

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

→ Ответить

allllekssssa

9 лет назад, # |

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

→ Ответить

9 лет назад, # ^ |

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

→ Ответить

Xellos

9 лет назад, # ^ |

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

→ Ответить

9 лет назад, # ^ |

if you access not existed index, then it will simply create it and give it value 0

→ Ответить

Xellos

9 лет назад, # ^ |

My computer says no — at least for pairs.

→ Ответить

baal-hammon

9 лет назад, # ^ |

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

→ Ответить

9 лет назад, # |

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

→ Ответить

Xellos

9 лет назад, # ^ |

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² minus the number of fields which have equal xor of row and column. And again some map juggling to update those values efficiently.

→ Ответить

animeshf

9 лет назад, # ^ |

How to do F?

→ Ответить

allllekssssa

9 лет назад, # ^ |

← Rev. 2 →

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.

→ Ответить

kalimm

9 лет назад, # ^ |

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

→ Ответить

allllekssssa

9 лет назад, # ^ |

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

→ Ответить

9 лет назад, # ^ |

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

→ Ответить

vintage_Vlad_Makeev

9 лет назад, # |

1) How to solve F?

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

→ Ответить

9 лет назад, # ^ |

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.

→ Ответить

9 лет назад, # ^ |

The queue was emptied sooner than expected. Results are available now.

→ Ответить

HellKitsune

9 лет назад, # ^ |

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 >_<

→ Ответить

Archazey

9 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

9 лет назад, # |

← Rev. 2 →

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 score

UPD: it is the intended complexity my code got full score after some constant improvements

→ Ответить

HellKitsune

9 лет назад, # ^ |

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.

→ Ответить