Egor's blog

By Egor, history, 8 years ago,

Contest is finished, you may discuss problems

• +28

 » 8 years ago, # |   +6 Is it really finished? It says "end: 25 Aug 2015, 22:00:00". Though looking at the screencast, now it should be forcibly finished...
•  » » 8 years ago, # ^ |   -15 It seems both views were by myself, so I think it should be ok
 » 8 years ago, # |   -7 Auto comment: topic has been updated by Egor (previous revision, new revision, compare).
 » 8 years ago, # |   +25 I appreciate that all of you was able to find out link when the contest was still up, but had you noticed that video on that link wasn't available at the time?
 » 8 years ago, # |   0 How to solve C? And question about B, could you please give me an counter-example for my algo? Algo is greedy. Start from the leftmost disk to the rightmost. Build machine queue, starting from empty queue. For each disk try to match machine type from the queue. If machine is not found add new machine with certain type to the end of the queue. Calculate max time. Example, disk -1: 3-2-1 disk -2: 1-2-3 Start building queue from 1-2-3. Since machine queue was empty from the beginning, after disk(-2) it looks like: 1,2,3. Steps = 4 Start matching disk(-1): type 3 matches last machine in the queue, so add 2 more machines with types 2 and 1. After disk(-1) queue looks like: 1,2,3,2,1. Total number of steps = 5. Got WA on 6th test.
•  » » 8 years ago, # ^ |   +11 Counter-example: 3 1 2 3 2 3 1 3 2 1 Correct answer is 6.
•  » » » 8 years ago, # ^ |   0 Thank you!
•  » » 8 years ago, # ^ | ← Rev. 2 →   +3 If gcd(a.len, b.len) = 1, then we compare each character of a to each character of b corresponding number of times
•  » » » 8 years ago, # ^ |   0 Thank you, Egor! Your answer and screencast helped me.
 » 8 years ago, # |   0 How to solve A and E?
•  » » 8 years ago, # ^ |   +8 A — for each connected component in the graph check that it is bipartite. Then use DP similar to knapsack putting all components there to find out what sum close to N / 2 you can get. DP[x][y] should be something like whether you can get a total of x people in one hall if you put people from last y components. After that you can restore the answer greedily starting from the component containing first scientist, if you can you need to assign him to the first conference hall which will give lexicographically smaller result string.
•  » » » 8 years ago, # ^ |   0 Thanks.