check that (r - l) % 2 == 1 Who can give me a test... AaCcGgTt 1 1 3 answ: 0 My program gives answer 0, but it's not passes this test. Could you explain, please, what can happens? I found my mistake. I have AC. Edited by author 12.12.2010 15:33 What was the problem? Test TTGgtAatTGgt 1 6 11 turned out to be helpful. What is standard method for this problem? Using stac I prepeared next[100000] for each opening and closing brackets. But it is appeared as bad because 50000*100000 too big. I made big jumps as next100[100000] and got Ac 0.203 Is my method can be beaten by new tests? What is standard method for this problem? You can use RMQ to solve this problem. My solution does not use RMQ. And it's just O(N) preprocess and O(1) query answer. Could you tell me more about your solution ? Is it sparse tables ? <O(L), O(log L)> segment tree solution acceptable too =) To do RMQ, I used a segment tree, but it could have been done using sparse tables too, I think. The idea, if I remember well, is the one I explained earlier in this topic. I just looked for my solution source code but without success. But i really think the final idea I used was that one. Remember, this is a problem for school kids, no RMQ is needed. Make a pointer-based stack, if isupper, then push to it, if islower, check if the current char matches the one on the top of the stack: if so, pop, otherwise discard the stack. For each query check that before l the top of the stack was the same as after r. Your algo is better not only because it is childish but due it's simple nature and then it may be implemented in assembler for example and it is not work for children. Please explain us, what will you algorithm output to following input: AaBbA 1 2 5 Before l=2 and after r=5 stack is the same, it is "A", but sequence aBbA is not human. Apply the GOOD JOB for College ACMers to Make Large Money and Become a Millionaire Hello, We need large no. of dedicated and hard working ACMers. The payment is good so we need ACMers to be efficient. All you have to do to get the job is to sign up at our websites. The link of our websites are given below. http://www.PaisaLive.com/register.asp?3556638-4847933 After the registration, a confirmation email will be sent to your specified email address. Please click on the link inside the confirmation email to activate your account and recieve ACM work instantly. For any other queries you can mail the administrator. Miss Juliet Admin paisalive.com Thank for good advice! I know RMQ and understood how to apply it in this problem. Hi! I've solved this task with custom <O(L), O(1)> algo. It is very interesting for me to reduce this problem to RMQ. Can you give me advice (here or by email: different-things[at]nm[dot]ru) ? Could you explain your custom <O(L), O(1)> solution, please? A idea i had today, but haven't yet tested using RMQ is this: 0 - Read the input string to str[] 1 - Create an int array val[], where in position i there is the position of the character that pairs with the character str[i]. If there is no such character, val[i] equal to X = -1. For example: pos - 0 1 2 3 4 5 6 7 8 9 str - A G g a a G T t c g val - 3 2 1 0 X X 8 7 X X 2 - For a query (a, b), the program answers "1" if the minimum and maximum values in val[] range [a-1, b-1] are between a and b. "0", otherwise. I'll see if it works later... SQRT-decomposition get TL on Java. Edited by author 25.06.2011 21:19 Apply the GOOD JOB for College ACMers to Make Large Money and Become a Millionaire Hello, We need large no. of dedicated and hard working ACMers. The payment is good so we need ACMers to be efficient. All you have to do to get the job is to sign up at our websites. The link of our websites are given below. http://www.PaisaLive.com/register.asp?3556638-4847933 After the registration, a confirmation email will be sent to your specified email address. Please click on the link inside the confirmation email to activate your account and recieve ACM work instantly. For any other queries you can mail the administrator. Miss Juliet Admin paisalive.com 11 authors lost AC. Thanks to Fedor Fominykh for new tests. Which method can be used in this problem? Really dynamic programming? Give me this test if you can please... :) My AC program gives answer "1" to the test: GTACcAaa 1 1 8 I'm wrong? I think so, as there is no "t" to pair with the "T" in the input string. Could you explain me how did you solve this one? My RMQ solution gives WA in test case 41. Why? My program is incorrect. It gives wrong answers on the test above and on many other tests. It's strange that I've got AC. But test 41 contains something like this: AGgTta 1 1 6 Right answer is "1". I aswered "i think so" trying to say that "your program is incorrect indeed". Sorry. Your code AC is strange for me too. BTW, really thanks for the test 41 tip. I finally got my AC. These tests have helped me to solve the problem. Test #1 input: A 1 1 1 output: 0 Test #2 input: Aa 3 1 1 1 2 2 2 output: 010 Test #3 input: AacCAa 5 1 6 1 2 1 4 2 3 5 6 output: 01001 Test #4 input: AaCAac 6 1 6 1 2 3 6 4 5 2 3 1 5 output: 111100 But what is wrong with the Test 3 in your example? The output is correct. Cannot beat test 41. Please share any ideas, tricky tests. Me too. I would really appreciate some help. This test failed me when I got wa 41: Input: TAaGgTtCcAaGgt 3 1 14 2 3 2 13 Output: 111 Now I have accepted #include <limits> #include <fstream> #include <algorithm> #include <set> #include <map> #include <sstream> #include <string> #include <vector> #include <cmath> #include <time.h> #include <cmath> #define fori(i,n) for(int i=0;i<n;i++) #define for1(i,n) for(int i=1;i<=n;i++) #define forbi(i,a,b) for(int i = a; i<=b; i++) #define len(v) (int((v).size())) #define vi vector<int> #define vvi vector<vi > #define sz(v) (int)v.size() #define mmin(a,b,c) min(a,min(b,c)) #define sqr(x) ((x)*(x)) #define all(v) v.begin(),v.end() #define inf 987654321 #define mmax(a,b,c) max(a,max(b,c)) #define ii pair<int,int> #define si pair<int,string> #define sii vector<si > #define vii vector<ii > #define vs vector<string > #define vvii vector<vii > const double pi = acos(0.0)*2; const double eps = 1e-7; #define mp(a,b) make_pair(a,b) using namespace std; #ifndef ONLINE_JUDGE ifstream cin("input.txt"); ofstream cout("output.txt"); #else #include <iostream> #endif vii X; vii Z; vi V; vi U; vector < char > S; void main() { V.reserve(200001); char T [200001]; X.reserve(200001); Z.reserve(200001); U.reserve(200001);
int n; scanf("%s", T); scanf("%d",&n); int t=strlen(T); X=vii(n); V.resize(t); Z=vii(t);
fori(i,n) scanf("%d%d",&(X[i].first),&(X[i].second)); int y=0, max=0, Root=0, c=1; U.resize(t); S.reserve(200001); fori(i,t) { if (S.empty() && (T[i]=='a' || T[i]=='c' || T[i]=='g' || T[i]=='t')) { V[i]=1; Z[i].second=Root; if (i!=0) Z[i].first=Z[i-1].second; continue; } if (T[i]=='A' || T[i]=='C' || T[i]=='G' || T[i]=='T') { S.push_back(T[i]); if (i!=0) Z[i].first=Z[i-1].second; y++; if (y>max) max=y; Z[i].second=y+c; } else { if (S.back() - T[i] == 'A' - 'a') { S.pop_back(); y--; Z[i].second=y+c; Z[i].first=Z[i-1].second; if (S.empty()) { Z[i].second=Root; y=Root; c++; }
} else { V[i]=1; Z[i].first=Z[i-1].second; S.clear(); Root=max+1; Z[i].second=Root; c++; y=Root; } } } /* fori(i,t) cout<<V[i].first<<" "; cout<<endl; fori(i,t) cout<<V[i].second<<" "; */
//V.push_back(mp(0,0)); U[0]=V[0]; for(int i=1; i<t; i++) U[i]=U[i-1]+V[i]; fori(j,n) { int d; if (X[j].first>1) d=U[X[j].second-1]-U[X[j].first-2]; else d=U[X[j].second-1];
if ((Z[X[j].first-1].first==Z[X[j].second-1].second) && d==0) printf("%d",1); else printf("%d",0); } } Edited by author 26.10.2009 23:17 Give me some test, please. I was just wondering- are "ACac" and "ACCcca" human strands? ACac -- is not; ACCcca -- is; |
|