|
|
| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | | To admin: please fix the problem statement. | 198808xc | 1544. Одноклассники 3 | 18 авг 2021 06:36 | 2 | In this problem, all the operations should be done on the SAME computer, but I could NOT understand this from the statement, until I read the forum.
This problem is quite easy: simple bruteforce could AC in short time, but I think this bug in statement have made this problem SEEMS hard (only 100+ ACed now).
Please, fix it. I think you can do on every computers.But doing on the same computer is the best solution.
Maybe.
Sorry my bad English.:) | | Proof of bfs-with-min-depth solution | Joseph Puh the Battle Bear | 1544. Одноклассники 3 | 8 авг 2011 12:09 | 1 | We can iterate through vertexes and choose one with smallest bfs-depth... How i can proove that it is correct?
Edited by author 08.08.2011 12:09 | | gg | Light | 1544. Одноклассники 3 | 31 май 2011 09:20 | 8 | gg Light 21 апр 2007 16:43 to Crocodiles
Prishlite kod zada4i na light@bti.secna.ru posle sorevnovaniya
zaranee spasibo Re: gg Light 21 апр 2007 20:49 parni, pomogite, ya reshal zada4u putem nahozhdeniya nesvyazannih grup v grafe, i potom sravnival koli4estva E i J grup. 4to ya upustil?? Re: gg Laise 22 апр 2007 20:07 to solve this task you would try to change all protocols using only one computer!!! so calculate number of steps needed to do that from each of computers, and print the best way ;) Re: gg wubin_s1 23 апр 2007 08:06 why?we may change some computers at a time. Re: gg Tiberiu-Lucian Florea 23 апр 2007 16:01 what's the point if you give the solution in the forums ? Re: gg Eldar Bogdanov 8 ноя 2007 12:25 --
Edited by author 21.05.2008 03:15 Indeed!
Great!
How it can be seen during contest(or what easy way to understand it). Try with test
7 6
E J E J E J E
1 2
2 3
1 4
4 5
1 6
6 7
Answer
2
1 J
1 E | | Read this, please! (+) | AlMag | 1544. Одноклассники 3 | 23 май 2011 11:07 | 3 | "It is known that all computers in the class are connected to each other directly or via other computers."
So, there must be just one group of cumputers, in wich we can move from any one to any other...
I thought, that we can just cange first pupil's computer to get the answer. Where is a mistake in my thoughts? it is wrong because
3 2
J E J
1 2
2 3
is answer
1
2 J Why not
1
1 E
?
Edited by author 23.05.2011 11:07
I think....
Edited by author 23.05.2011 11:17 | | idea | Evo | 1544. Одноклассники 3 | 15 июн 2009 19:10 | 1 | idea Evo 15 июн 2009 19:10 I have find my bug,and AC now!
Just try to find a start point,and then bfs,find the minimum depth.
Edited by author 15.06.2009 19:18 | | Help with idea of the decision of a task and with the fifth test. | ilyamit | 1544. Одноклассники 3 | 10 авг 2008 12:38 | 3 | Excuse me for my bad English.
My idea of the decision: On each step we find a component with the greatest amount of the components of other color connected with it and we paint it. And so until then while all tops do not make one component.
The component is a set of tops between which it is possible to spend a way which is not passing on edges, connecting tops of different color.
Components are considered coherent if between any two tops taken from first and second will connect a way which is passing only through one edge, connecting multi-coloured tops. Such edges I named heavy.
In realization it is ideas it is possible to use procedure of convolution the column, that is turns off a component in one top.
I cannot think up the test on which this decision gives the incorrect answer. Realization of the decision passes 4 tests (((. On the fifth Crash. ((
Tell please that in my idea incorrectly. Thanking you very much in advance. Dlya vseh kto ploho znaet angliiskii:
Pomogite s ideey resheniya zadachi i s pyatym testom.
Moya ideya resheniya:
Na kajdom shage nahodim komponent s naibol'shim kolichestvom svyazannyh s nim komponentov drugogo cveta i krasim ego. I tak do teh por poka vse vershiny ne sostavlyayut odin komponent.
Komponent - eto mnojestvo vershin mejdu kotorymi mojno provodit' put', ne prohodyaschiy po rebram, soedinyayuschim vershiny raznogo cveta.
Komponenty schitayutsya svyaznymi, esli mejdu lyubye dve vershiny, vzyatye iz pervogo i vtorogo budet soedinyat' put', prohodyaschiy tol'ko cherez odno rebro, soedinyayuschee raznocvetnye vershiny. Takie rebra ya nazyval tyajelymi.
V realizacii eto idei mojno ispol'zovat' proceduru svertki grafa, to est' svorachivaet komponent v odnu vershinu.
Ya ne mogu pridumat' test, na kotorom eto reshenie daet nevernyy otvet. Realizaciya resheniya prohodit 4 testa(((. na pyatom Crash.((
Skajite pojaluysta chto v moey idee neverno. Zaranee blagodaryu. I failed WA5 when I used wrong variable for the output of vertex node. Your idea was first that came into my head, but it's wrong...
Try this test:
11 10
J E E J J J J J J J J
1 2
1 3
2 4
2 5
2 6
2 7
3 8
3 9
3 10
3 11
The answer is 2, but your degree-greedy algo will give 3 | | What's the answer for this test? | elmariachi1414 (TNU) | 1544. Одноклассники 3 | 19 сен 2007 02:17 | 2 | 8 4
J J E J J E E E
1 2
2 3
3 4
4 5
Anser is
2
3 J
3 E
???
Thanks It is an incorrrect test. Read problem statement carefully. There always exists a path between any 2 computers |
|
|
|
