### cgy4ever's blog

By cgy4ever, history, 3 years ago, ,

Topcoder Open is back! The first round will be 1A:

As usual top 250 active coder will advance to Round 2 directly. We will announce the list of coder a bit later, at this time you can check this blog: https://www.topcoder.com/blog/next-algorithm-track-automatic-berths/

You can find rules this year with the schedule here: https://tco17.topcoder.com/algorithm/rules/

Update: Byes are announced here (cut-off rating is 1783): https://tco17.topcoder.com/algorithm/byes/

• +80

 » 3 years ago, # |   0 cgy4ever I think top 750 will advance to R2 (not 250)
•  » » 3 years ago, # ^ |   0 It is not what he said. Topcoder's active top 250 advances to Round 2 without taking part in Round 1. Then, for every sub-round of Round 1, top 750 advances to Round 2, as you said.
•  » » » 3 years ago, # ^ |   0 gotcha
 » 3 years ago, # |   0 Contest will start in 23 hours.
 » 3 years ago, # |   0 Auto comment: topic has been updated by cgy4ever (previous revision, new revision, compare).
 » 3 years ago, # |   0 This round has second Data Science Weekly Challenge associated with it: the author of the fastest submission to Easy problem in Round 1A done in the language which has the least submissions done in it will get a TCO'17 t-shirt!
•  » » 3 years ago, # ^ |   +13 If by fastest time you mean counting from the time the problem is opened, this seems like a bad challenge as it is trivially cheatable. If this is indeed the case I predict somebody submits Visual Basic.NET solution within 20 seconds of "opening" problem. If it is timed from start of contest ignore my criticism, then it is fine.
•  » » » 3 years ago, # ^ |   +2 From the start of the contest, of course :-) It also has to be a correct submission, which I obviously forgot to state explicitly.
 » 3 years ago, # |   0 Can we filer submission by language on Topcoder?
•  » » 3 years ago, # ^ |   0 Not that I'm aware of.If you just need to figure out the least frequently used languages, you can guesstimate from per-problem statistics from some recent SRM, like https://community.topcoder.com/tc?module=ProblemDetail&rd=16880&pm=14557
 » 3 years ago, # |   0 Will there be a parallel round for those with byes to compete?
•  » » 3 years ago, # ^ |   +8 No we don't have parallel for round 1. (If we have one then it will be something like Div1 contestants solving Div2 tasks, which is not that fun)We will have parallel round for round 2 and 3 for people already advance.
•  » » » 3 years ago, # ^ |   +69 That is really fun for me! I like solving easy tasks, it gives me a false sense of confidence! Otherwise I will be frustrated by always having difficult problems to work on.I wish that all problems on CodeForces and TopCoder were easier so we wouldn't have to think anymore!
 » 3 years ago, # |   0 A bit off topic, and maybe a newbie question, but why can't I practice from past SRMs right now? There's only TCO rounds in the options for practice rooms.
 » 3 years ago, # |   0 Off topic: does anyone know what to do if arena looks like this on my laptop?
•  » » 3 years ago, # ^ |   +5 Magnifying glass?
•  » » 3 years ago, # ^ |   +8 Your screen resolution is too damn high. Same is with me.. http://codeforces.com/predownloaded/3c/b7/3cb70e9d8fe1522463c1d1214c30238a2d2cb8ea.png
•  » » » 3 years ago, # ^ |   +22 Today I changed every font-size I've found in arena to 16pt. It's quite a shame technology develops faster than topcoder arena :(
•  » » » » 3 years ago, # ^ |   +13 Changed it to 24. Still it's not big enough
•  » » » » » 3 years ago, # ^ |   +8 Use some plugin like KawigiEdit.. I changed it to 30.. Atleast I can see editor perfectly.
 » 3 years ago, # |   0 Are we allowed to compete in TCO 1B if we qualify for the next round today in 1A?
 » 3 years ago, # |   +8 987 registrants! I doubt that there will be 750 non-zero scores!
•  » » 3 years ago, # ^ |   0 Is it too much? or too low?
 » 3 years ago, # | ← Rev. 2 →   0 I couldn't hack medium problem because I couldn't slide the window.
 » 3 years ago, # |   +3 How to solve Hard ?
•  » » 3 years ago, # ^ |   0 I couldn't code it during contest, but I think it might work. Take the mirror image of the left half of the convex polygon, so both halves are in the right half(x >= 0). Now, you need to find the upper hull of this set of segments. Once you do that, you can sum the volumes by using the volume of a frustum of a cone formula.
•  » » » 3 years ago, # ^ |   0 Cool! Thanks :)
•  » » » 3 years ago, # ^ |   0 How to find the upper hull ?
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   +3 So now you have two sets of segments. Note each set has O(N) segments. We want to find all points of interest, basically, the points which can be present on our upper hull. For that, create a set of points S. Add each vertex belonging to at least one of the segments to S. Now for all segments, if they intersect, add their intersection points to S as well.Now create another set Y from S such that Y stores the y coordinate of every point in S. Now our target is for all , find the maximum x that it stretches to. To do that, let's fix the y coordinate, say it is r. Now iterate over all segments, and if the segment is such that it intersects the line y = r, then evaluate the line (assume the segment is a line) by fixing the y coordinate in that line as r, and finding the corresponding x coordinate. Find the maximum such x coordinate for every y.Now iterate over all in increasing/decreasing order, and use the formula for volume of a frustum of a cone. The radii for the frustum will be the maximum value of x coordinate for the current y value, and the maximum value of x coordinate for the previous y value. Height will be the difference in the current y coordinate and the previous one.AC Code: ideoneEdit: When you are iterating over all points P, don't add (x, P.y) for every line L. Rather add it for only that line L' such that the corresponding x is maximumEdit 2: Rewrote Explanation.
•  » » 3 years ago, # ^ |   0 Another way of doing it is calculating if only the lefthand side is there, adding if only the righthand side is there, then subtracting the intersection of the two polygons. (Which should be easy to implement if you already have polygon intersection)
 » 3 years ago, # |   0 How to solve Medium?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 dp: f[a][b][c]=maximum surface of a cube of axbxc, in the transition cut a slice of length s from each dimension.
•  » » » 3 years ago, # ^ |   0 Thanks!
•  » » » 3 years ago, # ^ |   +12 And then comes someone who solves it greedily and make you unsuccessfully challenge him :(
•  » » 3 years ago, # ^ |   +10 There is another solution to this. I divided each side into parts like A=(s,s,s,s,s....,s+a%s) similarly B and C. Then for every possible combination of a[],b[],c[] I calculated required answer. Codeclass CheeseSlicing { public: int totalArea(int A, int B, int C, int s) { int ans=0; vectora,b,c; if(A=s) ans+=(x*y*z)/mm; } } } return ans; } }; 
•  » » » 3 years ago, # ^ |   0 Optimized version of your solution described in editorial without proving:int[] dim = new int[] {A % S + S, B % S + S, C % S + S}; Arrays.sort(dim); dim[0] -= S; return (A * B * C — dim[0] * dim[1] * dim[2]) / S;
•  » » » » 3 years ago, # ^ |   0 This is a greedy approach.Let's cut off slices of thickness exactly S (it doesn't make sense to cut off thicker slices). If the total volume of the slices cut is the same, their total area is also the same regardless of the order in which the cuts are done. We can keep cutting them off until a piece with all dimensions less than 2S is left. The dimensions of this piece are given as dim. int[] dim = new int[] {A % S + S, B % S + S, C % S + S}; This last piece is also a good slice, with thickness equal to the smallest of its dimensions and area equal to the product of two other dimensions. To make it a slice of thickness S, we can make a cut in the smallest dimension (this preserves the area of the slice). To get the dimensions of the throwaway piece (from which we can't produce any more slices), we model this cut: Arrays.sort(dim); dim[0] -= S; Finally, the only part of the original piece that is not converted to slices of thickness exactly S is this throwaway piece. To find the total area of good slices, we take the used volume (the volume of original piece minus the volume of throwaway piece), and divide it by S. return (A * B * C - dim[0] * dim[1] * dim[2]) / S; 
•  » » » » » 3 years ago, # ^ |   0 It is not complete proving of optimality. Someone can ask:Why we can cut off slices of thickness exactly S of whole piece?Why we need stop cutting if dimension less than 2S ?
•  » » » » » » 3 years ago, # ^ |   0 Because if a dimension less than 2S is cut into a and b (a+b<2S), we would at best be having a>=S and b
 » 3 years ago, # |   0 So you can literally do nothing and rank 715 :)
 » 3 years ago, # |   +15 It is only me or topcoder is too slow ?
 » 3 years ago, # |   0 How to upsolve the problems? Will the contest be rated? If so, when will the rating be updated?
•  » » 3 years ago, # ^ |   0 they're already updated
•  » » 3 years ago, # ^ |   +3 Already done. Log out and log in again.
•  » » 3 years ago, # ^ |   0 It already is(in the arena).
 » 3 years ago, # |   0 So many failed solutions on 250p problem(mine too)? What was the hack?
 » 3 years ago, # |   0 Will Byes also be there for Round 1B ?
 » 3 years ago, # |   +3 When I go to https://www.topcoder.com, I end up in an infinite loop of automatic redirects. Anybody else experiencing this?
•  » » 3 years ago, # ^ |   +2 This happens in firefox. Either open in chrome or clear firefox cache.
•  » » » 3 years ago, # ^ |   0 Thar was chrome, but yeah, clearing some data helped. Thanks!
•  » » 3 years ago, # ^ |   0 happens with me. I use chrome
 » 3 years ago, # | ← Rev. 3 →   +3 In medium I am getting better results than expected. Codebool inici = true; int area[101][101][101]; class CheeseSlicing { public: int totalArea(int A, int B, int C, int S) { if (inici) { inici = false; for (int i = 0; i <= 100; i++) for (int j = 0; j <= 100; j++) for (int k = 0; k <= 100; k++) area[i][j][k] = -1; } if (area[A][B][C] < 0) { if (min(A, min(B, C)) < S) area[A][B][C] = 0; else if (A%S == 0 or B%S == 0 or C%S == 0) area[A][B][C] = (A*B*C)/S; else if (A < 2*S and B < 2*S and C < 2*S) area[A][B][C] = max(max(A*B, A*C), C*B); else { int candA, candB, candC; candA = candB = candC = 0; for (int i = 1; i < A; i++) candA = max(candA, totalArea(i, B, C, S) + totalArea(A-i, B, C, S)); for (int i = 1; i < B; i++) candB = max(candB, totalArea(A, i, C, S) + totalArea(A, B-i, C, S)); for (int i = 1; i < C; i++) candC = max(candC, totalArea(A, B, i, S) + totalArea(A, B, C-i, S)); area[A][B][C] = max(max(candA, candB), candC); } } return area[A][B][C]; } }; In Test 3: [49,92,20,3] I get 45080 and I should get 30045. What is going on? I would appreciate any insight.UPD: I got it. The global variable bool inici shall be inside the class to reinitialize it for every test. Sorry for the noise.
•  » » 3 years ago, # ^ |   0 Were u using kawaga edit or something other than standard editor??
•  » » » 3 years ago, # ^ |   0 I was using kate as an editor.
 » 3 years ago, # | ← Rev. 2 →   0 https://pastebin.com/4kaTEfffHere is my solution for the 2nd problem. It didn't pass in the contest. I don't know why. I tested it in the practise mode and it showed me "Passed". Also I see many other similar solutions with mine that passed. So can you tell me what is wrong with my source or it is wrong with the system ?Thank you !
•  » » 3 years ago, # ^ |   0 TLE100, 100, 100, 1Click
•  » » » 3 years ago, # ^ |   0 Well why I get TLE ? Isn't my complexity O(10^6) ? Also why in the practise mode it says "Passed" ?
•  » » » » 3 years ago, # ^ |   0 It's complexity is O(n^4). Declare a global cnt variable, increment it before if(ret != -1) return ret; you can see that there 2.97*10^8 recursive calls. I also had same solution but couldn't submit because of one typo error but it failed in practice room afterwards.Most people used O(n^3) solution. Instead of loop, you can cut two blocks one with size s and other size side-s. How to prove this is optimal?And there is O(1) solution.
•  » » » » » 3 years ago, # ^ |   0 My solution's complexity is O(n4) and it passed the 100 100 100 1 case in 0.24s.
•  » » 3 years ago, # ^ |   0 I think that's pretty unfortunate. I tested the case provided by dush1729 during contest and that ran in roughly 1.5s in the arena.
•  » » » 3 years ago, # ^ |   0 Did you test it with my source or with yours ? I saw similar solutions with mine that passed and I don't know what is wrong with mine....
•  » » » » 3 years ago, # ^ |   0 I tested my solution which is almost identical to yours, with complexity O(n4).
•  » » » » » 3 years ago, # ^ |   0 Did it pass in the contest yesterday ?
•  » » » » » » 3 years ago, # ^ |   0 Yes it did.
•  » » » » » » » 3 years ago, # ^ |   0 Well any idea what happened with mine ? It is really strange and I don't care for the current submission but I want to know what went wrong so I can avoid it in the future.
•  » » » » » » » » 3 years ago, # ^ |   0 TBH I don't know. Though your solution seems to fit TL by taking S globally, rather than passing in function. Also note that my solution's runtime varies in range 1.53-1.9
•  » » 3 years ago, # ^ |   0 It's really unfortunate that your code got TLE. But one correction, your complexity is not O(10^6) it's close to O(3*10^8) in worst case. Which is really tight.Besides, in your solve function you are using unnecessary too much if else condition which is also a main reason i think. And more importantly when you solve a problem using recursion it always add a constant factor.
 » 3 years ago, # |   0 i tried this code for 500 point problem (practice room) and unfortunately got TLE on test case {{42, 84, 99, 7}.My code — 500 points practiceCan anyone help me with this? Thanks
 » 3 years ago, # |   0 How do I know if I qualified? do I get an email or something?
•  » » 3 years ago, # ^ |   0 You will get an email. Everyone got a positive score then you will advance (except cheater or ineligible for other reasons).