| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| Some tests | Конобейцев Иван Олегович | 1129. Покраска дверей | 15 сен 2022 09:36 | 1 |
Some tests Конобейцев Иван Олегович 15 сен 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 |
| Idea | Felix_Mate | 1129. Покраска дверей | 27 авг 2015 15:36 | 1 |
Idea Felix_Mate 27 авг 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 |
| WHAT WRONG WITH TEST 10 | Piratek-(akaDK) | 1129. Покраска дверей | 18 авг 2015 04:35 | 3 |
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??? maybe more than one component! |
| No subject | Zayakin Andrey[PermSU] | 1129. Покраска дверей | 22 июл 2014 22:13 | 3 |
No subject Zayakin Andrey[PermSU] 19 фев 2010 00:26 flow can solve this.
Edited by author 19.02.2010 16:08 How we can solve this using flow? Some hints?
Thanks,
Ostap Re: No subject Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 22 июл 2014 22:13 OMG! How difficult - flow, it's O(N^3) and lots of code...
Let the DFS help you! =) |
| Solution always EXISTS!!! | Tigran92[RAU_902] | 1129. Покраска дверей | 21 ноя 2010 19:12 | 2 |
axper jan..
good that found ...
can you send message? vk com/mikaelarakelyan
....
sometimes an idea is bad for a solution |
| test #5 - Graph is not connectivity | UdSU: Ajtkulov, Kotegov, Saitov | 1129. Покраска дверей | 6 авг 2010 09:35 | 4 |
Some algos do not depend on this property |
| About Java... | DWED | 1129. Покраска дверей | 28 авг 2009 07:22 | 3 |
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! I suppose that's because server use JDK1.5, not 1.6 Maybe their method of calculating Running time is different |
| To admin | player | 1129. Покраска дверей | 13 июл 2009 09:17 | 3 |
Could you check the test 10,please!
Thanx I know why i got wrong......... |
| Would you like to do me a favor to post me a copy of testing data? | orlando22 | 1129. Покраска дверей | 26 мар 2009 10:17 | 1 |
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" |
| i don't think the numbers of adjacent lodgings follow in ascending order! | pittycat | 1129. Покраска дверей | 1 авг 2008 14:41 | 2 |
Because if i use this condition i got WA,
if i ignore it(change my program) i got AC. I had a trap for that, it didn't signal. So, they ARE ascending. |
| I used Greedy and got AC.By the way,why the AC rate is so high? | Yu YuanMing | 1129. Покраска дверей | 1 авг 2008 14:40 | 2 |
If your greed is chain-based, then it's correct
Edited by author 01.08.2008 14:40 |
| Is that Possible& | Piratek-(akaDK) | 1129. Покраска дверей | 1 авг 2008 14:39 | 2 |
Может ли быть между двумя комнатами больше чем одна дверь? (Can there exist more than 2 doors between rooms?)
No because numbers of adjacent rooms are ASCENDING. |
| problem 1129 | tyana | 1129. Покраска дверей | 1 авг 2008 14:38 | 5 |
Whether in a problem 1129 some variants of the answer are possible?? In that case my answer will not converge at check. Or here such situations are provided? Some checkers are smarter than just identity |
| How to avoid TLE in Test#10? | Nickolas Kakà | 1129. Покраска дверей | 1 авг 2008 14:37 | 2 |
How to avoid TLE in Test#10? Solution is O(M), M - number of doors |
| 1129 | tyana | 1129. Покраска дверей | 13 янв 2008 20:42 | 1 |
1129 tyana 13 янв 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 |
| Show Test 10 | Piratek-(akaDK) | 1129. Покраска дверей | 6 окт 2007 01:09 | 1 |
Please send me a test 10 to my email destyon@mail.ru |
| help me pleas writen this programm | Titan | 1129. Покраска дверей | 9 июл 2007 22:48 | 3 |
#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 #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();
} |
| Good Problem) | AlexF [USTU] | 1129. Покраска дверей | 30 июн 2007 21:03 | 1 |
Edited by author 30.06.2007 21:05 |
| Could anyone give me a hint or point out my mistake? (WA10) | Tbilisi SU: Eldar Bogdanov | 1129. Покраска дверей | 6 окт 2006 22:59 | 1 |
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 |
| Problem 1129 "Door painting". Rejudge (+) | Vladimir Yakovlev (USU) | 1129. Покраска дверей | 9 авг 2005 22:19 | 1 |
A bug was found in validator program of 1129. Many incorrect solutions got AC because of it. All ACs were rejudged. |
