Discussion @ 1041. Nikifor @ Timus Online Judge

Sema Greedy algo [6] // Problem 1041. Nikifor 21 Jan 2007 15:15

Why is greedy algo get's WA on test 9?

svr Re: Greedy algo [5] // Problem 1041. Nikifor 21 Jan 2007 21:51

Because better use integer- Gauss solution without
heuristics.

ftc Re: Greedy algo // Problem 1041. Nikifor 21 Jan 2007 23:58

My algorithm uses Gauss algo as a part, but also gets WA on test 9. I think this problem is similar to minimal spanning tree problem, which is solved by Kruskal's algo, but here we should use Gauss to check linear independence. So, greedy (in fact) algo could get AC. May be you know counter-example?

Sema Re: Greedy algo [3] // Problem 1041. Nikifor 22 Jan 2007 09:46

I'm using Gauss method with precision about 50 digits (BigDecimal) and still get WA? Can you give me some test, where it doesn't works

svr Re: Greedy algo [2] // Problem 1041. Nikifor 22 Jan 2007 10:54

You should make Gauss under ring of integers
when we make matrix diagonal but don,t make ones on it

ftc Re: Greedy algo // Problem 1041. Nikifor 22 Jan 2007 18:35

I did exactly what you mean but i think, that there should be an overflow when you several times will use Gauss algo. Now i have WA9, can you give me any tricky test?

ftc Re: Greedy algo // Problem 1041. Nikifor 22 Jan 2007 18:35

Silly mistake, AC now.

Edited by author 22.01.2007 18:54

Discussion of Problem 1041. Nikifor