Tommorow will be held Single Round Match 639 at 15:00 MSK.
Let's discuss here problems after the contest.
Tommorow will be held Single Round Match 639 at 15:00 MSK.
Let's discuss here problems after the contest.
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 3 | Proof_by_QED | 147 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 142 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
I like your ID.
I use it :D
Another 3-week period between two SRMs
There was TCO, which should count as several SRMs.
250 was cruel!!!
It allowed
solutions though, so not that cruel.
It showed us how greedy we are. :P
It was the HackRound :)
15th place: l0l h4x
See the 33th place. No problem solved)))
Yeah, well 15th place is no problem attempted.
Also, I guess this gives us simple proof that the "positive points for challenging" rule has been removed.
The rule is "non-negative points for challenging", so you still have one chance if your score is 0.
Oh, okay. I'm not too familiar with TC rules, because I never read rules. I just try out stuff for practice and check what the most important stuff means (and go by common sense). And TC has a lot of more obscure ones that don't apply to me much (like this one, since I'm almost never challenging).
256th lol) But I was speaking with chinese contestant in chat and discovered that "erfen" is "lower_bound" and "huangjin" is "golden_section".
How to solve Div 2. 500?
find N such that N*(N+1)/2 == x+y, if you can't — return -1;
and find the answer by greedy substractions x := x — N..1.
UPD but I wasn't sure that greedy will work, so I've created array a[2*10^6] with some strange values and used binary search to find the answer "i" such that a[i]<=x
(Edit: This is for d1-250, not d2-500): In your greedy subtractions, make sure to never leave 2 as a remainder, because it's the only number you can't make.
(...and if you do find that corner case, make sure to write the if condition correctly or you'll end up failing like me anyway u.u)
Did you think greedy only because input size was an indication that DP won't work? Or were you able to see the greedy solution from the beginning?
yep I wonder why return is long long :D int is enough
UPD: removed, I didn't notice div2 500 was similar to div1 250
Xellos editorial:
Can you share code?
prev. edit
x=9, y=0, no such N exists
This is my solution. I forgot to check the corner case when x = 0 and my solution was challenged. But I fixed and sent it after contest and it passed all the test. It is sad because I only forgot to include &&x = = 0. Next time I will be pending for small details.
Your solution is great i was able to understand it . But seeing other submissions in topcoder i came across this solution Topcoder Solution unable to understand logic
How to solve 1000? I've reduced it to some problem of linear programming with integer values, but do not know how to solve it in these constraints.
I reduced 1100 to the form X * case1 + Y * case2, where case1 is if you feed first pet on t=0, and case2 is if you feed second pet on t=0 (eventually you'll reach a time t in which you can choose again, so you'll end up choosing case1 X times and case2 Y times).
I couldn't finish during the contest time, but I managed to solve it in the practice room with ternary search on X. Now have fun dealing with all of the corner cases and overflows! :D
As I can see, Petr and tourist solved it differently, so maybe their solution is a bit closer to what you came up with.
I did the same as you (talking about idea), but did not come up with the ternary search approach.
By the way, why ternary search works in this problem?
I like the 500 problem very much though I didn't solve it in the contest. (With some array doesn't clean up and one more stupid mistake.) But I'd like to share with you guys my O(N2) solution. I am going to write a post about it. Will be updated soon. :D
UPD LINK
Can someone explain why in Div 1 500 folding row-wise and then column-wise independently and at the end multiplying the two values gives the correct result? My main problem is that I don't really understand why they are independent? Intuitively I thought that if the number of remaining rows is smaller, the possible column-wise folding should be smaller.
Take a vertical and horizontal fold. Show that if you can fold vertically first and horizontally afterwards, the board is such that you can swap them.