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

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

Привет.

11 марта в Самарском университете состоялась ежегодная олимпиада по программированию, и мы снова выкладываем ее в тренировки Codeforces. Тренировка пройдет в воскресенье, 18 марта, в 11:00 MSK.

Этот контест уже третий год проводится личным. Поэтому просим всех тоже участвовать лично. Наиболее интересно должно быть фиолетовым и синим участникам.

Ну и как обычно,

•
• +88
•

 » 10 месяцев назад, # |   +13 Can I register with my team? Or only individual contestants?
•  » » 10 месяцев назад, # ^ |   +8 You can, but people on the onsite contest played individually.
 » 10 месяцев назад, # |   +4 Will there be an editorial after the contest. It becomes really hard to get solutions for all the problems from the comments for beginners like me.
 » 10 месяцев назад, # |   0 I enjoyed the contest, the problems were really interesting. Can I see the case I'm failing at on problem M?
•  » » 10 месяцев назад, # ^ |   +3 This test has n = 3.
•  » » » 10 месяцев назад, # ^ |   0 I'm like brute forcing, so maybe it's some logical bug.Can you share the full test? :)
 » 10 месяцев назад, # |   0 Can someone share his code for C.
•  » » 10 месяцев назад, # ^ |   +2 CodeI'm not sure how clear it is but I can explain anything if it's unclear.
•  » » » 10 месяцев назад, # ^ |   0 Could you please explain how your code works. This is my Code. The Idea is same as yours I guess but its giving wrong answer on Test 11.
•  » » » » 10 месяцев назад, # ^ |   +2 I start by sorting the ranges by their end points. Then as I'm processing the end points, ill greedily build my set. Basically, if by the time I get to the end of some range and there's no number in my set (that's the ceiling() call) that belongs in it's range, then I'll add that range's endpoint to the set. This is always optimal because I'm going in increasing order of endpoints so every time I add a number to my set, it's as large as possible so it's most likely to fit in the other ranges (who all have end points greater than the current one).
•  » » » » » 10 месяцев назад, # ^ |   0 Why I sort the ranges by their start points then I got wrong answer ? But sort the ranges by their end points will get AC ?
 » 10 месяцев назад, # | ← Rev. 2 →   0 Any hint for problem H or L???
•  » » 10 месяцев назад, # ^ |   +5 Problem H:BFS off of every monster tile and only go a maximum of d distance away. Any tile that was touched by a monster's BFS is now no longer usable. Now BFS from your starting point and do regular shortest path in a grid but making sure to ignore cells touched by the monsters.Problem L: For every position i in the string, find the next position of every letter in the alphabet. Now keep some kind of queue and find the next position of whatever letter is queried (or pop the back of your queue). If the next position of the queried letter doesn't exist, the answer is no otherwise it's yes.
•  » » » 10 месяцев назад, # ^ |   0 So simple BFS's were enough in H? I thought that with n*m up to 4*10^10 that would take too long, even just to calculate 'bad' cells
•  » » » » 10 месяцев назад, # ^ | ← Rev. 2 →   +5 n * m ≤ 2 * 105
•  » » » » » 10 месяцев назад, # ^ | ← Rev. 2 →   +4 Oh.. I guess I can't read :(Thanks, now it's a lot more clear
•  » » » » » » 9 месяцев назад, # ^ |   0 that's what i missed:(
•  » » » 9 месяцев назад, # ^ |   0 For H，first i DFS for each 'M' finding which grid can't reach, then BFS for shortest path, but wrong answer on test 20，i really wanna know what test 20 data is,thx~
•  » » » » 9 месяцев назад, # ^ |   0
•  » » » » » 9 месяцев назад, # ^ |   0 really useful!thx!
•  » » » » » 9 месяцев назад, # ^ |   0 but test 20 can just see one line of data:(
•  » » » » 6 месяцев назад, # ^ |   -8 Yeah I too got a WA on test 20 , but I don't know why this approach gives WA with dfs
•  » » » » » 6 месяцев назад, # ^ |   0 Test 22 is here, most probably you can't pass it too.Test 20 is the same but with other parameters: Spoilern=m=447, d=10
•  » » » » » » 6 месяцев назад, # ^ |   -8 But can you help me out why, am I getting a wrong answer. Is doing dfs to find cells at distance d wrong?
•  » » » » » » » 6 месяцев назад, # ^ |   0 Yep, it's definitely wrong. You may visit some cell with distance X <= M, and then, when you will try to visit it again with distance Y < X <= M, you will ignore that edge because cell already visited. So the fix is change visited array type from boolean to int (shortest distance from M to that cell), but in that case I think you may get stuck with TLE.
•  » » » » » » » » 6 месяцев назад, # ^ | ← Rev. 3 →   0 Yeah I encountered a TLE, with bfs
•  » » » » » » » » » 6 месяцев назад, # ^ | ← Rev. 2 →   0 Don't run bfs from each M separately (run normal bfs, just put all 'M' together to the queue with H=0) Try to replace HashMap by array
•  » » » » » » » » » 3 месяца назад, # ^ | ← Rev. 2 →   0 can someone explain why this code gives MLE (the queueis full ) i used bfs from all M then one bFS from s for path length https://pastebin.com/ip8Q1hH8 solved : I have to mark the node visited than added to the queue not the inverse
 » 10 месяцев назад, # |   +1 Задачи в ваших контестах очень интересные и разнообразные! Продолжайте в том же духе!
 » 10 месяцев назад, # | ← Rev. 3 →   0 What's output of problem E for this test case: abaca aabac
•  » » 10 месяцев назад, # ^ |   +4 The output is "NO"
 » 10 месяцев назад, # |   0 What is the test 48 on F?
•  » » 10 месяцев назад, # ^ |   +5 During the contest this test helps me: 4 3 2 3 4 1 4 1 4 0 Answer is NO
 » 10 месяцев назад, # |   0 Any hints on how to approach I? My approach can't seem to get past test 12.
•  » » 10 месяцев назад, # ^ |   +3 I used this approach:Define a procedure findRoot(vertices, leafs, depth) for search a tree root among vertices, inside it we need to find two leafs from a different subtrees (relative to root). It can be managed in O(size(vertices)), then you can easily find a root (it is a vertex, that dist(leaf1, v) = dist(leaf2, v) = depth). Then you need to run findRoot recursively from left/right subtree.So, each findRoot procedure takes 2 * size(vertices) queries (2 * nlogn in total) and additional queries at start to find leafs.
•  » » » 10 месяцев назад, # ^ | ← Rev. 2 →   0 That makes a lot of sense. Thank you!
•  » » » 9 месяцев назад, # ^ |   +3 Hi, I can't figure it out how do you manage to classify vertex according to left and right subtree for the recursive call. Can you explain that part? Because you pass vertices and leafs parameters that, I guess, represent vertices and leafs of the current subtree.Thanks
•  » » » » 9 месяцев назад, # ^ |   0 You have two leafs from different subtrees, so lets call them left & right. So to classify arbitrary vertex we need to compare dist(left, vertext) and dist(right, vertex) — if dist from vertex to left vertex smaller then vertex in a left subtree and vice versa.
•  » » » 9 месяцев назад, # ^ |   0 Could you show me the code? I try many many ways but i still can't figure it out.Thanks.
•  » » » » 9 месяцев назад, # ^ |   0 It's very easy to include interactor in the solution and test it locally. All tests for this problem are just trees with random-shuffled vertex indices (there are no any special cases). So it doesn't seem you "tried many many ways".
•  » » » » » 9 месяцев назад, # ^ |   0 That's because I make too many queries then I get a wrong answer,but i have no idea how to reduce the query though I know my ways can restore the tree.
•  » » » » » » 9 месяцев назад, # ^ |   0 SpoilerSo you have leaf1 and leaf2 (leaf1-leaf2 is a diameter), find the root, divide all vertices into two sets: the ones which are closer to leaf1 and to leaf2. When you go deeper in recursion, the distances from leaf1 and leaf2 can be reused, since they are still leaves in the subtrees (it's done automatically if you cache the distances).
•  » » » » » » » 9 месяцев назад, # ^ |   0 I got it. Thanks a lot.
 » 10 месяцев назад, # |   0 What's test 22 on H ?
•  » » 10 месяцев назад, # ^ |   +9 Test 22 generatorn = 5000; m = 40; d = 5; a.assign(n, string(m, '.')); a[0][m/4] = 'S'; a[0][m/2] = 'M'; a[0][3*m/4] = 'F'; for (int i = d + 1; i < n - d - 1; i++) { for (int j = d + 1; j < m - d - 1; j++) { a[i][j] = 'M'; } } 
 » 10 месяцев назад, # |   +29 The game .C.O.N.T.E.S.T: Unexpected Behaviour from Problem K "Video Reviews" does not exist. But recently our gamedev team Veslo Games released the game .T.E.S.T: Expected Behaviour (from creator of Codeforces Simulator!) to the Steam Early Access. If you like puzzles, consider checking this out!
 » 10 месяцев назад, # |   0 is there a algorithm about problem M？or it's just a simulation？
•  » » 10 месяцев назад, # ^ |   0 Spoiler, MJust bruteforce. Try to set all letters on all critical positions (there are no more than 3 of them).I thought it's like 4th or 5th easiest problem in the contest. But everyone gets stuck.
 » 10 месяцев назад, # | ← Rev. 2 →   0 Can any body help me for problem C ?? I can not find the algorithm. And Why (2 _ 1 5 ) is a wrong answer on test_case 1 for problem C.
 » 9 месяцев назад, # |   0 could anybody help me with the problom I, I can't pass the test 5
•  » » 9 месяцев назад, # ^ |   0 This test has n = 7 and random-shuffled vertices.
•  » » » 9 месяцев назад, # ^ |   0 thanks a lot,but i'm stuck in test 12 now, trust me,i will figure it out :( lol
 » 9 месяцев назад, # |   0 I am stuck on problem H 8-th test . Can I see the case I'm failing ?
•  » » 9 месяцев назад, # ^ |   0 Test Case 81 3 0MSFJury's Answer: 1
•  » » » 9 месяцев назад, # ^ |   0 Thanks
 » 9 месяцев назад, # |   0 Существует ли разбор контеста?
 » 9 месяцев назад, # |   0 Can anyone provide any hints for problem K ,video reviews? thanks.
•  » » 9 месяцев назад, # ^ |   0 Main hint: binary search
•  » » » 9 месяцев назад, # ^ |   0 thanks for replying.binary search i figured out but was not able to come up with a predicate.thanks.
•  » » » » 9 месяцев назад, # ^ |   0 Suppose we have X, and we need to check if X is enough to get m reviews. You need to process the bloggers from left to right. There are two options: blogger is already interested in the game — just increase reviews count blogger isn't interested in the game — you need to convince him (if already convienced count < X) and increase reviews count. It can be easily proven that greedy algorithm works.
 » 9 месяцев назад, # |   0 Can someone knows what is the case 50 for problem F?Thanks
 » 9 месяцев назад, # |   0 What is the test case 50 in problem F? I got stucked there :(
•  » » 9 месяцев назад, # ^ |   0 F, test 48Generate random tree, generate input for the problem, remove one number from one of the lists F, test 50Generate random tree, generate input for the problem, add one number to one of the lists
•  » » » 9 месяцев назад, # ^ |   0 Thanks, I don't know why my aproach was wrong. At the end I changed my strategy and get AC.Do you have any hint for problem D? I belive that a maxflow algorithm could said if it is possible or not, but I can't construct the solution
•  » » » » 9 месяцев назад, # ^ | ← Rev. 2 →   0 Certificate in DI'll just leave an example. Let's say you need to exchange player 1 with player 6, and you have a path 1->2->3->4->5->6, where players 1 and 4 are in your team. Then we'll do two sequences of exchanges: the first is (4, 5) and (5, 6), and the second is (1, 2), (2, 3) and (3, 4). Now players 4 and 6 are in your team.
 » 9 месяцев назад, # |   0 What is the test case 52 in problem F? I got stucked there.
•  » » 9 месяцев назад, # ^ |   0 The same as test 48 (see my comment above), but with different random seed
 » 9 месяцев назад, # |   0 What's the approach for 'L — Queries on a String'? My current solution exceeds the memory limit at test 7.
 » 7 месяцев назад, # |   0 Can someone that give hints about questions D, G and I ? I'm stuck on those.
 » 4 месяца назад, # |   0 May I get some help about 112 No. test case of problem No. F ???
•  » » 4 месяца назад, # ^ |   +3 The same as test 48 and 52 (see my comment above), but with different random seed
 » 6 дней назад, # | ← Rev. 2 →   0 Problem H. Safe PathWA on Test Case 124 :( I am stuck.Here's My Code: