Discussion @ 1651. Shortest Subchain @ Timus Online Judge

A.Z WA test 7 [31] // Problem 1651. Shortest Subchain 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

LSBG Re: WA test 7 [12] // Problem 1651. Shortest Subchain 1 Nov 2008 14:14

You have.

A.Z Re: WA test 7 [11] // Problem 1651. Shortest Subchain 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?

LSBG Re: WA test 7 [10] // Problem 1651. Shortest Subchain 1 Nov 2008 14:27

Yes after the contest is finished ;-)

A.Z Re: WA test 7 [1] // Problem 1651. Shortest Subchain 1 Nov 2008 14:39

thnx! ;-)

Ali Re: WA test 7 // Problem 1651. Shortest Subchain 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

Lyceum BSU#0 Re: WA test 7 [7] // Problem 1651. Shortest Subchain 2 Nov 2008 00:35

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

Piratek-(akaDK) Re: WA test 7 [1] // Problem 1651. Shortest Subchain 2 Nov 2008 01:00

something like that

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

hywei Re: WA test 7 // Problem 1651. Shortest Subchain 2 Nov 2008 10:24

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

goqadze Re: WA test 7 [4] // Problem 1651. Shortest Subchain 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

Birne Ageev [USU] Re: WA test 7 [3] // Problem 1651. Shortest Subchain 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

Felix_Mate No subject // Problem 1651. Shortest Subchain 10 Oct 2015 23:45

Edited by author 27.01.2016 19:11

Felix_Mate Re: WA test 7 [1] // Problem 1651. Shortest Subchain 10 Oct 2015 23:45

Edited by author 27.01.2016 19:11

Fetisov Alex [XZ Team] Re: WA test 7 // Problem 1651. Shortest Subchain 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]

hywei Re: WA test 7 [17] // Problem 1651. Shortest Subchain 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

Piratek-(akaDK) Re: WA test 7 [1] // Problem 1651. Shortest Subchain 2 Nov 2008 11:12

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

Crash_access_violation Re: WA test 7 // Problem 1651. Shortest Subchain 2 Nov 2008 12:02

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

Ulyanovsk STU - Alex Erofeev Re: WA test 7 [14] // Problem 1651. Shortest Subchain 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?

Infinity. Re: WA test 7 [13] // Problem 1651. Shortest Subchain 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..

bright ..... [3] // Problem 1651. Shortest Subchain 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) ??

Aram Shatakhtsyan Re: ..... [2] // Problem 1651. Shortest Subchain 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.

bright Re: ..... [1] // Problem 1651. Shortest Subchain 3 Nov 2008 00:29

thanks

svr Re: ..... // Problem 1651. Shortest Subchain 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

AlMag(VNTU) Re: WA test 7 [8] // Problem 1651. Shortest Subchain 4 Nov 2008 20:25

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

give more tests, please

Infinity. Re: WA test 7 // Problem 1651. Shortest Subchain 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

Azrail Re: WA test 7 [6] // Problem 1651. Shortest Subchain 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 :)

Nisarg Shah WA#6 [4] // Problem 1651. Shortest Subchain 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?

Alexander Georgiev Re: WA#6 [3] // Problem 1651. Shortest Subchain 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")

NotImplemented Re: WA#6 [2] // Problem 1651. Shortest Subchain 17 Dec 2008 19:05

Can anybody give me test #7?

Edited by author 18.12.2008 20:57

NotImplemented Re: WA#6 [1] // Problem 1651. Shortest Subchain 18 Dec 2008 22:26

Please, give me test 7.

erfan a good test // Problem 1651. Shortest Subchain 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

marat Re: WA test 7 // Problem 1651. Shortest Subchain 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