### Блог пользователя cgy4ever

Автор cgy4ever, история, 10 месяцев назад, ,

TCO Round 2A will start at 12:00 noon EDT Saturday, May 20, 2017

Top 40 will advance to Round 3 and will get a T-shirt.

Find more details here: https://tco17.topcoder.com/algorithm/rules/

•
• +48
•

 » 10 месяцев назад, # |   +15 I'm sure that some time ago, the start time on that page (https://tco17.topcoder.com/algorithm/rules/) was 11:00, not 12:00, but they quietly changed it.
 » 10 месяцев назад, # |   +5 DS Weekly Challenge #8.2: Do the latest successful challenge in Algorithm Round 2A.
•  » » 10 месяцев назад, # ^ |   +1 Who won that challenge?
•  » » » 10 месяцев назад, # ^ |   0 This thread has all winners which have been announced yet.
 » 10 месяцев назад, # |   0 Starts in 1 hour.
 » 10 месяцев назад, # |   +18 How to solve 500?
•  » » 10 месяцев назад, # ^ |   +39 Consider just solving it for dist0 with as many edges possible. Now, take the intersection of these two solutions and see if it satisfies the original constraints.
•  » » » 10 месяцев назад, # ^ |   +39 So, this is the same as creating a complete graph and removing all edges which are invalid (ie. abs(dist0[a]-dist0[b]) > 1 || abs(dist1[a]-dist1[b]) > 1).I finished coding this 2 min after the contest ended. FML. :(
•  » » 10 месяцев назад, # ^ | ← Rev. 3 →   +23 First rule out the obvious non solutions (d0[0] ≠ 0, d1[1] ≠ 0 and d0[1] ≠ d1[0]).Consider a pair of vertices (u, v). If there is an edge between them, then |d0[u] - d0[v]| ≤ 1 and |d1[u] - d1[v]| ≤ 1. Although this is not an equivalent condition, one possible solution is to include all edges where the above conditions satisfy. Do a Floyd-Warshall in the end to check if the solution is valid.EDIT: typo.
•  » » 10 месяцев назад, # ^ |   +29 A harder version was here: http://cf16-exhibition.contest.atcoder.jp/tasks/codefestival_2016_ex_a, and there is an editorial for this problem here (problem A, english version is at the end).
•  » » » 10 месяцев назад, # ^ |   0 Yes, this problem ruined my 2a. :( I tried harder version ideas and made a bug.)
 » 10 месяцев назад, # | ← Rev. 3 →   +39 How is "unused code rule" enforced? Had to scroll through 3-4 screens of templates today before reading one solution(and there were some comments inside too). pinging cgy4ever
•  » » 10 месяцев назад, # ^ |   +10 Please send an email to support@topcoder.com. "unused code rule" is handled manually.
 » 10 месяцев назад, # |   +26 Who else missed the case (c, s) = (5, 6)?
•  » » 10 месяцев назад, # ^ |   +20 I did. And also screwed up B. Yay, 0 points :)
•  » » 10 месяцев назад, # ^ |   0 It takes me one attempt! :(
 » 10 месяцев назад, # |   +55 Medium reminds me this: http://cf16-exhibition-open.contest.atcoder.jp/tasks/codefestival_2016_ex_a
 » 10 месяцев назад, # |   0 How to solve 250?
•  » » 10 месяцев назад, # ^ | ← Rev. 3 →   0 I did it like this: let's find all reachable pairs for A, B <= 50 using straightforward dynamic programming. If c, s <= 50, we're done. Otherwise, let's try to subtract each reachable pair from c and s and check if the gcd of the remaining numbers is not 1 for at least one such pair. A good thing about this solution is that it's impossible to miss a corner case as there're no corner cases (unlike in a solution that uses case analysis).
•  » » » 10 месяцев назад, # ^ |   +20 Each integer greater than 6 or equals 5 always presents as 2a + 3b. Small case is easy to handle.
•  » » » 10 месяцев назад, # ^ |   0 It can be shown even stronger that if you can split (C, S) into (x, y) and (C — x, S — y) for x, y <= T and the gcd conditions hold (in my code I choose T = 10), you are done. That saves the DP :)
•  » » » 10 месяцев назад, # ^ |   0 Thanks :)
 » 10 месяцев назад, # |   +8 wow! too fast editorial!Problem A seems to be almost same as 500pts!
 » 10 месяцев назад, # |   +10 Anyone can solve 1000 correctly has great attention! I didn't have >_<
•  » » 10 месяцев назад, # ^ |   0 What do you mean? I had an idea but didn't have time to complete all its details. What I tried to do is to consider how an array b[i] = (a[i] ^ a[i + 1]) changes after a move.
•  » » » 10 месяцев назад, # ^ | ← Rev. 3 →   0 After considering the array b, there is one free variable : a[0], so the answer to the original problem seems to be something like solve(b)*2, but if we can perform no operation, then the answer is 1 (not 2). I implemented and submitted this code, but in fact, when K==1, the answer is solve(b)*2 minus 1, because we cannot make the array (~a[0],~a[1],...,~a[N-1]). It's difficult to notice this fact (at least for me).
•  » » » » 10 месяцев назад, # ^ |   0 Ohh I see. I've tried to implement something in 5 minutes and failed that test and thought about this. But I gave up as my dynamic programming had a really important flaw (maybe some other observation missing?) and even though I realized multiplying by 2 needs some extra subtracting, I couldn't finish it. I think the problem is really nice and interesting, but, at least for me, it demanded more time
•  » » » » 10 месяцев назад, # ^ |   +5 I also missed the k=1 case, sad.