Discussion @ 1651. Shortest Subchain @ Timus Online Judge

WA test 7 A.Z 1 Nov 2008 14:09

what's is the wrong with this solution ?: i find the shortest path from the first vertx in the chain to the last ( with bfs) an print that path.i read my code , and I think it's correct ,say if I misunderstood the problem

Re: WA test 7 LSBG 1 Nov 2008 14:14

You have.

Re: WA test 7 A.Z 1 Nov 2008 14:26

I can not understand any thing else that I said , I read the problem description many times !!
    * the initial and final vertices of the chains p and q coincide;
    * the edges in the chain q are in the same order as in the chain p;
    * the chain q has the minimal possible number of edges under the given conditions.

means that , it should be a path from first vertex to last ,and should use only the chains edges and should be minimal . so is the shortest path between first and last!!
could you pleas give me a test, that my algorithm crashs?

Re: WA test 7 LSBG 1 Nov 2008 14:27

Yes after the contest is finished ;-)

Re: WA test 7 A.Z 1 Nov 2008 14:39

thnx! ;-)

Re: WA test 7 Ali 1 Nov 2008 15:09

the edges in the chain q are in the same order as in the chain p;

BFS breaks this rule

Re: WA test 7 Lyceum BSU#0 2 Nov 2008 00:35

Can you share tests now? I also want to know, what was in the 7th test:)

Re: WA test 7 NickSergeev[MSU MindCraft] 2 Nov 2008 01:00

something like that

13
1 2 3 4 5 6 7 6 2 6 8 9 7

Re: WA test 7 hywei 2 Nov 2008 10:24

my answer is 1 2 6 7,I think it's right,but still Wa test 7

Re: WA test 7 Avtandil Gokadze 11 Jul 2012 20:54

Edited by author 11.07.2012 20:55

Edited by author 11.07.2012 20:55

Edited by author 03.04.2013 23:29

Re: WA test 7 Birne Ageev 11 Jul 2012 21:30

Right answer for
15
1 2 3 4 5
6 7 6 2 5
2 8 9 10 7
is
1 2 8 9 10 7

No subject __Andrewy__ 10 Oct 2015 23:45

Edited by author 27.01.2016 19:11

Re: WA test 7 __Andrewy__ 10 Oct 2015 23:45

Edited by author 27.01.2016 19:11

Re: WA test 7 Alex Fetisov 29 Nov 2015 09:14

That is not right. Edges should be in the same order as the initial path. In your answer edges are not in the same order. Here is the right one: [1 2 8 9 10 7]

Re: WA test 7 hywei 2 Nov 2008 11:10

try this test
17
1 2 3 4 5 6 7 2 8 9 5 10 8 9 11 3 9

Re: WA test 7 NickSergeev[MSU MindCraft] 2 Nov 2008 11:12

1 2 6 7 - is not correct answer check yourself
1 2 6 8 9 7 - correct

Re: WA test 7 Crash_access_violation 2 Nov 2008 12:02

to Piratek-(akaDK) : Please said me why 1 2 8 9 is not correct? thx

Re: WA test 7 Ulyanovsk STU - Alex Erofeev 2 Nov 2008 13:21

My program says
1 2 8 9
for
17
1 2 3 4 5 6 7 2 8 9 5 10 8 9 11 3 9

and
1 2 6 8 9 7
for
13
1 2 3 4 5 6 7 6 2 6 8 9 7

both answers seem correct, but i'm still getting WA7. What is the problem with it?

Re: WA test 7 Infinity. 2 Nov 2008 15:59

This test helped me to pass 7
13
1 2 3 4 5 6 7 3 6 11 12 10 7
(1 2 3 4 5 6 7)
However, I got WA 12 :-(

Then I invented this one
15
1 2 3 12 4 5 6 7 3 6 11 12 10 7 6
(1 2 3 6)
And finally got AC..

..... Noob 2 Nov 2008 18:01

13
1 2 3 4 5 6 7 6 2 6 8 9 7

Why not (1 2 6 7) ??

Re: ..... Aram Shatakhtsyan 2 Nov 2008 23:41

For input
13
1 2 3 4 5 6 7 6 2 6 8 9 7

the output
1 2 6 7
is wrong, because here edge (6,7) comes after (2,6),
but in input edge (6,7) comes before edge (2,6).

Hint: Don't use BFS, there is a simple O(n) solution,
you don't need to construct graph.

Re: ..... Noob 3 Nov 2008 00:29

thanks

Re: ..... svr 3 Nov 2008 11:49

But if decided to use BFS?
It is important to know:
1. Can vertex be used multiply in BFS search- Yes.
2.Can edge be used multiply in BFS search-Yes.
Thus what objects should we use in BFS constructing
and how avoid loop in BFS.
Good mastering in BFS more important than
cleverness by the chance.
P.S.
Ac with BFS. 18 bad submissions on test 3 were answer: v1-
I think that it is stupid trick. Case v1=v2 should
be processed as common.
BFS:
1)used pair(r1,r2) adjacent edges and r2 after r1 as
object of layers of BFS because this pair can be meet in
searching uniquely. And must use set<pair> to defining
that pair is new.
2) used vector<int> sloi1,sloi2 for layers of BFS
and struct pair data[1000000] as store of all items of BFS.
Time Ac is bad but approach is in standard layout.
After first Ac I had got Tle 17 because of new redjudjement.
Wanted to have Ac throught BFS and no DP.
I recoded BFS radically:
1) foud all states on reading data stage and stored its in
array data[3000000]
2) used char met[3000000] to control uniquness of new states on searchind in BFS
These helped to take AC 0.640c.

Edited by author 08.11.2008 12:55

Re: WA test 7 exwRabbits_AlMag(VNTU) 4 Nov 2008 20:25

Infinity, i've produced correct answer to your test, but WA12 anyway :(

give more tests, please

Re: WA test 7 Infinity. 5 Nov 2008 01:05

I think you have just a bug somewhere.. Because I had. If you've passed 7, the idea seems to be right.. Try to check your code better.. I don't have more good tests

Re: WA test 7 Azrail 29 Nov 2008 08:09

I think test 12 contains something like that:
4
1 2 1 3
At least, such test helps in my WA12 :)

WA#6 Nisarg Shah 2 Dec 2008 12:46

My program works for all the test cases given in this thread, but it is giving WA#6, can you please give me this test case?

Re: WA#6 espr1t 16 Dec 2008 22:00

Mine was wrong because of the test:
17
1 2 12 3 4 7 4 1 5 4 7 8 4 9 10 11 8

(Correct answer is "1 5 4 7 8")

Re: WA#6 NotImplemented 17 Dec 2008 19:05

Can anybody give me test #7?

Edited by author 18.12.2008 20:57

Re: WA#6 NotImplemented 18 Dec 2008 22:26

Please, give me test 7.

a good test erfan 17 Feb 2009 22:53

hello to all i could'nt pass test 7 but i've a good test

9
1 2 3 4 1 3 5 6 4

Re: WA test 7 marat 30 Oct 2011 23:51

Try to use this one for test 12:
13
1 4 5 13 8 6 4 8 17 11 12 8 7
Answer: 1 4 8 7

Discussion of Problem 1651. Shortest Subchain