cgy4ever's blog

Topcoder SRM 704
By cgy4ever, history, 8 years ago, In English

Topcoder SRM 704

Time: 7:00 am EST Thursday, December 29, 2016

Calendar: https://www.topcoder.com/community/events/

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

Comments Comments (60)
| Write comment?
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I cannot login to arena.topcoder.com and this is the only way I can compete.
Does anyone has the same problem?

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

Update: this round will start in 16 hours.

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

Topcoder have an unusual method of submission. It is very difficult use

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

    Just learn it, It will become the easiest service you will ever use for CP.

    Take a look: fusharblog.com/apps/testerdream/

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

      It will become the easiest service you will ever use for CP.

      or if you prefer

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

        That is why you topped coding round?

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

          Because I don't like TC Arena :P? I don't think disliking Arena was the most important factor xD.

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

Why we can't change handle in new year in topcoder ?. Admin of topcoder please enable this.

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

How to solve Div1 B?

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

    I think it's DP. dp[pos][gcd(current product, K)]. DP for n — 1 elements. The last element will be chosen!

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

      Could you please explain more on your approach? It seems to be very different from what I saw in solutions of various coders (mostly used CRT).

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

        K has at most ~ 1000 divisors. So total state is at most 50 * 1000. Assume gcd(a1 * a2 * ... * an - 1, K) = r. Then an will only depend on r and v.

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

What is the difference between D1 300 and AGC 5 problem C?

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

    Well here you have to actually provide tree, so it is harder?

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

      Harder? By returning string("yes/no") instead of tree itself? xD.

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

        I mean the other way around, here being the topcoder round, sorry for ambiguity :)

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

          no no no, i understood u, i meant for me these problems r equal and i think i would solve atcoders's problem the same way as todays toproder's problem.

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

Is there a problem with div2 medium because all solutions in my room failed system test ?

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

How to solve Div2 C ???

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

    I had an idea using inclusion-exclusion as the number of divisors of numbers uptil 100 would be very small. Didn't have enough time to code it up.

    Is there an alternate solution?

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

      Didn't try this but i think this might work .

      DP[i][j] — number of sequences of length i whose product mod k is j .

      can be computed using matrix exponentiation i think .

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

    Here, your biggest hint is that n is very big and k is small. Keep an answer array of k values, the number of ways you can form 0, 1 2, etc so far (mod k). Now, to compute it for a certain n, you find the matrix you need to multiply it by to transform n to n + 1 (actually, you need to construct this matrix in your program since it depends on k), and exponentiate this matrix and multiply it by the initial answer array(should be just 1's). It's O(k3 log n)

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

How to solve div2. C?

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

So there was an issue with div1 systest also? i was 110th after 1 systest, but after resystest i became 100th.

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

    That's because people who failed systests have their score wrong(see negative scores). I went from 82nd to 73rd :D

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

    That's because people who failed systest get negative score instead of zero ;)

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

I can't join SRM because I'm busy in today, but it seem that I lost big chance to up my rating. (I'm writer of AGC005, and actually Problem C is constructing problem first, so I have source code to constructing ... XD)

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

Is it rated?

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

Actually D1 300 is completely the same as problem D of NEERC Western 2014 (except data range is 50 instead of 100000.)

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

When I try to log in at arena.topcoder.com, I am redirected to topcoder.com/my-dashboard, which redirects me back to arena.topcoder.com :D This circular dependency is not allowing me to login :(

Is any one else facing the same issue?

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

    Login into topcoder.com first. Then hit arena.topcoder.com

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

      I can't login to topcoder.com. It has the same issue.

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

        I use google login. No issue for me.

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

          I mean, I can't even see the main page.

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

            Erase the cookies from topcoder

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

              Doesn't help for chrome, but managed to get inside with internet explorer.
              If they are reading comments here, I'll leave the detailed

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

How to solve Div1 500?

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

    http://mirror.codeforces.com/blog/entry/48850?#comment-333916. It passed.

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

    Let K = p1e1... pses. The answer to the problem is just the product of answers to the prime factors (CRT) so WLOG K = pe.

    Observation: if and . then answer for v = x and v = y is exactly the same.

    So we just want to compute how many n-tuples has product divisible by exactly pf.

    Consider the polynomial W(x) = (pe - pe - 1)x0 + (pe - 1 - pe - 2)x1 + ... + (p - 1)xe - 1 + xe.

    i.e. coefficient at k-th power of x is number of remainders from [0, pe) which are divisible exactly by pk.

    Now what we want is just more or less W(x)n, (powers greater than x^e should be replaced by x^e). Now if and pf + 1 doesn't, the answer is f-th coefficient of W(x)n divided by (pe - f - pe - f - 1).

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

       Can you clarify a bit more: for instance, K = p1*p2, how do we combine solutions a1*a2*...*an = v mod p1 and b1*b2*...*bn = v mod p2 to get solution for K?

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

      Actually, (following the notation,) when f < e, the answer is

      which finishes all cases v ≠ 0. The case v = 0 can be then computed.

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

How to solve Div1 300?

https://en.wikipedia.org/wiki/Centered_tree says a tree is either centered or bicentered (with adjacent centers)

Besides that, all I can think of is a brute force approach. When we need to place a node of eccentricity e, try all possibilities of nodes of e-1 and place the node where it does not affect the eccentricity of already placed nodes.

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

    You have the center, it is the node/nodes of minimum eccentricity (there can be only 2 centers at most). Now about the ones that have eccentricity higher you can note a couple of things:

    1. They always come in frequencies of 2 or more. Why is this? Think about the point where the excentricity is max. There's a path that's the maximum path and it obviously ends in a leaf so you can note that this leaf also has maximum eccentricity. For the ones in the middle of the path you can think the same way, just note that the maximum length path goes through the center.

    2. A point closer to the center has lower eccentricity.

    Now to construct the graph just order the input, if there are 2 centers you connect them and connect the vertices to some vertex that has a immediatelly inferior eccentricity making sure that there are at least 2 branches while checking if there's a number with freq<=1 (that means it is impossible). Check if this is a real answer (the numbers could be higher than possible for example) and it's done.

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

There seems to be still some issues on the results. Result

According to this result, everyone doesn't get decreased on their total scores, even if they got Failed System Test. Also I can guess rating is calculated by this wrong result. (See 40th place filip.bartek. His total score should be -25pts overall, but his rating is increased by 290.)

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

    You are right, I was wondering how my rating went down, and this somewhat explains it, failed submissions are apparently as good as correct ones these days! If I had known I would have submitted the 500 and 900 for max points and had my rating go through the roof!

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

    Yes, we are looking into it.

    Sorry for the issue, it was caused by my mistake (there is a bug in checkData() for Div2-Medium, so someone submitted an invalid test case in challenge phase.)

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

    This should now be corrected, just waiting on cache to expire so it shows up properly online :)

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

Some people still have got points for their submission after system test fail and hence rating increase. :3

→ Reply