chrome's blog

TopCoder SRM 626
By chrome, 10 years ago, translation, In English

Hello, everyone!

Tomorrow will take place TopCoder SRM 626. Don't miss!

GL & HF

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

Comments Comments (17)
| Write comment?
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Thanks, seems like I'm going for my first SRM ever :)

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

It conflicts with Codingame challenge

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

    Also with first 1/8 fifa game [Brazil — Chile] Sad. hadn't decide which one I will choose.

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

Can someone explain why in 500 we get a huge negative score in example 1 using a self loop from a final vertex (vertex 1), but in example 3 we are not allowed to go back and forth between vertices 1 and 2 to get a huge negative score?

Thanks!

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

How was Div2 1000 problem to be solved?

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

My fail on 900 this time was quite unusual: the whole problem can be siplified to counting sum of squares of integers coprime to and (the answer's that times a2 + b2), but for some mysterious reason, I decided to count the sum of squares of non-divisors. Not to mention I didn't notice that and though that I'm only failing on the last sample due to some hidden overflow, because what else could cause me to pass the other large sample? (Of course, it's the fact that is a power of 2 in all samples except the last one and the one where the answer's trivially 0.) Boop.

In the end, this reduction's easily solvable by Google Search Algorithm...

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

For problem 250 div 2 I have solved it with a really fast algorithm but it's status is "challenge succeeded" . I don't know what it means ?

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

    Your solution may have passed the given test cases, but it was not correct.

    The person who hacked(challenged) your solution found a test case, where your algo gave the wrong output

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

How was Div1 600 problem solved?

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

    dp[a][b][c] — answer for way from a to b with c charges.

    1. if c==0 then answer is shortest path (floyd helps)

    2. if c is even then for some vertex i answer is dp[a][i][c/2]+dp[i][b][c/2]. for all such i we take best.

    3. if c is odd then instead of vertex we choose edge (i,j) and answer is dp[a][i][c/2] + dp[j][b][c/2] — weight(i,j).

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

      c charges will be between 0 and 1,000,000,000, inclusive so how can it be the third dimension ??

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

        look carefully: charges always divided by 2, so total number of states is O(n2log(Charges))

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

          Got it.Thnxz.

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

          I can't get the point of (even & odd) how & why it work ?
          thanks

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

            Think about the shortest path from u to v with c charges (c is even). Since you do charges one by one, there will unequivocably be a middle node m such that you do c / 2 charges from u to m and c / 2 charges from m to v. That's why the DP works.

            → Reply