| Show all threads Hide all threads Show all messages Hide all messages |
| wa 1,2,3,4 and greedy algo | 👑TIMOFEY👑 | 1721. Two Sides of the Same Coin | 3 Jul 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. Two Sides of the Same Coin | 16 Mar 2022 17:38 | 1 |
The man texted "anything" can only do one work |
| Greedy solution | Programmer | 1721. Two Sides of the Same Coin | 21 Nov 2015 14:02 | 1 |
Why simple greedy algo: take two people with minimal rank - is not work |
| Help with algo please | Grigor Gevorgian | 1721. Two Sides of the Same Coin | 22 Sep 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. Two Sides of the Same Coin | 20 Jul 2015 13:25 | 2 |
wa3 Fyodor Menshikov 31 Oct 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 Jul 2015 13:25 My solution got wa1 because of this)) |
| WA14 | sherbina_evgeniy | 1721. Two Sides of the Same Coin | 17 Jul 2015 23:34 | 1 |
WA14 sherbina_evgeniy 17 Jul 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. Two Sides of the Same Coin | 12 Dec 2014 15:41 | 1 |
WA5 Michael Uskov [USU] 12 Dec 2014 15:41 Could you give me some tests please? |
| About the statement of the problem | Churchill | 1721. Two Sides of the Same Coin | 11 Dec 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. Two Sides of the Same Coin | 3 Aug 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. Two Sides of the Same Coin | 10 Oct 2009 16:02 | 1 |
WA 2 McArchuk 10 Oct 2009 16:02 I use greedy.
Is this rigth?
Give me some tests. |
