ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1580. Dean's Debts

How about case M>N(+)?
Posted by SPIRiT 29 Oct 2007 23:18
I think it's clear for the system of linear equations, that if M<N, than it's impossible. If M=N then it may be possible (and I know how to check). How about case M>N? We need to select N pairs that get an unambiguous solution?
Re: How about case M>N(+)?
Posted by Alexander Georgiev 15 Feb 2008 17:40
You have to keep only the lineary independet ones, I think.
What I did is I kept only the first 5 ones, which contain certain number (so the matrix in the end was at most 5000 rows long, containing at least 5 rows, containing a digit at each position) and it passed system test (otherwise the solution was right, but too slow)
Re: How about case M>N(+)?
Posted by Denis Koshman 19 Aug 2008 19:57
Just find at least one odd loop in each connected component
Re: How about case M>N(+)?
Posted by test 24 Apr 2010 20:49
Denis Koshman wrote 19 August 2008 19:57
Just find at least one odd loop in each connected component

hmm i make this but i get TLE( test 12)... (with a BFS) any ideea why?
Re: How about case M>N(+)?
Posted by ARK (***AESC_USU***) 20 Jan 2018 04:29
Alexander Georgiev wrote 15 February 2008 17:40
What I did is I kept only the first 5 ones, which contain certain number
Strange. It will not work for this test (A_i can be arbitrary).

43 43
2 3 0
1 2 0
1 3 0
1 4 0
1 5 0
1 6 0
1 7 0
2 8 0
2 9 0
2 10 0
2 11 0
2 12 0
2 13 0
3 14 0
3 15 0
3 16 0
3 17 0
3 18 0
3 19 0
4 20 0
4 21 0
4 22 0
4 23 0
4 24 0
4 25 0
5 26 0
5 27 0
5 28 0
5 29 0
5 30 0
5 31 0
6 32 0
6 33 0
6 34 0
6 35 0
6 36 0
6 37 0
7 38 0
7 39 0
7 40 0
7 41 0
7 42 0
7 43 0

Edited by author 20.01.2018 04:30