### Med0b1011's blog

By Med0b1011, history, 11 months ago, ,

Topcoder SRM 723 starts tomorrow.

https://www.timeanddate.com/worldclock/fixedtime.html?msg=Topcoder%20SRM%20723&iso=20171118T1700&ah=2&am=0

I only created this blog because cgy4ever stopped doing them. I always disliked knowing about SRMs before they start by like 1-2 hours so thought I'd post about it a day in advance. ( If there is someone from TC that prefers to post these kind of blogs, I will happily delete this).

•
• +96
•

 » 11 months ago, # |   +3 Can you please tell how you use Topcoder arena. Do you use any plugins for C++(and other system settins). I find it really weird to use Topcoder. Thanks in advance.
•  » » 11 months ago, # ^ | ← Rev. 2 →   +6 First option: Use web arena https://arena.topcoder.com . Second option: Download applet from https://www.topcoder.com/community/competitive-programming/ . After that, watch some first part (~10:00 or ~15:00?) of this youtube video https://www.youtube.com/watch?v=A5vnkkFGOo0 .
•  » » » 11 months ago, # ^ |   0 Does applet work better. I find web arena quite slow.
•  » » » » 11 months ago, # ^ |   +6 Yes the applet works much better for me. The Practice section on Arena keeps on Logging Off and telling me to Log In again even on a very good connection. I faced no problems of the kind on the Applet.
•  » » » 11 months ago, # ^ |   0 I am using Kawigi Edit.I faced a problem if I have global array. Expected is that it should reinitialise to zero for every testcase automatically but it uses the array which was left over by previous testcase. How to get the expected work done ??Apart for getting class and stuff written ,does kawigi do anything better
•  » » 11 months ago, # ^ |   +1 This link was shared by one of our seniors to begin with topcoder, I think it may help you. And I personally use KawigiEdit as plugin for c++. Download it from here
 » 11 months ago, # |   0 How do you keep track of the upcoming SRMS?
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 Use clist.by.You can further signup and customize the list to see contests of particular websites only !
 » 11 months ago, # |   0 REMINDER: The contest starts in 30 mins. Let's participate and enjoy!
 » 11 months ago, # |   0 First time when I was about to solve the Hard problem and made the code work 4 minutes after the end...Anyway, the only reason for which I was able to solve it was because it was given before in some IOI. How to solve medium?
 » 11 months ago, # | ← Rev. 2 →   +22 Medium: Write bruteforceHard: Problem taken from IOI (IOI 2012 — City) with additional tediousnessThis was not the most glorious SRM problemset.
 » 11 months ago, # | ← Rev. 2 →   +11 How to solve Div2B(500 — point problem) (TopXorer Problem)?
•  » » 11 months ago, # ^ | ← Rev. 6 →   +2 You are solving for a, b, c , let it be ans(a, b, c)[assume a >  = b >  = c]. Let the highest power of 2 <  = a be 2x. We know that xth bit will be set in your answer no matter what. And number of bits in your answer will be x + 1.case 1: If 2x  <  = b, We can always make 2x + 1 - 1 , and this is your answer, a = 2x, b = 2x - 1, c = 0.case 2: Elseans(a, b, c) = 2x|ans(a - 2x, b, c).
•  » » » 11 months ago, # ^ |   0 Amazing Solution! Thanks for the reply.
•  » » » 11 months ago, # ^ |   0 Thanks for a clear solution.
•  » » 11 months ago, # ^ |   0 Hints: lets s="00" is a bit sequence. since s[0] is '0' i can't take s[1] as '1'. again lets s="10". here we can take s[1] as '1' by considering s[0]='0'.
•  » » 11 months ago, # ^ |   0 I think it was an overkill, but, I wrote a DP solution for this problem: https://pastebin.com/BYknMGXH during the contest. It should be self-explanatory.
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 A single loop over the bit positions of the binary representations of A, B, C starting from 30 (the maximum possible in a positive integer) and down to 0. Let i be the current bit position, we want every bit position to be 1 after the XOR operation if possible to get the maximum result. We can count the number of 1s in the ith position in A, B, C. There are 3 casescase 1: number of 1s at position i = 0 We can't get a one in that position in the resultcase 2: number of 1s at position i = 1 We simply get a one in that position in the resultcase 3: number of 1s at position i = 2 or 3 In that case we can "sacrifice" (clear) one 1 (in the case of 2) or two 1s (in the case of 3) from any of A, B or C and still get a one in that position in the result because the number of ones will be odd for XOR, and after that position it is possible to get all 1s, so you can just end the loop here and set all the 1s after this position in the result to 1. The reason is once you clear a 1, any combination of 0s and 1s is possible to get after it because they all form a smaller number which is within the interval, so you'll form the combination that gets the maximum possible result
 » 11 months ago, # | ← Rev. 4 →   +1 For Div1 500, I have came up with O(m6) solution if m = n / 7. Keep track (cb, cu, cf, ca, cl, co) by DP and maintain m ≥ cb ≥ cu ≥ cf / 2 ≥ ca ≥ cl ≥ co. For max test case (n = 100 with all '?') it only took 15ms. I think this problem was some new ideas for me (so it was good for me), but I want to ask why the writer did not set the constraints to n = 150 and make problem more better. UPD: For Swistakk's reply, because I thought O(m7) seems kind of "obvious" (because some kind of obvious dp divided by 2something?). But for O(m6) it was focused on "how to combine one 'f' from 2 'f''s." I took over 20 minutes to find out this. UPD 2: Now I've noticed that these are solution and solution. So both running time is almost equal.
•  » » 11 months ago, # ^ |   0 In what sense that would be a better problem? What do we want to achieve by raising constraints?
•  » » » 11 months ago, # ^ |   +6 I think the 500 is a reasonable problem as is...To me, the observation that a brute force DP is not 100^6 but much smaller is pretty reasonable (even if it's simple).
 » 11 months ago, # |   +3 why brute force in div2 medium doesn't time out? for example solution by m.subkhankulov
•  » » 11 months ago, # ^ |   0 Most of the solutions (including mine) append a character to the longest "buffalo". This means the array of "completed prefixes" is non-decreasing. The number of states is a lot less than 8^14 (it can be proven as being the number of increasing arrays of size 14 and sum <= 100). On input equal to all '?'s (7 * 14 of them, to be exact), the number of states checked is ~65k.
•  » » » 11 months ago, # ^ |   0 I was talking about div2 :) ... so the loop with 10^9 iterations can be used... ok... why not use higher constaints so that it would time out.
 » 11 months ago, # | ← Rev. 4 →   0 Maybe it is silly, but problems with defining 6-dimensional array costed me medium. I have the following code: int used[15][15][29][15][15][15]; int dp[15][15][29][15][15][15]; int f(int b, int u, int f, int a, int l, int o, int ind, int cnt, string &s) { if (used[b][u][f][a][l][o]) return dp[b][u][f][a][l][o]; used[b][u][f][a][l][o] = 1; } I get the following error:BuffaloBuffaloBuffalo.cpp:21:2: error: 'used' does not name a type used[b][u][f][a][l][o] = 1;Does someone have an idea why it does not compile?
•  » » 11 months ago, # ^ |   +23 function name = variable name = f?
•  » » » 11 months ago, # ^ |   +8 OMG Thank you!
•  » » » 11 months ago, # ^ | ← Rev. 2 →   +8 UPD: fixed, the problem was with parentheses.
•  » » » 11 months ago, # ^ | ← Rev. 2 →   +5 UPD: fixed, the problem was with parentheses.
 » 11 months ago, # |   +3 Can anyone explain the solution idea of Div 2 1000(C) of this contest?
 » 11 months ago, # |   +70 My solution to the hard problem:Consider cutting the polygon into halves with a vertical or horizontal segment. If one part is of size a, and the other one is or size b, then a × b pairs will have to pass this segment. Therefore, we just need to find all possible cuts and sum their contributions up.Let's do vertical and horizontal segments separately. Suppose we want to do vertical ones. A given vertical line(not segment) can intersect the polygon multiple times, and each of them corresponds to a cut. Since many "adjacent" vertical lines intersect the polygon in similar positions, we can partition the x-axis into at most O(n) parts so that contributions in each part are a quadratic function of the x-coordinate. Thus we can calculate the total contributions easily.Too bad I had some bugs during the contest...... :(
•  » » 11 months ago, # ^ |   +5 After contest I found some funny idea how to omit possibility of making a lot of bugs here. Probably for every x1 so that there is a vertical line (x1,y1)-(x1,y2) you cut this polygon using this line and calculated what part is on left and what is on right etc. But since this infinite line coincides with side it makes it somehow troublesome. But if we stretch polygon 3 times and ask about cutting it with lines x=3*x1+1 and x=3*x1+2 we never coincide with any vertical line and get all needed information :). I hope overflows are not becoming a problem after this xD.
•  » » » 11 months ago, # ^ |   0 Wow...That's ingenious
 » 11 months ago, # |   +7 Someone please explain how to solve Div 2 1000. This was the only solution accepted in the contest.
•  » » 11 months ago, # ^ | ← Rev. 2 →   +7 The solution is simple that can write in one line. The answer mod 1000000007 equals to 666666691x5 - 333333332x3 mod 1000000007. How can we get the answer polynomial? I'll explain the way of solving. 1. There are O(n2) number of vertices, so there are O(n4) pair of vertices. Distance for each pair is at most O(n) so you can guess that the answer can be a polynomial with degree equals to 5. 2. Now you have to calculate the polynomial. If you can calculate for the six different n (0 ≤ n < 1000000007), you can get the polynomial. So how to get value for six n's? Of course, "writing naive solution + getting answer for n = 0, 1, 2, 3, 4, 5" is enough. 3. Do interpolation. Using Newton's polynomial interpolation with modulo 1000000007 is a good way to do it. Then, you get 666666691x5 - 333333332x3. This is the final answer. Code: How we got the answer polynomial#include #include #include using namespace std; long long solve(int n) { vector x, y; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { x.push_back(i); y.push_back(j + n); x.push_back(i + n); y.push_back(j); x.push_back(i + n); y.push_back(j + n); x.push_back(i + n); y.push_back(j + 2 * n); x.push_back(i + 2 * n); y.push_back(j + n); } } int V = x.size(); vector > d(V, vector(V, 1012345678)); for (int i = 0; i < V; i++) { for (int j = i + 1; j < V; j++) { if (abs(x[i] - x[j]) + abs(y[i] - y[j]) == 1) { d[i][j] = 1; d[j][i] = 1; } } } for (int i = 0; i < V; i++) d[i][i] = 0; for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { for (int k = 0; k < V; k++) { d[j][k] = min(d[j][k], d[j][i] + d[i][k]); } } } long long ret = 0; for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { ret += d[i][j]; } } return ret / 2; } vector interpolation(vector x, int m) { int n = x.size() - 1; vector inv(n + 1); inv[1] = 1; for (int i = 2; i <= n; i++) inv[i] = 1LL * inv[m % i] * (m - m / i) % m; vector > dp(n + 1, vector(n + 2)); for (int i = 0; i <= n; i++) dp[i][i + 1] = x[i]; for (int i = 2; i <= n + 1; i++) { for (int r = i; r <= n + 1; r++) { int l = r - i; dp[l][r] = 1LL * (dp[l + 1][r] - dp[l][r - 1] + m) * inv[i - 1] % m; } } vector ret(n + 1); ret[0] = x[0]; vector mul({ 1 }); for (int i = 0; i < n; i++) { vector mul2(i + 2, 0); for (int j = 0; j <= i; j++) mul2[j + 1] = mul[j]; for (int j = 0; j <= i; j++) mul2[j] = (mul2[j] + 1LL * (m - i) * mul[j]) % m; mul = mul2; for (int j = 0; j <= i + 1; j++) ret[j] = (ret[j] + 1LL * mul[j] * dp[0][i + 2]) % m; } return ret; } int main() { vector v; for (int i = 0; i <= 5; i++) { int res = solve(i); cout << i << ' ' << solve(i) << endl; v.push_back(res); } vector ret = interpolation(v, 1000000007); for (int i = 0; i < 6; i++) { if (i >= 1) cout << " + "; cout << ret[i] << "x^" << i; } return 0; } 
•  » » » 11 months ago, # ^ |   0 Thanks for the response :)