| ENG RUS | Timus Online Judge |
Обсуждение задачи 1544. Одноклассники 3198808xc To admin: please fix the problem statement. [1] // Задача 1544. Одноклассники 3 11 окт 2010 00:25 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. Walker Re: To admin: please fix the problem statement. // Задача 1544. Одноклассники 3 18 авг 2021 06:36 I think you can do on every computers.But doing on the same computer is the best solution. Maybe. Sorry my bad English.:) Joseph Puh the Battle Bear Proof of bfs-with-min-depth solution // Задача 1544. Одноклассники 3 8 авг 2011 12:09 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 Light gg [7] // Задача 1544. Одноклассники 3 21 апр 2007 16:43 to Crocodiles Prishlite kod zada4i na light@bti.secna.ru posle sorevnovaniya zaranee spasibo Light Re: gg [6] // Задача 1544. Одноклассники 3 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?? Laise Re: gg [4] // Задача 1544. Одноклассники 3 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 ;) wubin_s1 Re: gg // Задача 1544. Одноклассники 3 23 апр 2007 08:06 why?we may change some computers at a time. Tiberiu-Lucian Florea Re: gg // Задача 1544. Одноклассники 3 23 апр 2007 16:01 what's the point if you give the solution in the forums ? Eldar Bogdanov Re: gg // Задача 1544. Одноклассники 3 8 ноя 2007 12:25 -- Edited by author 21.05.2008 03:15 svr Re: gg // Задача 1544. Одноклассники 3 20 июн 2009 10:50 Indeed! Great! How it can be seen during contest(or what easy way to understand it). alp Re: gg // Задача 1544. Одноклассники 3 31 май 2011 09:20 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 AlMag Read this, please! (+) [2] // Задача 1544. Одноклассники 3 22 апр 2007 22:02 "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? [bsu] LuPoVo Re: Read this, please! (+) [1] // Задача 1544. Одноклассники 3 18 июн 2007 02:17 it is wrong because 3 2 J E J 1 2 2 3 is answer 1 2 J alp Re: Read this, please! (+) // Задача 1544. Одноклассники 3 23 май 2011 11:07 Why not 1 1 E ? Edited by author 23.05.2011 11:07 I think.... Edited by author 23.05.2011 11:17 Evo idea // Задача 1544. Одноклассники 3 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 ilyamit Help with idea of the decision of a task and with the fifth test. [2] // Задача 1544. Одноклассники 3 21 окт 2007 18:03 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. ilyamit ___Help with idea of the decision of a task and with the fifth test. [1] // Задача 1544. Одноклассники 3 21 окт 2007 18:06 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. Denis Koshman Re: ___Help with idea of the decision of a task and with the fifth test. // Задача 1544. Одноклассники 3 10 авг 2008 12:38 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 elmariachi1414 (TNU) What's the answer for this test? [1] // Задача 1544. Одноклассники 3 14 июн 2007 03:29 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 Pskov SPI 2 ~ Roman Dvoinev Re: What's the answer for this test? // Задача 1544. Одноклассники 3 19 сен 2007 02:17 It is an incorrrect test. Read problem statement carefully. There always exists a path between any 2 computers
|