cgy4ever's blog

By cgy4ever, history, 3 years ago, In English,

Hello there,

TCO2016 Online Wildcard round will start at 12:00 noon on Sept 10 EDT:

  • If you got top 10 in one of the 4 onsite regionals (and you haven't advanced to TCO onsite finals yet), then this is your last chance — top 2 will advance to onsite finals!
  • For other people, you can participate in the parallel round, it will be rated. This is open for both division, but the difficulty will be at least as hard as Div1 in SRM.

Welcome to participate and hope you can enjoy it!

Update: TooDifficuIt and tourist are top 2 and will advance to onsite finals, congratulations!

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

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

What is the method to solve 500 of the parallel round?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    We use the same tasks in both rounds, so it is also 500 in Wildcard round.

    For the number of nodes n (1 <= n <= 16) and a mask that is between 0 and 2^n-1, we can construct a graph: for i, if the i-th bit of mask is 1, then we connect node i to node 1,2,...,i-1.

    Then the number of connected subgraph in it will be very close to mask: the difference between them will be less than 16. We have 4 more nodes, use them to fix this difference.

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

      I'm having some difficulty understanding this solution. Could you please explain in a bit more detail?

      For the number of nodes n (1 <= n <= 16) and a mask that is between 0 and 2^n-1, we can construct a graph: for i, if the i-th bit of mask is 1, then we connect node i to node 1,2,...,i-1.
      How do we calculate the number of connected subgraphs for the graph constructed according to a particular mask?

      the difference between them will be less than 16.
      Why is this true?

»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

I think the hard problem is much more easier than the medium one. T_T

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I tried both and medium was much easier for me. I didn't even know how to find the square root modulo in hard, while in medium I immediately know how to move towards the solution.

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

      I understand that hard can be harder for some people, but the thing is some pregained knowledge can make hard significantly easier, while it is not the case for medium (I think I haven't seen k-th root previously, but tricks with generators were no black magic for me).

      At least I would move distribution towards 300-600-900 rather than sticking to regular one.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      I didn't even know how to find the square root modulo in hard

      What would you even need that for? (That was what I thought about first, but since sqrt doesn't solve odd k, I scrapped it and tried primitive roots next. It worked. I also find 1000 about as easy as 500.)

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

        That was not meant to be "I wasn't even able to figure out the first required step", but "I wasn't even able to solve an easier problem".

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

    Yes, Hard looks overwhelming but the solution itself is pretty simple. Somehow most people opened Medium instead of Hard, so at least it is a fair game.

    Btw, congratulations!

»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Got TLE on hard, added "unordered_" and it passed in practice room ;__;. Missed such a chance of defeating all guys in official round :(.

Btw, TopCoder achieves a new level of quality in number of participants :P.

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

    Regarding the number of participants — this is what they get for naming a round "fun round".

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

      What? Do you think that 100 people wanted to participate, entered arena, looked that it is called "fun round" and decided not to participate? I think it is the cause of very bad distribution of information. This blog was the only source I learned about that from.

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

        Those who had read about the round from this blog and wanted to participate did participate. Those who entered the arena from some reason and saw "Wildcard round" and "Fun round" — not necessarily.

        Even though I told Stonefeang about the round, he answered me that he can't register because it says "invitation only". He tried "Wildcard round" of course. I understand perfectly not checking "Fun round" because it doesn't look like a rated contest, does it?

        In your post I would change "decided not to participate" to "did not think about participating".

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

    Hmm, there were some issues about the announcement process. It should be included in the Newsletter. I found it too late and only managed to post it less than 1 day before it.

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

      Still, those newsletters suck hard, you have to admit it. Can't there be separate e-mails only about algo competitions?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In 250 point problem, lot of solutions choose 25 as the number of items to check when there are 1000 items in the array. Can someone please explain