| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| wa 1,2,3,4 and greedy algo | 👑TIMOFEY👑 | 1721. Две стороны одной монеты | 3 июл 2023 09:55 | 1 |
why greedy with catching two mins dont work
pseydotests:
#1:
test
test, universal
base
#2:
universal, base
base, universal
#3:
universal
base
test
universal |
| Be Careful | DarksideCoder | 1721. Две стороны одной монеты | 16 мар 2022 17:38 | 1 |
The man texted "anything" can only do one work |
| Greedy solution | Programmer | 1721. Две стороны одной монеты | 21 ноя 2015 14:02 | 1 |
Why simple greedy algo: take two people with minimal rank - is not work |
| Help with algo please | Grigor Gevorgian | 1721. Две стороны одной монеты | 22 сен 2015 01:30 | 11 |
How to solve this problem ? Flow seems not enough because of the vertexes of "anything" type. Flow can solve it but there's a better way in fact.
Edited by author 11.10.2009 21:40 Could you tell me, please, how to construct the graph for a flow ? you should construct bipartite graph.
for example , you have people with ranks:
2 4 6 8 10
2 , 6 , 10 - to the left side
4 , 8 - to the right side I tried to use Kuhn (max pair-combination), but get WA#11. And don't know, what to do next... You always can put all the people with skill < 2 (modulo 4) to the left part and all the people with skill >= 2 (modulo 4) to the right. Definitely, all the edges will connect vertices from different parts, so this graph will be bipartite. My algo is O(n^3),but it got TLE 11!
What is right algo here? My algo is O(n^2*m) and AC in 0.093
It is standart bipartite matching algo My algo is O(n^2*m) and AC in 0.093
It is standart bipartite matching algo I was use Hopcroft_Karp algo (from wiki) and AC. 0.031 s. You always can put all the people with skill < 2 (modulo 4) to the left part and all the people with skill >= 2 (modulo 4) to the right. Definitely, all the edges will connect vertices from different parts, so this graph will be bipartite. But why will the maximum match in this graph will be answer to the problem? I used a Hopcroft-Karp algorithm to solve this problem and got AC in 31 ms. So, not bad :) |
| wa3 | Fyodor Menshikov | 1721. Две стороны одной монеты | 20 июл 2015 13:25 | 2 |
wa3 Fyodor Menshikov 31 окт 2010 01:44 Pairs in output should be ordered: in each pair first the name of a person writing the statement and then the name of a person preparing the tests.
Solution printing unordered pairs gets wa3. Re: wa3 Zakharov Konstantin 20 июл 2015 13:25 My solution got wa1 because of this)) |
| WA14 | sherbina_evgeniy | 1721. Две стороны одной монеты | 17 июл 2015 23:34 | 1 |
WA14 sherbina_evgeniy 17 июл 2015 23:34 I got WA 14. I don't understand why? Please give me some tests or explain where is my mistake. |
| WA5 | Michael Uskov [USU] | 1721. Две стороны одной монеты | 12 дек 2014 15:41 | 1 |
WA5 Michael Uskov [USU] 12 дек 2014 15:41 Could you give me some tests please? |
| About the statement of the problem | Churchill | 1721. Две стороны одной монеты | 11 дек 2014 13:19 | 2 |
Can there be two persons that have the same Specialization and the same rank?? No, difference between two ranks should be equal 2 |
| Can anyone help me shortening this problem statement ? | ConanKudo | 1721. Две стороны одной монеты | 3 авг 2010 23:15 | 2 |
Can anyone tell me what does the problem say in short ?
This problem is too long to read...-.-" Just read only two last paragraphs of statement. |
| WA 2 | McArchuk | 1721. Две стороны одной монеты | 10 окт 2009 16:02 | 1 |
WA 2 McArchuk 10 окт 2009 16:02 I use greedy.
Is this rigth?
Give me some tests. |
