### cgy4ever's blog

By cgy4ever, history, 5 years ago,

Topcoder SRM 713

• +46

 » 5 years ago, # |   +5 18 hours before this SRM.
•  » » 5 years ago, # ^ |   +8 1 hour before the contesst.
 » 5 years ago, # |   -10 Starts in 8 minutes!
 » 5 years ago, # |   0 I think admins should not count challenges of white accounts today.
 » 5 years ago, # |   +8 How to solve hard? I've come up with per query but have no idea how to solve for all queries at once.
•  » » 5 years ago, # ^ |   +40 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.)
•  » » » 5 years ago, # ^ |   0 Oh, so simple. Nice.
 » 5 years ago, # | ← Rev. 2 →   +25 life in codeforces: solve 3 problems, rank 500+ in div2; life in topcoder: solve 0 problems, rank 50+ in div1 :D
•  » » 5 years ago, # ^ |   +1 TFW you solve 0 problems and still get +38 rating increase.
 » 5 years ago, # |   0 How to solve Div-2 B ???? :( :(
•  » » 5 years ago, # ^ | ← Rev. 2 →   -17 I tried to solve like that: PowerEquationEasyint PowerEquationEasy::count(int n) { for (int m = 2; m * m <= n; m++) root[m * m] = m; long long total_cnt = n * n; for (int m = n; m >= 2; m--) { cnt[m] += n; cnt[root[m]] += cnt[m]; total_cnt += cnt[m]; cnt[root[m]] %= mod; total_cnt %= mod; } return total_cnt % mod; } But, for some reason it doesn't always work.
•  » » » 5 years ago, # ^ |   0 Someone help on this one. Courtesy — Div II noobs.
•  » » 5 years ago, # ^ |   +3 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.
•  » » 4 years ago, # ^ |   0 My solution is much more simpler and compact public static int count(int n){ long ans = (1l*n*n); for(int i=1;i<=20;i++){ for(int j=1;j<=20;j++){ int g = gcd(i,j); if(g!=1){ continue; } int max = Math.max(i,j); long lcount = ((long)Math.pow(n, 1.0/(max*1.0))+MOD-1)%MOD; long rcount = (long) (1l*n/max)%MOD; ans = (ans + (1l*lcount*rcount)%MOD)%MOD; } } return (int)ans; }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
 » 5 years ago, # |   +32 Div1-250 was nice!But a bit too hard for the Div1-Easy slot.
•  » » 5 years ago, # ^ |   +18 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).
 » 5 years ago, # |   +22 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.
•  » » 5 years ago, # ^ |   0 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.
•  » » » 5 years ago, # ^ |   +36 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.
•  » » » » 5 years ago, # ^ |   +15 Vietnam 2 : America 0
 » 5 years ago, # | ← Rev. 2 →   +19 Can someone please explain solution for div 1 — 500, TIA.
•  » » 5 years ago, # ^ |   0 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<
•  » » 5 years ago, # ^ |   +16 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<