ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1651. Shortest Subchain

Pages: 1 2 Next
WA test 7
Posted by 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
Posted by LSBG 1 Nov 2008 14:14
You have.
Re: WA test 7
Posted by 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
Posted by LSBG 1 Nov 2008 14:27
Yes after the contest is finished ;-)
Re: WA test 7
Posted by A.Z 1 Nov 2008 14:39
thnx! ;-)
Re: WA test 7
Posted by 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
Posted by 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
Posted by Piratek-(akaDK) 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
Posted by 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
Posted by 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
Posted by Piratek-(akaDK) 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
Posted by 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
Posted by 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
Posted by 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..
.....
Posted by bright 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: .....
Posted by 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: .....
Posted by bright 3 Nov 2008 00:29
thanks
Re: .....
Posted by 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.
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
Posted by AlMag(VNTU) 4 Nov 2008 20:25
Infinity, i've produced correct answer to your test, but  WA12 anyway :(