Show all threads Hide all threads Show all messages Hide all messages | If you have Runtime Error with Python solution at 8-19 test | iron_orc | 1501. Sense of Beauty | 24 Jan 2022 03:27 | 1 | If using recursive algorithm increase recursion depth limit at least 4000. For my algo 2000 was not enough import sys sys.setrecursionlimit(4000) | Useful test cases | Pravă Felix-Mihai | 1501. Sense of Beauty | 28 Apr 2021 19:31 | 1 | I checked them using my AC algorithm 6 100110 000111 -> Impossible 10 1001100110 0101010101 -> 11111111112222222222 10 1001110000 0011111010 -> 11111211221212122222 11 01011100000 01111011001 -> 1111121112121212222222 14 10011111100101 00000110101010 -> 1111121212121111112222222222 18 100111111001010010 000001101010100111 -> 111112121212111111222222222222121112 18 100111111001010011 000001101010100011 -> Impossible | if you have WA6 | Viktor Krivoshchekov`~ | 1501. Sense of Beauty | 28 Nov 2019 17:15 | 1 | | Why wrong answer in case 12 ? | Al Mahfuz | 1501. Sense of Beauty | 2 Jan 2018 07:19 | 1 | | WA, Case 12, Help please. | Al Mahfuz | 1501. Sense of Beauty | 2 Jan 2018 07:19 | 1 | Edited by author 02.01.2018 07:25 | How to solve. | Mahilewets | 1501. Sense of Beauty | 14 Jul 2017 10:39 | 1 | I have solved it by reduction to a graph exploration task. Each vertex consists of three parameters (i, j, pr). Where i, j denote number of card at the top of each pile and pr denotes previous state. pr is also a "used" array. So, if pr[N] [N] =none, then impossible. Otherwise just recover answer using pr. You can also have in your state additional parameter diff denotes difference between red and black cards. I have used instead additional two arrays diff11 and diff2 denote difference between first i cards in first pile and in the second pile respectively. There is an edge iff difference at the next step would be not greater than one (abs) , obviously. | WA on #6 | Double_O | 1501. Sense of Beauty | 10 Dec 2015 12:49 | 1 | Can anyone give some test cases? #include<bits/stdc++.h> using namespace std; int i, j, k, l, x, y, z, m, n, ans; string first, second; int dp[1010][1010][3][4], dir[1010][1010]; int make_way(int first_pile, int second_pile, char c, int state) { //cout << first_pile << ' ' << second_pile << endl; if(first_pile == n && second_pile == n){ if(state > 1) return 0; else return 1; } if(state > 1) return 0; int p = 0, q = 0, r = 0; char d; if(c == '0') d = '1'; else d = '0'; if(first_pile < n){ if(first[first_pile] == c){ p = make_way(first_pile + 1, second_pile, c, state + 1); } else{ p = make_way(first_pile + 1, second_pile, d, 1); } } if(second_pile < n){ if(second[second_pile] == c){ q = make_way(first_pile , second_pile + 1, c, state + 1); } else{ q = make_way(first_pile , second_pile + 1, d, 1); } } if(p == 1){ dir[first_pile][second_pile] = 1; } else if(q == 1) dir[first_pile][second_pile] = 2; dp[first_pile][second_pile][c - '0'][state] = p | q; return dp[first_pile][second_pile][c - '0'][state]; } int main() { cin >> n >> first >> second; ans = make_way(0, 0, '0', 0); if(!ans){ cout << "Impossible" ; return 0; } for(i = 0, j = 0; i < n || j < n; ){ cout << dir[i][j]; if(dir[i][j] == 1) i++; else j++; } return 0; } | Dynamic solution - help needed | Narek Aghekyan | 1501. Sense of Beauty | 22 Oct 2014 05:32 | 2 | I want to use bool dp[N][N][3] array, where dp[i][j][0] is true if it is possible to solve the problem for last 'i' characters of string1 and for last 'j' characters of string2 and in current state it is necessary to take 0 and place into the stack of '0's. dp[i][j][1] is true if it is possible to solve the problem for last 'i' characters of string1 and for last 'j' characters of string2 and in current state it is necessary to take 1 and place into the stack of '1's. dp[i][j][2] is true if it is possible to solve the problem for last 'i' characters of string1 and for last 'j' characters of string2 and in current state stacks of '0's and '1's have the same size. Obviously (dp[N][N][2] == true) means that it is possible to solve the problem. My problem is that I can't fill this 3D array. Please help. you just need dp[i][j] and store there form were you get the last piece, if it was from 1 you can rebuild the path looking dp[i-1][j], if it was from 2 you llok dp[i][j-1]. If dp[i][j] = 0 you can't solve the problem. | Why WA#6??????????????????/ | Neizvestnii | 1501. Sense of Beauty | 15 Oct 2013 21:26 | 4 | Well, try these: 11 01011100000 01111011001 10 1001110000 0011111010 10 1001111110 0000011010 They should n't be impossible. Edited by author 31.08.2007 16:17 Edited by author 15.10.2013 21:28 Edited by author 15.10.2013 21:28 | Why 22121112 why not 22121121? | mehran | 1501. Sense of Beauty | 1 May 2013 19:23 | 2 | I think both answer would do | Any idea? | Olympic Bear | 1501. Sense of Beauty | 10 Feb 2012 04:47 | 4 | Edited by author 12.11.2006 01:35 You can read the input into the status table which has a number 'x' inside the cell "[i][j]" if the difference in height between two piles (red and black) after you remove 'i' cards from the first pile and 'j' from the second one is 'x'. For the first statement example, the table is: {{0,-1,0,1,0},{-1,-2,-1,0,-1},{-2,-3,-2,-1,-2},{-1,-2,-1,0,-1},{0,-1,0,1,0}} (you can view it using "Wolfram|Alpha" service). Thus, you are to "move" over the table cells from the top left-hand one to the bottom right-hand one, but you can't visit cells with the values different from -1,0,1. Use DP with the diagonal process to draw the right way. It help you. I don't post all code =) int n; vector<int> poker_log, I, II; vector<vector<bool>> IsUs; void f( int posI, int posII, int kol0, int kol1 ){ if( abs(kol0-kol1)>1 ) return; if( !IsUs[posI][posII] ) IsUs[posI][posII] = true; else return; /* hush-hush secreted deleted code here*/ } Just recursive function and bool vector IsUs[0..n][0..n] which answer on quastion "Was we in this state? Y/N" | WA#8 could anyone help me providing a test or any idea? | jlcastrillon | 1501. Sense of Beauty | 17 Aug 2011 09:12 | 1 | I have been trying to solve this problem but I am getting WA 8 , please help me. | WA9, give tests please! | Vasily Slesarev | 1501. Sense of Beauty | 28 Jun 2011 13:27 | 5 | Hello, I use DP and get WA9. Please give tests. pls give me solution. Edited by author 29.06.2011 15:01 #include <vector> #include <string> #include <iostream> using std::vector; using std::cin; using std::cout; using std::string; using std::pair; int main() { int count; string first_pile, second_pile; cin >> count; cin >> first_pile >> second_pile; vector<vector<pair<int, int> > > possibility(count + 1); for (int i = 0; i <= count; ++i) { possibility[i].resize(count + 1); } possibility[0][0].first = 1; possibility[0][0].second = 0; for (int i = 1; i <= count; ++i) { if (possibility[i - 1][0].first == 0) { possibility[i][0].first = 0; } else { if (first_pile[i - 1] == '0') { if (possibility[i - 1][0].second <= 0) { possibility[i][0].first = 1; possibility[i][0].second = possibility[i - 1][0].second + 1; } else { possibility[i][0].first = 0; } } else { if (possibility[i - 1][0].second >= 0) { possibility[i][0].first = 1; possibility[i][0].second = possibility[i - 1][0].second - 1; } else { possibility[i][0].first = 0; } } } if (possibility[0][i - 1].first == 0) { possibility[0][i].first = 0; } else { if (second_pile[i - 1] == '0') { if (possibility[0][i - 1].second <= 0) { possibility[0][i].first = 2; possibility[0][i].second = possibility[0][i - 1].second + 1; } else { possibility[0][i].first = 0; } } else { if (possibility[0][i - 1].second >= 0) { possibility[0][i].first = 2; possibility[0][i].second = possibility[i - 1][0].second - 1; } else { possibility[i][0].first = 0; } } } } for (int i = 1; i <= count; ++i) { for (int j = 1; j <= count; ++j) { possibility[i][j].first = 0; if (possibility[i - 1][j].first != 0) { if (first_pile[i - 1] == '0') { if (possibility[i - 1][j].second <= 0) { possibility[i][j].first = 1; possibility[i][j].second = possibility[i - 1][j].second + 1; continue; } } else { if (possibility[i - 1][j].second >= 0) { possibility[i][j].first = 1; possibility[i][j].second = possibility[i - 1][j].second - 1; continue; } } } if (possibility[i][j - 1].first != 0) { if (second_pile[j - 1] == '0') { if (possibility[i][j - 1].second <= 0) { possibility[i][j].first = 2; possibility[i][j].second = possibility[i][j - 1].second + 1; continue; } } else { if (possibility[i][j - 1].second >= 0) { possibility[i][j].first = 2; possibility[i][j].second = possibility[i - 1][j].second - 1; continue; } } } } } if (possibility[count][count].first == 0) { cout << "Impossible\n"; // cin >> count; return 0; } vector<int> answer(0); int i = count, j = count; while ((i != 0) || (j != 0)) { answer.push_back(possibility[i][j].first); if (possibility[i][j].first == 1) { --i; } else { --j; } } for (int k = answer.size() - 1; k >= 0; --k) { cout << answer[k]; } // cin >> count; return 0; } But I think, it is difficult to understand it.) 4 1010 0110 22221111 Edited by author 29.06.2011 15:00 | Finally AC!! | zeroh | 1501. Sense of Beauty | 12 Sep 2008 21:39 | 2 | Search: TLE; Greed: WA; DP: AC. -_-!!! | It't too hard for java | Iambitious | 1501. Sense of Beauty | 6 Nov 2007 19:12 | 2 | After I have tle many times, I found that in java declaring a 10^6 array would take 0.5 second. | hi, WA 12 ..... is any one know what the ... is in this test... | Alireza_Keshmiri | 1501. Sense of Beauty | 31 Aug 2007 15:58 | 1 | | I Got WA#1. But my algo passes the following three test cases. | Kingway Jin | 1501. Sense of Beauty | 10 Mar 2007 18:10 | 3 | =========== Input ===================== Sample input #1 4 0011 0110 Sample input #2 4 1100 1100 Sample input #3 6 101010 101010 ============= Output ================= Sample output #1 22121112 Sample output #2 Impossible Sample output #3 111111222222 OK. I found that my program gave me the wrong answer when the input is as follow: 1 0 0 I fixed this, and I still got WA#1. I need some hints. | Why wa 18 | valdem | 1501. Sense of Beauty | 10 Mar 2007 18:07 | 1 | there is my code: program z1501; Var s,s1,s2:string; i,l,n:longint; p:shortint; st:boolean; begin readln(n); readln(s); readln(s1); s:=s+' '; s1:=s1+' '; s2:=''; i:=1; l:=1; st:=false; while True do begin while ((i<=n)or(l<=n))and not st do begin if (p=-1)and(s[i]='1')and(s[i+1]='1')and(s[i+2]='0')then begin s2:=s2+'11'; inc(i,2); p:=1; break; end; if (p=-1)and(s1[l]='1')and(s1[l+1]='1')and(s1[l+2]='0')then begin s2:=s2+'22'; inc(l,2); p:=1; break; end; if (p=1)and(s[i]='0')and(s[i+1]='0')and(s[i+2]='1')then begin s2:=s2+'11'; inc(i,2); p:=-1; break; end; if (p=1)and(s1[l]='0')and(s1[l+1]='0')and(s1[l+2]='1')then begin s2:=s2+'22'; inc(l,2); p:=-1; break; end; if (p=-1)and(s[i]='1')and(s[i+1]='0')then begin s2:=s2+'1'; inc(i); p:=0; break; end; if (p=-1)and(s1[l]='1')and(s1[l+1]='0')then begin s2:=s2+'2'; inc(l); p:=0; break; end; if (p=1)and(s[i]='0')and(s[i+1]='1')then begin s2:=s2+'1'; inc(i); p:=0; break; end; if (p=1)and(s1[l]='0')and(s1[l+1]='1')then begin s2:=s2+'2'; inc(l); p:=0; break; end; if (p=0)and(s[i]='1')and(s[i+1]='0')then begin s2:=s2+'1'; inc(i); p:=1; break; end; if (p=0)and(s1[l]='1')and(s1[l+1]='0')then begin s2:=s2+'2'; inc(l); p:=1; break; end; if (p=0)and(s[i]='0')and(s[i+1]='1')then begin s2:=s2+'1'; inc(i); p:=-1; break; end; if (p=0)and(s1[l]='0')and(s1[l+1]='1')then begin s2:=s2+'2'; inc(l); p:=-1; break; end; if (p=-1)and(s[i]='1')then begin s2:=s2+'1'; inc(i); p:=0; break; end; if (p=-1)and(s1[l]='1')then begin s2:=s2+'2'; inc(l); p:=0; break; end; if (p=1)and(s[i]='0')then begin s2:=s2+'1'; inc(i); p:=0; break; end; if (p=1)and(s1[l]='0')then begin s2:=s2+'2'; inc(l); p:=0; break; end; if (p=0)and(s[i]='1')then begin s2:=s2+'1'; inc(i); p:=1; break; end; if (p=0)and(s1[l]='1')then begin s2:=s2+'2'; inc(l); p:=1; break; end; if (p=0)and(s[i]='0')then begin s2:=s2+'1'; inc(i); p:=-1; break; end; if (p=0)and(s1[l]='0')then begin s2:=s2+'2'; inc(l); p:=-1; break; end; st:=true; end; if (length(s2)=2*n)or st then break; end; if length(s2)=2*n then writeln(s2) else writeln('Impossible'); end. | WA7 | tanas | 1501. Sense of Beauty | 22 Feb 2007 21:27 | 1 | WA7 tanas 22 Feb 2007 21:27 My program gives right answers for all your tests, but I got WA7. Please help. | Possible wrong example test#1 | Ont | 1501. Sense of Beauty | 9 Dec 2006 13:28 | 5 | Try to take as described in answer and you give this order of the cards: for test 0011 0110 and answer 22121112 ----> 01010(11)0 (mistake!) True possible answer is 22121121. Am I right? I think you don't understand problem statement. Sample test is right. You don't need to make sequence like 01010101..... Read the task again. Edited by author 06.12.2006 18:24 But it's just hard to understand for me... Why example is true? If we take card 1 than card 1 than pile with ones is lager than pile with zeros. And lager by 2 cards, not by 1! See problem - <...> At each moment the resulting piles must not differ in size by more than one card <...> See table: zero's, one's, difference ---|-------- 0 | 1 0 1 1 | 1 1 0 0 | 2 1 1 1 | 2 2 0 0 | 3 2 1 1 | 3 3 0 1 | 3 4 1 0 | 4 4 0 I think all is right. Edited by author 08.12.2006 23:22 Yes :). I was very stupid.... Many sanks, now i will try to solve it. |
|
|