Topcoder SRM 713

# | User | Rating |
---|---|---|

1 | tourist | 3870 |

2 | Benq | 3618 |

3 | Miracle03 | 3453 |

4 | peehs_moorhsum | 3430 |

5 | Radewoosh | 3418 |

6 | Petr | 3408 |

7 | maroonrk | 3387 |

8 | sunset | 3338 |

9 | ko_osaga | 3334 |

9 | jiangly | 3334 |

# | User | Contrib. |
---|---|---|

1 | YouKn0wWho | 214 |

2 | 1-gon | 203 |

3 | Um_nik | 195 |

4 | Errichto | 182 |

5 | awoo | 180 |

6 | sus | 176 |

6 | tourist | 176 |

8 | antontrygubO_o | 172 |

9 | -is-this-fft- | 169 |

10 | maroonrk | 168 |

Topcoder SRM 713

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/03/2021 09:48:16 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

18 hours before this SRM.

1 hour before the contesst.

Starts in 8 minutes!

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

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

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

Oh, so simple. Nice.

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

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

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

I tried to solve like that:

PowerEquationEasyBut, for some reason it doesn't

alwayswork.Someone help on this one. Courtesy — Div II noobs.

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.

My solution is much more simpler and compact

My idea is , we should find number of solutions for a^b = c^d (1<=a,b,c,d<=n) a can be written as i^x and c can be represented as i^y (bases are common i.e i) So, (i^x)^b = (i^y)^d ----- (1) we can write i^(xb) = i^(yd) so we need to solve xb = yd i.e x/y = d/b Our problem boils down to finding number of solutions such that x/y = d/b where b <= n and d<=n AND i^x <= n and i^y <= n (since i^x=a and i^y=c from eq (1)) It's easy to see that , since i^x <= n and n is atmax 100000, x can'be greater than 20 (2^20 == 1000000). Same for y. y<=20. So, we can easily iterate through all the possible x/y ratios (only reduced fractions such that gcd(x,y)=1) Once you have an x/y ratio, we can find the maximum allowed value, mallow for i i.e (n^(1/x) (since i^x<=n)) or n^(1/y) whichever is lower. i.e we can have 'mallow' possible values for base i such that i^x<=n and i^y<=n. Now, we know the x/y ratio. We can find number of possible values of c and d such that x/y = c/d. It is simply n/max(x,y). Our answer will be sum of mallow*n/max(x,y) for all possible reduced fractions x/y

Div1-250 was nice!

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

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

Count of the SRM time from the last 12 ones:

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

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:

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.

In the past, it

used to besplitted 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.Vietnam 2 : America 0

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

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.

I got AC using the following approach. I use DP with state as (mask, current_vertex). I iterate over the next vertex

nxtI will visit. If I do visit some particular vertexnxt, I will always return back tocurrent_vertexonly after ALL the vertices reachable fromnxt, 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 atcurrent_vertex(I store this inreachable[mask][v]in my code).So, I go from

current_vertextonxt, 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 withnxtand the latter deals with the number of ways of dealing with the remaining unvisited neighbours ofcurrent_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