| ENG RUS | Timus Online Judge |
Discussion of Problem 1129. Door PaintingКонобейцев Иван Олегович Some tests // Problem 1129. Door Painting 15 Sep 2022 09:36 4 2 2 3 2 1 3 3 1 2 4 1 3 6 5 2 3 4 5 6 5 1 3 4 5 6 5 1 2 4 5 6 5 1 2 3 5 6 5 1 2 3 4 6 5 1 2 3 4 5 8 7 2 3 4 5 6 7 8 7 1 3 4 5 6 7 8 7 1 2 4 5 6 7 8 7 1 2 3 5 6 7 8 7 1 2 3 4 6 7 8 7 1 2 3 4 5 7 8 7 1 2 3 4 5 6 8 7 1 2 3 4 5 6 7 6 2 2 3 2 1 3 2 1 2 2 5 6 2 4 6 2 4 5 Felix_Mate Idea // Problem 1129. Door Painting 27 Aug 2015 15:36 My algo works O(N^3) at 0.015 sec. Solution always exist. Idea: We must paint first half of edge in 'Y' and second half in 'G'. 1)Delete cycles (if the edge belongs to the cycle then we delete it from the graph) and paint edges; 2)Paint a tree. Edited by author 27.08.2015 15:36 Piratek-(akaDK) WHAT WRONG WITH TEST 10 [2] // Problem 1129. Door Painting 4 Oct 2007 23:58 I'm looked for cycles. Deleted them. Finally i got some tree without cycles. I think my idea is correct , pass 10 test do not passed/ Help me please??? Denis Koshman Re: WHAT WRONG WITH TEST 10 // Problem 1129. Door Painting 1 Aug 2008 14:39 Why care about cycles? kerpoo Re: WHAT WRONG WITH TEST 10 // Problem 1129. Door Painting 18 Aug 2015 04:35 maybe more than one component! Zayakin Andrey[PermSU] No subject [2] // Problem 1129. Door Painting 19 Feb 2010 00:26 flow can solve this. Edited by author 19.02.2010 16:08 spiker Re: No subject [1] // Problem 1129. Door Painting 21 Jul 2014 16:49 How we can solve this using flow? Some hints? Thanks, Ostap Vedernikoff 'Goryinyich' Sergey (HSE: АОП) Re: No subject // Problem 1129. Door Painting 22 Jul 2014 22:13 OMG! How difficult - flow, it's O(N^3) and lots of code... Let the DFS help you! =) Tigran92[RAU_902] Solution always EXISTS!!! [1] // Problem 1129. Door Painting 20 Nov 2010 00:28 Mikael Re: Solution always EXISTS!!! // Problem 1129. Door Painting 21 Nov 2010 19:12 axper jan.. good that found ... can you send message? vk com/mikaelarakelyan .... sometimes an idea is bad for a solution UdSU: Ajtkulov, Kotegov, Saitov test #5 - Graph is not connectivity [3] // Problem 1129. Door Painting 26 Jun 2006 17:12 Rachel Re: test #5 - Graph is not connectivity [1] // Problem 1129. Door Painting 27 Jan 2008 13:09 Great hint!!! Denis Koshman Re: test #5 - Graph is not connectivity // Problem 1129. Door Painting 1 Aug 2008 14:37 Some algos do not depend on this property nenucs Re: test #5 - Graph is not connectivity // Problem 1129. Door Painting 6 Aug 2010 09:35 3ks!! DWED About Java... [2] // Problem 1129. Door Painting 7 Aug 2008 18:17 Java on this server is EXTREMELY slow! Moreover - it is really strange - don't you ever notice how it gives you "Compilation Error" on @Overriden annotation automatically generated by Eclipse. On maximal set (K100 graph) on my P4 3GHz my last solution works 0.03s, on server it works 5 times longer - 0.17s! Fantastic! Initially on my machine solution worked 0.400s - it is TLE, no words. To make it faster I tried to avoid all collections. I thought "DAMN! They want all programmers to write like with raw C/Pascal". After I've finished, it worked 0.360s - so collections did not a great slowdown. "Output is slow?" I constructed output in StringBuffer, and "viola" - twice speed-up (0.170s). "That's enough" - I thought and got TLE again - now i know about 5x time scale, but then... I switched of my algo and output and found that all time (0.150s) is taken by input. I did input with Scanner class, now it is time to throw it away. Just a simple method for input: >public final static int nextInt() throws IOException { >>InputStream in = System.in; >>int i = in.read() - 48; >>while (i<0) { >>>i = in.read() - 48; >>} >>int ret = i; >>i = in.read() - 48; >>while (i>=0) { >>>ret = (10*ret) + i; >>>i = in.read() - 48; >>} >>return ret; >} "Bingo!" - my solution now works 0.03s. But on server it is 0.03x5=0.15. So BEWARE! [SPbSU ITMO] WiNGeR Re: About Java... // Problem 1129. Door Painting 7 Aug 2008 23:26 I suppose that's because server use JDK1.5, not 1.6 tiancaihb Re: About Java... // Problem 1129. Door Painting 28 Aug 2009 07:22 Maybe their method of calculating Running time is different player To admin [2] // Problem 1129. Door Painting 11 Jul 2009 07:37 Could you check the test 10,please! Thanx player Re: To admin [1] // Problem 1129. Door Painting 11 Jul 2009 07:41 Is it special judge? player Re: To admin // Problem 1129. Door Painting 13 Jul 2009 09:17 I know why i got wrong......... orlando22 Would you like to do me a favor to post me a copy of testing data? // Problem 1129. Door Painting 26 Mar 2009 10:17 Thanks a lot! I need to analyize why my algorithm is wrong!I use forward-star to construct Graph, and Euler circuit algorithm. unfortunately, still the prompt "Wrong answers" pittycat i don't think the numbers of adjacent lodgings follow in ascending order! [1] // Problem 1129. Door Painting 6 Apr 2002 00:47 Because if i use this condition i got WA, if i ignore it(change my program) i got AC. Denis Koshman Re: i don't think the numbers of adjacent lodgings follow in ascending order! // Problem 1129. Door Painting 1 Aug 2008 14:41 I had a trap for that, it didn't signal. So, they ARE ascending. Yu YuanMing I used Greedy and got AC.By the way,why the AC rate is so high? [1] // Problem 1129. Door Painting 5 Jul 2004 13:29 Denis Koshman Re: I used Greedy and got AC.By the way,why the AC rate is so high? // Problem 1129. Door Painting 1 Aug 2008 14:40 If your greed is chain-based, then it's correct Edited by author 01.08.2008 14:40 Piratek-(akaDK) Is that Possible& [1] // Problem 1129. Door Painting 5 Oct 2007 00:01 Может ли быть между двумя комнатами больше чем одна дверь? Denis Koshman Re: Is that Possible& // Problem 1129. Door Painting 1 Aug 2008 14:39 (Can there exist more than 2 doors between rooms?) No because numbers of adjacent rooms are ASCENDING. tyana problem 1129 [4] // Problem 1129. Door Painting 25 Dec 2007 16:58 Whether in a problem 1129 some variants of the answer are possible?? Alias (Alexander Prudaev) Re: problem 1129 [3] // Problem 1129. Door Painting 25 Dec 2007 23:20 Yes, of course tyana Re: problem 1129 [2] // Problem 1129. Door Painting 26 Dec 2007 01:50 In that case my answer will not converge at check. Or here such situations are provided? SuperLight Re: problem 1129 [1] // Problem 1129. Door Painting 26 Dec 2007 14:17 no message Denis Koshman Re: problem 1129 // Problem 1129. Door Painting 1 Aug 2008 14:38 Some checkers are smarter than just identity Nickolas Kakà How to avoid TLE in Test#10? [1] // Problem 1129. Door Painting 12 Jun 2008 21:44 How to avoid TLE in Test#10? Denis Koshman Re: How to avoid TLE in Test#10? // Problem 1129. Door Painting 1 Aug 2008 14:37 Solution is O(M), M - number of doors tyana 1129 // Problem 1129. Door Painting 13 Jan 2008 20:42 You could not send me the test № 3 on my e-mail (tyana_gr@mail.ru), please Edited by author 13.01.2008 20:56 Piratek-(akaDK) Show Test 10 // Problem 1129. Door Painting 6 Oct 2007 01:09 Please send me a test 10 to my email destyon@mail.ru Titan help me pleas writen this programm [2] // Problem 1129. Door Painting 9 Jul 2007 13:03 Laktarugar Re: help me pleas writen this programm // Problem 1129. Door Painting 9 Jul 2007 17:29 #include<iostream.h> const int max = 101; int ke[max][max],color[max][max],mau[max][3]; int n; int fillchar(int mas[max][max],int rosme=max,int k = 0) { int j; for(int i = 1; i<rosme;i++) {for(j = 1; j<rosme;j++) mas[i][j] = k;} return 1; } int fillchar1(int mas[max][3],int rosme=3,int k = 0) { int j; for(int i = 1; i<rosme;i++) {for(j = 1; j<rosme;j++) mas[i][j] = k;} return 1; } //------------------------------------------------------------------------ void input() { int i,j; cin>>n; for (i = 1;i<=n;i++) {cin>>ke[i][0]; for(j=1;j<=ke[i][0];j++) {cin>>ke[i][j]; } } } //----------------------------------------------------------------------- void chonmau(int i,int &t) { if (mau[i][1]>=mau[i][2]) t = 2; else t = 1; } //--------------------------------------------------------------------- void tomau(int i,int j,int t) {int flag = 0; int u,v; do { color[i][j] = t; mau[i][t] = mau[i][t] + 1; u = ke[i][j]; flag = 0; for (v = 1; v<=ke[u][0]; v++) if(ke[u][v] == i ) { flag =1; break;} color[u][v] = 3-t; mau[u][3-t] = mau[u][3-t] +1; flag = 0; for (v = 1;v<=ke[u][0];v++) if (color [u][v] == 0) {flag = 1;break;} i = u; j = v; } while (color[i][j] != 0); } //------------------------------------------------------------------ void solve() { int i,j,t; fillchar(color); fillchar1(mau); for (i = 1;i<=n;i++) {for(j = 1;j<=ke[i][0];j++) if (color[i][j] == 0) { chonmau(i,t); tomau(i,j,t); } } } //-------------------------------------------------------------------------- void out() { int i,j; for (i=1;i<=n;i++) {for(j=1;j<=ke[i][0];j++) switch(color[i][j]) { case 1:cout<<"G ";break; case 2:cout<<"Y ";break; } cout<<endl; } } void main() { input(); solve(); out(); } i fink soo, but she dont work Edited by author 09.07.2007 21:51 Edited by author 09.07.2007 22:03 Laktarugar Re: help me pleas writen this programm // Problem 1129. Door Painting 9 Jul 2007 22:48 #include<iostream.h> const int max = 101; int ke[max][max],color[max][max],mau[max][3]; int n; int fillchar(int mas[max][max],int rosme=max,int k = 0) { int j; for(int i = 1; i<rosme;i++) {for(j = 1; j<rosme;j++) mas[i][j] = k;} return 1; } int fillchar1(int mas[max][3],int rosme=3,int k = 0) { int j; for(int i = 1; i<rosme;i++) {for(j = 1; j<rosme;j++) mas[i][j] = k;} return 1; } //------------------------------------------------------------------------ void input() { int i,j; cin>>n; for (i = 1;i<=n;i++) {cin>>ke[i][0]; for(j=1;j<=ke[i][0];j++) {cin>>ke[i][j]; } } } //----------------------------------------------------------------------- void chonmau(int i,int &t) { if (mau[i][1]>=mau[i][2]) t = 2; else t = 1; } //--------------------------------------------------------------------- void tomau(int i,int j,int t) {int flag = 0; int u,v; do { color[i][j] = t; mau[i][t] = mau[i][t] + 1; u = ke[i][j]; flag = 0; for (v = 1; v<=ke[u][0]; v++) if(ke[u][v] == i ) { flag =1; break;} color[u][v] = 3-t; mau[u][3-t] = mau[u][3-t] +1; flag = 0; for (v = 1;v<=ke[u][0];v++) if (color [u][v] == 0) {flag = 1;break;} i = u; j = v; } while (color[i][j] == 0); } //------------------------------------------------------------------ void solve() { int i,j,t; fillchar(color); fillchar1(mau); for (i = 1;i<=n;i++) {for(j = 1;j<=ke[i][0];j++) if (color[i][j] == 0) { chonmau(i,t); tomau(i,j,t); } } } //-------------------------------------------------------------------------- void out() { int i,j; for (i=1;i<=n;i++) {for(j=1;j<=ke[i][0];j++) switch(color[i][j]) { case 1:cout<<"G ";break; case 2:cout<<"Y ";break; } cout<<endl; } } void main() { input(); solve(); out(); } AlexF [USTU] Good Problem) // Problem 1129. Door Painting 30 Jun 2007 21:03 Edited by author 30.06.2007 21:05 Tbilisi SU: Eldar Bogdanov Could anyone give me a hint or point out my mistake? (WA10) // Problem 1129. Door Painting 6 Oct 2006 22:59 I suggest that it's always possible to paint all the doors in such a way that the problem requirements will be satisfied. So I just DFS starting from every room and paint the door to some room in yellow if the amount of green rooms is more than amount of yellow ones for that door, and paint it in green in the other case. And I get WA10 :D Edited by author 06.10.2006 22:59 Vladimir Yakovlev (USU) Problem 1129 "Door painting". Rejudge (+) // Problem 1129. Door Painting 9 Aug 2005 22:19 A bug was found in validator program of 1129. Many incorrect solutions got AC because of it. All ACs were rejudged.
|