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

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

1660A - Вася и монеты

Идея: MikeMirzayanov

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

1660B - Влад и конфеты

Идея: Vladosiya

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

1660C - Получи четную строку

Идея: MikeMirzayanov

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

1660D - Максимальное произведение наносит ответный удар

Идея: Aris

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

1660E - Матрица и сдвиги

Идея: myav, MikeMirzayanov

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

1660F1 - Перспективные подстроки (простая версия)

Идея: MikeMirzayanov

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

1660F2 - Перспективные подстроки (сложная версия)

Идея: MikeMirzayanov

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

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

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table to increase/decrease the constraints.

I've also added a new feature to view progress of your judgement in near real-time. (For example, the current state of your ticket, how many inputs were evaluated, etc).

If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.

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

There is a solution in the f2 order_set or fenw_tree.This is awesome

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

Can anyone please point out for me the difference between these two submissions:

152864441(I used vector and got WA)

152864364 (I used array and got AC)

Thanks in advance!!!

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

Does the solution of F1 take into account the adjacent situation?

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

How can I solve C. Get an Even String with dp ?

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

    To solve 1660C with DP we should start by finding the recursive solution: for each i in the strings there are 2 options: I either remove the current element, or I remove elements until I reach the next occurrence of this character in the string (if there is any). We recur on both options and take the minimum result.

    The naive approach to finding out how many elements are until current element and next occurrence of character is a simple linear scan. We can speed it up by a LOT by first scanning the string and then storing the positions of the characters in the string in a vector<set<int>> pos(26), where index stores the character type, and the elements in the set store the indexes where this element occurs.

    After that simple (but most likely necessary) optimization, we can notice one thing: if I happen to be in the same index again, the best solution is going to be the same! So I simply store it in a memo vector.

    This is my submission for additional clarity: 163585297

    It's gonna be pretty simple translating it to a simple iterative bottom-up approach! This exercise is left for you.

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

I think there is a mistake in tutorial for problem C. Instead of used it should be prev.