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/

Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official.
×

# | User | Rating |
---|---|---|

1 | tourist | 3880 |

2 | jiangly | 3669 |

3 | ecnerwala | 3654 |

4 | Benq | 3627 |

5 | orzdevinwang | 3612 |

6 | Geothermal | 3569 |

6 | cnnfls_csy | 3569 |

8 | jqdai0815 | 3532 |

9 | Radewoosh | 3522 |

10 | gyh20 | 3447 |

# | User | Contrib. |
---|---|---|

1 | awoo | 161 |

2 | maomao90 | 160 |

3 | adamant | 156 |

4 | maroonrk | 153 |

5 | -is-this-fft- | 148 |

5 | SecondThread | 148 |

7 | atcoder_official | 147 |

7 | Petr | 147 |

9 | TheScrasse | 145 |

10 | nor | 144 |

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/

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/20/2024 09:10:42 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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.

DS Weekly Challenge #8.2: Do the latest successful challenge in Algorithm Round 2A.

Who won that challenge?

This thread has all winners which have been announced yet.

Starts in 1 hour.

How to solve 500?

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.

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

First rule out the obvious non solutions (

d0[0] ≠ 0,d1[1] ≠ 0 andd0[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.

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

Yes, this problem ruined my 2a. :( I tried harder version ideas and made a bug.)

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

Please send an email to [email protected]. "unused code rule" is handled manually.

Who else missed the case (

c,s) = (5, 6)?I did. And also screwed up B. Yay, 0 points :)

It takes me one attempt! :(

Medium reminds me this: http://cf16-exhibition-open.contest.atcoder.jp/tasks/codefestival_2016_ex_a

How to solve 250?

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

Each integer greater than 6 or equals 5 always presents as 2a + 3b. Small case is easy to handle.

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 :)

wow! too fast editorial!

Problem A seems to be almost same as 500pts!

Anyone can solve 1000 correctly has great attention! I didn't have >_<

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.

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

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

I also missed the k=1 case, sad.