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

Time: 12:00 noon EDT Saturday, April 1, 2017

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/

cgy4ever I think top 750 will advance to R2 (not 250)

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.

gotcha

Contest will start in 23 hours.

Auto comment: topic has been updated by cgy4ever (previous revision, new revision, compare).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!

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.

From the start of the contest, of course :-) It also has to be a correct submission, which I obviously forgot to state explicitly.

Can we filer submission by language on Topcoder?

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

Will there be a parallel round for those with byes to compete?

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.

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!

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.

Off topic: does anyone know what to do if arena looks like this on my laptop?

Magnifying glass?

Your screen resolution is too damn high. Same is with me..

http://codeforces.com/predownloaded/3c/b7/3cb70e9d8fe1522463c1d1214c30238a2d2cb8ea.png

Today I changed every font-size I've found in arena to 16pt. It's quite a shame technology develops faster than topcoder arena :(

Changed it to 24. Still it's not big enough

Use some plugin like KawigiEdit.. I changed it to 30.. Atleast I can see editor perfectly.

Are we allowed to compete in TCO 1B if we qualify for the next round today in 1A?

987 registrants! I doubt that there will be 750 non-zero scores!

Is it too much? or too low?

I couldn't hack medium problem because I couldn't slide the window.

How to solve Hard ?

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.

Cool! Thanks :)

How to find the upper hull ?

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 pointsS. Add each vertex belonging to at least one of the segments toS. Now for all segments, if they intersect, add their intersection points toSas well.Now create another set

YfromSsuch thatYstores the y coordinate of every point inS. Now our target is for all , find the maximum x that it stretches to. To do that, let's fix theycoordinate, say it isr. Now iterate over all segments, and if the segment is such that it intersects the liney=r, then evaluate the line (assume the segment is a line) by fixing the y coordinate in that line asr, 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: ideone

Edit: When you are iterating over all points

P, don't add (x,P.y) for every lineL. Rather add it for only that lineL' such that the correspondingxis maximumEdit 2: Rewrote Explanation.

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)

How to solve Medium?

dp: f[a][b][c]=maximum surface of a cube of axbxc, in the transition cut a slice of length s from each dimension.

And then comes someone who solves it greedily and make you unsuccessfully challenge him :(

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.

CodeOptimized 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;

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.

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:

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.

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 ?

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<S so the part with dimension B is wasted in this case(which could have been used in case the other dimension in the original piece was <a+b) so instead we could just retain the piece as it is and do not cut it.

So you can literally do nothing and rank 715 :)

It is only me or topcoder is too slow ?

How to upsolve the problems?

Will the contest be rated? If so, when will the rating be updated?

they're already updated

Already done. Log out and log in again.

It already is(in the arena).

So many failed solutions on 250p problem(mine too)? What was the hack?

Will Byes also be there for Round 1B ?

When I go to https://www.topcoder.com, I end up in an infinite loop of automatic redirects. Anybody else experiencing this?

This happens in firefox. Either open in chrome or clear firefox cache.

Thar was chrome, but yeah, clearing some data helped. Thanks!

happens with me. I use chrome

In medium I am getting better results than expected.

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

Were u using kawaga edit or something other than standard editor??

I was using kate as an editor.

https://pastebin.com/4kaTEfff

Here 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 !

TLE100, 100, 100, 1

Click

Well why I get TLE ? Isn't my complexity O(10^6) ? Also why in the practise mode it says "Passed" ?

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.

My solution's complexity is

O(n^{4}) and it passed the`100 100 100 1`

case in 0.24s.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.

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

I tested my solution which is almost identical to yours, with complexity O(n

^{4}).Did it pass in the contest yesterday ?

Yes it did.

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.

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

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.

How do I know if I qualified? do I get an email or something?

You will get an email. Everyone got a positive score then you will advance (except cheater or ineligible for other reasons).