AtCoder Grand Contest 017 will be held on Sunday (time). The writer is semiexp.
The point values will be 200 — 400 — 1000 (500) — 1100 — 1200 — 1600.
Let's discuss problems after the contest.
AtCoder Grand Contest 017 will be held on Sunday (time). The writer is semiexp.
The point values will be 200 — 400 — 1000 (500) — 1100 — 1200 — 1600.
Let's discuss problems after the contest.
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 4 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 142 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
[reminder] The contest starts in 2 hours.
Your contests are serious hit on my self-esteem, guys.. It took me an hour to solve B and I totally don't know how to prove my solution to D, not to mention I couldn't come up with C or E at all. And something like that happens all the time I try to solve AtCoder. It seems I just can't into solving your problems :'(
That's what you get for problems which require you to utilize your brain ;) If you participate for fun, not for self-esteem, such problems are much nicer than yet-another-standard-technical-problem from (put almost any other contest platform name here).
That said, this time problem D wasn't very original :( It is called "Hackenbush", and it probably appeared before on dozens of different contests.
Have you seen D before? I was surprised to see that it was solved in 3 minutes.
It came in our ICPC regionals and i have seen it at cf gym before as well.
It's a well-known game called Green Hackenbush.
Will the contest be unrated because of this ?
UPD: It's rated
khsoo01 didn't seen it before but he solved it in 3min. He said it was trivial grundy number question.
I'm not familiar with grundy number, but I thought there will be simillar problem somewhere. So I started to google and found a nice editorial in HackerRank
Yes,when practising for OI about 3 months ago,I was told the exactly same problem and its solution.And since the only difficulty lies in the way of calculating Sprague-Grundy function,the problem seemed to be easier than Problem A for me. (And I'm sure that many Chinese contestants,especailly who participated in OI,have seen this problem before.)
Yes, I did: https://www.codechef.com/AMR16MOS/problems/AMR16J
When I was solving problems from that Amritapuri contest I was pretty surprised, because I solved all harder problems without big effort (only painting one demanded more work for me), but I couldn't solve this one for a really long time. I was pretty frustrated that problem without any ACs was no-brainer for me, but I was stuck for few hours at something that so many teams have solved :p (results here: http://results.cloudcontest.org/amrita2016/ACMICPCRC.html, problem J). I finally solved it, but after long time. I wouldn't call it "trivial grundy question", it depends on some details in definitions you make whether solution becomes intuitive or not. Still, after I shared this with my teammates Marek told me it is well-known game called green hackenbush, as already mentioned here.
Never been waiting so eagerly for the testcases (of E) to be uploaded...
indeed a notorious coincidence with last AGC...
Uploaded.
Thanks ^ ^
Typo in solution for E: replace
if Di ≠ 0, r = + Bi
by
if Di ≠ 0, r = + Di
C was much harder than D and E IMO.
Initially there were no queries in C. The writer's intended solution works in the same way even with queries (and it's described in the editorial), but I solved the original vertion with standard DP + segment tree, and we decided to add queries to avoid that. It seems it became much harder.
My F passes (after contest) in 3796 ms and 221568 KB, but during the contest it gave MLE with 275 KB. Did anyone else have this problem?
The limits seems very tight for this problem, even if you are trying to fail O(2^n n^3) solutions.
Sorry this time the limit had to be very tight because we have to separate O(2nn2) and O(2nn3). Still our Java solution works in 2s.
This line tricked me into optimizing my O(mn22n) until it passed.
Remember that Codeforces somehow shitty parses powers in Latex :p
Exact same question:
Link
O(1) solution for problem B:
" On the other hand, when this inequality holds, we can find an example of Yi. We can first set the values of Yi to −D or C, and while the sum is smaller than B − A, we can increase integers one by one in the order Y1, Y2, Y3, . . . , YN−1, Y1, Y2, . . . ." . I am not getting these lines from editorial of B .Can someone please help !!!!
Please help someone,I am still not getting it :(
I have a solution using flow with upper and lower bound capcity and I wonder whether it is right.
For a piece i we make two new nodes : i and i + n, and we add an edge (i + n, i) with capacity [1, 1].
If piece i on the left of piece j, then we have:
Cj = 0 and Aj = Di
or
Di = 0 and Bi = Cj
then we add an edge (j, i + n) with capacity [0, 1].
Add twos edges (S, SS) and (TT, T) with capacity [1, 1], and if i can be put at the leftmost place, we add an edge (SS, i + n) with capacity [0, 1], similar for the rightmost one.
It's easy to make 2 * h new nodes to reduce the number of edges to O(n).
I wonder whether it's right. Anyone help me, please?
Sorry for poor English.
My bad.
I just want to find whether there's a Hamilton path in polynomial time.
The solution above will find some circles instead of a Hamilton path.