GuralTOO's blog

COCI
By GuralTOO, history, 9 years ago, In English

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.

  • Vote: I like it
  • +49
  • Vote: I do not like it

Comments Comments (50)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

GuralTOO GuralTOO Guler yuzun mahriban!!!

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

Time of it's starting time?

→ Reply
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can I participate online ?

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it -11 Vote: I do not like it

22 hours left//

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will we get full feedback for our submissions?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what are they gonna do with this contest?

→ Reply
»
9 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it

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.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

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

Any ideas how I can submit?

UPD: Now I can submit :)

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
  Vote: I like it -11 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          My computer says no — at least for pairs.

          → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How to do F?

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

1) How to solve F?

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, it is possible to avoid division:

    http://ideone.com/nd4dDL

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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!

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it +2 Vote: I do not like it

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

            → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Contest is now in the analysis mode, so you can continue submitting solutions.
    → Reply