cgy4ever's blog

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

Topcoder SRM 713

Time: 9:00 pm EDT Wednesday, April 26, 2017

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

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

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

18 hours before this SRM.

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

Starts in 8 minutes!

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

I think admins should not count challenges of white accounts today.

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

How to solve hard? I've come up with per query but have no idea how to solve for all queries at once.

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

    Hint: Matrix * Matrix takes O(n^3), but Matrix * Vector only takes O(n^2). (Looks like al13n had the intended algorithm but unfortunately failed by overflow.)

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

life in codeforces: solve 3 problems, rank 500+ in div2; life in topcoder: solve 0 problems, rank 50+ in div1 :D

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

    TFW you solve 0 problems and still get +38 rating increase.

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

How to solve Div-2 B ???? :( :(

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

    I tried to solve like that:

    PowerEquationEasy

    But, for some reason it doesn't always work.

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

    Solution to the more general div 1 250: it can be seen from prime factorization that if a^b= c^d, then a= t^x and b= t^y for some t,x,y. Now you can just loop over all t and count the number of possibilities of (x,y). You don't need to consider because then x and y cannot be greater than 1.

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

Div1-250 was nice!

But a bit too hard for the Div1-Easy slot.

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

    Completely agree! I think that should have been scored as 300 but not 250!

    I honestly think that 250 scenario is: open and implement, the average score is about 200. Here we have only 3 coders with more than 200 points on it. And having that many people did not open 2nd (or open and had only 10 minutes to read and code it).

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

Count of the SRM time from the last 12 ones:

  • 9 PM: 6
  • 7 AM: 3
  • 11 AM: 2
  • 5:30 AM: 1

It would be nice if we can at least have have a more even distribution here.

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

    I did the math. I count 6 at 9PM and 6 at 5:30AM-11AM. Seems like a fair game to me.

    Or maybe you are right, it should be something like:

    • 7 PM: 2
    • 5 PM: 1
    • 10 PM: 3

    • 7 AM: 3
    • 11 AM: 2
    • 5:30 AM: 1

    Or you want less amount of contests in the first group?

    Topcoder is the only site that actually rotate the starting time to fit all time zones. Codeforces, Codechef, Hackerrank, Atcoder don't give a shit.

    And you know, there's some people living in the Americas and the 9 PM is good for them.

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

      In the past, it used to be splitted more evenly between 9PM, 7AM and 11AM. 9PM ones are usually those with least participants. I personally don't think it makes sense to shift more contests to 9PM and lose participation in result.

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

Can someone please explain solution for div 1 — 500, TIA.

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

    I'm not sure about my approach (couldn't get enough time to implement during contest), but some solutions looked like this:

    Start with bitmask dp, dp[1<<n][n] where dp[i][j] is the number of ways to traverse mask i, ending up (last traversal) at j.

    Recurrence relation should be dp[i][j]=sum(dp[i&(~(1<<j))][k] if k,j are set in i and it is possible to move from k to j. It is possible iff node x is visited (marked in i) only when complete subtree of x is visited or x lies on path from root to j.

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

    I got AC using the following approach. I use DP with state as (mask, current_vertex). I iterate over the next vertex nxt I will visit. If I do visit some particular vertex nxt, I will always return back to current_vertex only after ALL the vertices reachable from nxt, unvisited as of yet, get visited. So, for each pair (mask, current_vertex) I calculate the mask of all the unvisited-till-now vertices I will visit if I start at current_vertex (I store this in reachable[mask][v] in my code).

    So, I go from current_vertex to nxt, I add the product dp(mask|(1<<nxt), nxt)*dp(mask|reachable[mask|(1<<nxt)][nxt], current_vertex) to the answer. The first part of the product calculates the number of ways of dealing with nxt and the latter deals with the number of ways of dealing with the remaining unvisited neighbours of current_vertex.

    DP[mask][v] returns the number of permutations possible if I have already visited nodes denoted by mask and am currently at v.

    Code

    → Reply