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

Автор MrPaul_TUser, история, 5 лет назад, перевод, По-русски

1593A - Выборы

Идея: MikeMirzayanov

Разбор
Решение

1593B - Делись на 25!

Идея: MikeMirzayanov

Разбор
Решение

1593C - Спасти больше мышек

Идея: коллектив студентов ИТМО

Разбор
Решение

1593D1 - Все одинаковые

Идея: MikeMirzayanov

Разбор
Решение

1593D2 - Половина одинаковых

Идея: MikeMirzayanov

Разбор
Решение

1593E - Садовник и дерево

Идея: MikeMirzayanov

Разбор
Решение

1593F - Красно-чёрное число

Идея: MikeMirzayanov

Разбор
Решение

1593G - Меняя скобки

Идея: nastya_ka

Разбор
Решение
Разбор задач Codeforces Round 748 (Div. 3)
  • Проголосовать: нравится
  • +54
  • Проголосовать: не нравится

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain the solution to F pls

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

d2 is really intresting.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

It seems that in the tutorial for A, the answer should be max(0, max(b,c) + 1 — a) (as in the solution code), instead of min(0, max(b,c) + 1 — a).

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +16 Проголосовать: не нравится

We don't need that extra array to recover answer string. We can store masks in DP and recover the answer from that. Submission with comments : 131983798

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Your dp is so messy.(F) -__-
Good problemset btw.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
»
5 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

For the E problem, will the standard graph bfs not work? I pushed all the leaves ( adjacency list size == 1 ) to a queue and assigned them a distance of 1 ( distance = number of times the operation has to be performed to cut off that node ). Then I performed a bfs assigning increasing distance. Answer is simply all the nodes whose distance is greater than k. This is failing though. Please if somebody could help me out. Thanks in advance

https://codeforces.me/contest/1593/submission/132264294

UPD : I changed the visited logic to an in-degree logic while preserving the bfs (AC : 132341078). Hope somebody finds this helpful. Thank you dedsec_29

»
5 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится
  • Can Someone help with the time complexity of this code: https://codeforces.me/contest/1593/submission/132395142 for problem D2.
  • I have used dp table for calculating the maximum gcd possible when I consider exactly n/2 numbers( because I have to make atleast half elements equal)
  • dp[i][cnt][last] stores set of GCDs that are possible after considering cnt number of elements upto ith position in the array with index of previous selected element as last.
  • It got submitted with 15ms runtime. According to me, the time complexity of this code is O(n^5 * (log(max(Ai)) + log(n))). I want to know whether I am wrong with the time complexity or test cases are not strong enough !
Reason behind asking this question
»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Did anyone solve F using meet in the middle idea ?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

My idea for E was to look at one diameter of the tree and take a middle point in that diameter. After that i root the tree in this middle point and after that it's easy but unfortunately i got memory limit exceeded. Is this idea works?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

CAN F QUESTION DE DONE USING MEET INT THE MIDDLE?

»
5 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

deleted

»
3 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Can anycody give a counter case in which this approach fails for the problem E (link to problem)? I am not able to think about a counter case thanks Submission

»
11 месяцев назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Ignore. Found an approach in preceding comments.

»
6 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

i dont understand the solution for B , can someone please explain it to me?