Today will be held Single Round Match 633 at 19:00 MSK.
Let's discuss here problems after the contest.
UPD: Contest delayed to 15 minutes
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3821 |
3 | Benq | 3736 |
4 | Radewoosh | 3631 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3388 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Today will be held Single Round Match 633 at 19:00 MSK.
Let's discuss here problems after the contest.
UPD: Contest delayed to 15 minutes
Name |
---|
SRM 633 — Brought to you by Google :).
Anyone's going to compete in Div. II ?
Most of Div2 users will compete in Div2 :D
Glad to hear it :D I asked, because I have only seen Div.I problems discussed in this posts (most of the times).
Is there anyone facing problem with launching arena or doing registration? I can't launch my arena. I have downloaded the latest one. it shows a lot of exceptions when I try to launch it :(
Try to clear your java cache.
Contest delayed 15 minutes :((
Good job Topcoder!
numerOfScrewedUpContests++;
I considered this contest a good one for me. Happy to go back to yellow. :)
He meant that some contestants weren't assigned a room, contest was delayed and challenge phase was delayed even more.
Awesome problems! How to solve 600? I've tried iterating over the node which is then called "root" in both trees, taking "tree1 + inverse_arcs(tree2)" and solving "max-weight strongly connected subset problem" there. It seems that this should somehow be reduced to max-flow, but I didn't figure out how :(
Is is possible to solve "max-weight strongly connected subset problem" in poly time?
I don't know about general case. But in this case, it is apparently possible, because (as pointed out below by azizkhan and Petr), if we also reverse the arcs of the first tree, we'll get max-weight closure problem.
After you fix the root, the problem is finding the max weight subset which contains that root. Now you have 2 rooted trees. Let's build a network as follows: For each vertex v add a directed edges from it to its parents with infinite capacity in both trees. For each vertex v, where score[v] >= 0, add an edge from S to v with capacity score[v]. For each vertex v, where score[v] < 0, add an edge from v to T with capacity -score[v]. It can be shown that the answer is sum of positive scores minus minCut between vertices S and T.
P.S. My solution is failed because I have a bug in MaxFlow algorithm
After we've picked the root, then our condition boils down to: if we take a vertex, we need to take its parents in both trees.
If we have a set of conditions "if we take X, we must take Y" we can apply min-cut by adding an infinite edge from X to Y — this way if we take X, we must take Y :) The only remaining part is choosing weights for edges from S and to T so that the weight of the cut is const+answer.
Woah, I just finished first in Div 2, had to share this somewhere.
I solved 250 and 500 (but not very fast), and then in the challenging phase I noticed a guy has only return "Solution exists" in this code. One guy tried challenging him, but accidentally entered a "solution exists" test and got a wrong challenge. I did that mistake too, but I was faster for the second challenge and got 25 off him. Then I noticed his 500 was also a return, I challenged it, and for the 250 he tried entering all possibilities manually, but only did it until 19, so I challenegd that one for a total of 125 from that guy.
Then I found two more wrong 500 solutions (one timed out, one had a flaw) for 100 more points.
Did you advance to Div. 1 ? I spent most of the time debugging my 250 and got only something like 100 points for it and then there was no time left to solve 500...
I sadly didn't. My first SRM was a complete blowout (two wrong solutions with very dumb mistakes and two wrong challenges) so I started with 300-ish rating. I advanced from 771 to 1136 this round.
That's quite a jump anyway, congrats :D I'm like much more stable, my rating is always >= 900 && <= 1100.
I wonder which is Div 1 Easy which has the least % accepted. I remember Nickolas' AgeEncoding had very low acc rate.
AgeEncoding had 9.17% — very low AC rate; at least it should be lowest one during last few years:)
And sometimes all 6 problems have low AC rate, like in SRM 438.
Would anyone like to explain the problem of DIV-2 ,500 POINTS, 1000 POINTS how to solve both of these problem ?
Div 2 500 :
Let's look at the first test sample : We need to get to (5,4) with steps of distance 2 and 5. Using Euclidean distance we find the distance from the goal (5,4) to the start (0,0). In this case, the distance is 6.4. We also take a sum of all the steps. In this case, the sum is 7. If the sum is less than the distance, then you are not able to reach it in any way. Also, if the sum is equal to the distance, you are 100% able to reach it (just jumping directly towards the goal). Otherwise, we have this situation :
We try to represent the path as a triangle, one side is the distance, the other sides are the steps you have in the input. For triangles, there's the following rule:
a < b+c
b < a+c
c < a+b
Otherwise stated : Every side of the triangle must be smaller than the sum of all other sides. If this is valid, then you return "Able", otherwise you return "Not able". This "theorem" is also valid for all other polygons. For example, if we had 4 sides, it would be :
a < b+c+d
b < a+c+d
c < a+b+d
d < a+b+c
So you just have to check this theorem. Here's my solution.
thanx add1ctus
There is another way to think about this problem.
If all reachable points after k jumps are a filled ring (true for first jump which is a circle). Where do all reachable points after k+1 jumps lie? Answer: A ring with a bigger outer radius (enlarged by k+1 th jump) and a smaller inner radius (diminished by k+1 th jump but not smaller than 0). And they also fill this ring completely.
I don't have a strict mathematical prove though (I used a sheet of paper and circle to get the idea)
oops, left out something crucial: The above is only true if jumps are in diminishing length.
But one can convince oneself that the order of jumps doesn't matter so we can start with the largest jump. Again no proof (just pen and paper to get the idea)
I was looking on similar solution all the Challenging, but I had no idea how it should work. Thanks a lot for your explanation!
I am always confused about this one.Can you tell me while you are comparing
sum
anddistance
why are you doing thisabs((double)sum-distance)<0.00001
and not this
abs((double)sum-distance)< numeric_limits<double>::epsilon()
How can one decide that factor while comparing two doubles?
We know, a triangle is valid, if
a < b+c
b < c+a
c < a+b
so, triangle with length {1,2,3} is not valid, as
3 < 1+2
isn't true. So in general, if a side is equal to summation of other side of a polygon, then this polygon isn't valid. Right ?Now in your code:
Here, why you don't need to check if
temp-jumpLengths[j]
is equal tojumpLengths[j]
?I coded like this comment(I returned "Not able" if
temp-jumpLengths[j]<=jumpLengths[j]
), but there is a input {1, 0, {100, 101}} for which my code returns "Not able", but judge says, "Able". From (0,0) to (1,0) distance is 1. If I think the input is a triangle with the length of {1,100,101} then101 < 100+1
isn't true. So output should be "Not able". Shouldn't be it ? Please, clear me...Woah, this is actually a mistake on my end, and a lucky one (because if I didn't do that mistake, my answer would have been wrong).
The problem with that theorem is that it is only valid for valid triangle. In the case of sides 1, 100 and 101, we have two angles of 0 degrees and one angle of 180 degrees. That is an invalid triangle, but it is a valid jump sequence. Removing the '=' will make sure that you count those jump sequences as well.
Humm got it... Thanks... :)
But it was really a tricky one and most probably the cause of too many system test failure is this case... :/
how lucky you are !!! :P :)
congratulation for division 2 winning ... :)
Rank 3 goes to egor in both the divisons :)
Div1-1000pts after considering each prime individually boils down to that problem
Is there an assignment for a[1], ..., a[n] such that some constraints of form max(a[i], a[j]) = c and min(a[i], a[j]) = d are fulfilled? If for particular vertex those constraints are contradictory, we return "NO". If not, then we can fulfill max edges with lowest label ot min edges with highest labels and we create a boolean variable for this. What is left to do is to check whether 2SAT is satisfiable (which can be very easily done since contraints are small — just check if there is vertex v such that there exist paths v->!v and !v->v)
Arena is not opening :(
How to solve Div 1 250?
If you are in a jump n : You need to check if exist a polygon with sides of length jump[ 0 ] ,jump[ 1 ] , ...jump[ n] and the side with length x.
So your answer is the minimum value of n.
Where can I see results of the round? Arena is down, topcoder.com is also down. Maybe someone has a copy of results. Please, share.
Topcoder.com works well for me right now. Here is overview of the round.
felix-halim.net/tc
What is the solution for the Div2 1000 problem? Any hint anyone?