cgy4ever's blog

By cgy4ever, history, 3 years ago, , Topcoder SRM 713 Comments (23)
 » 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.
 » 2 years ago, # | ← Rev. 2 →   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 ???? :( :(
•  » » 2 years ago, # ^ | ← Rev. 2 →   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.
•  » » » 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 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
 » 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: 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.
•  » » 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.
•  » » » 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.
•  » » » » Vietnam 2 : America 0
 » 2 years ago, # | ← Rev. 2 →   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<
•  » » 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<