Разбор Технокубок 2017 — Отборочный Раунд 1

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

Автор fcspartakm, история, 10 лет назад, По-русски

Tutorial is loading...

Разбор задач Технокубок 2017 - Отборочный Раунд 1

editorial, technocup, 2017, elimination

fcspartakm
10 лет назад
9

Комментарии (9)

Написать комментарий?

Diplomate

10 лет назад, скрыть # |

Добавьте ссылку на разбор в соревнование.

→ Ответить

rachitiitr

10 лет назад, скрыть # |

First of all, I didn't even come to know when this editorial came.
In D, there was the constraint "Each person needs S or M, M or L, L or XL" and so on.
I was wondering how to solve D if this constraint is removed. I was trying to maintain what all people are left with just a SINGLE choice, so I have no option but to give them the t-shirt of their choice, and on doing so, find new people that are left with single choice.
Ofcourse, this can stop mid-way, and we would be left with people having exactly two choices. But I couldn't analyse how to proceed ahead. My failed attempt

→ Ответить

I_Love_Tina

10 лет назад, скрыть # ^ |

← Rev. 2 →

You can just build a network and run max flow on it and it will pass since the graph is special.

→ Ответить

rachitiitr

10 лет назад, скрыть # ^ |

That's cool. Then I guess this problem from last contest is also basically the same but with cost assigned to each edge.(MinCostMaxFLow) I am new to the concept of max flow, but let me know whether I am thinking correct or not. Also can you share some AC codes on CF/CC where you used MaxFlow and MinCostMaxFlow because I am not able to find a good template for them.

→ Ответить

I_Love_Tina

10 лет назад, скрыть # ^ |

Try this.My solution 17710740.

→ Ответить

rachitiitr

10 лет назад, скрыть # ^ |

Your implementation is not the fastest right? So instead of adjacency matrix, i should implement it with vectors and that would be the best code in terms of time complexity?

→ Ответить