ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1651. Кратчайшая подцепь

Страницы: 1 2 Следующая
WA test 7
Послано A.Z 1 ноя 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 ноя 2008 14:14
You have.
Re: WA test 7
Послано A.Z 1 ноя 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 ноя 2008 14:27
Yes after the contest is finished ;-)
Re: WA test 7
Послано A.Z 1 ноя 2008 14:39
thnx! ;-)
Re: WA test 7
Послано Ali 1 ноя 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 ноя 2008 00:35
Can you share tests now? I also want to know, what was in the 7th test:)
Re: WA test 7
Послано Piratek-(akaDK) 2 ноя 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 ноя 2008 10:24
my answer is 1 2 6 7,I think it's right,but still Wa test 7
Re: WA test 7
Послано hywei 2 ноя 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
Послано Piratek-(akaDK) 2 ноя 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 ноя 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 ноя 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 ноя 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 2 ноя 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 ноя 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: .....
Послано bright 3 ноя 2008 00:29
thanks
Re: .....
Послано svr 3 ноя 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
Послано AlMag(VNTU) 4 ноя 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 ноя 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
Страницы: 1 2 Следующая