I have WA in test 13 Edited by author 21.02.2023 01:48 Please Help and give me some tests! Never mind got it. The case is like this 10 <<<<><>>>> I just forgot to count the '>' that can never be used for swapping. Я долго бился с этой проблемой несмотря на то,что сложность <200. Я пытался решить с помощью ДП,но там очень много случаев и сложная реализация. Задачу можно решить логически: во-первых,первые символы "<" и последние символы ">" ни на что не влияют,поэтому удалим их; во-вторых,если слева есть хоть один ">",то он в ЛЮБОМ случае будет меняться с КАЖДЫМ "<" РОВНО один раз(если "<" существует). Т.е. нас не интересует конструкция строки. Нас интересуют числа Z[1],E[1],Z[2],E[2],...Z[p],E[p],где Z[i] -количество ">" в последовательности 00000000...00000,а E[i]- количество "<" в последовательности 11111....11111111. Т.е. нашу строку делаем в виде 00...0011..1100..0011..11........00..0011..11,где P чередований (я ">" заменил на "0",а "<" на "1") . Тогда ответ есть Z[1]*(E[1]+...E[p])+Z[2]*(E[2]+..+E[p])+...+Z[p]*E[p]. Сумму можно посчитать через частичные с помощью ДП. Асимптотика O(N). madness :D Imho, it can be solved by easier way. Let's create the array, where put 0 instead of '<' and 1 instead of '>'. Then answer is number of swaps in bubblesorting of this array. I went exactly this way and my solution looks very easy! >><<>< 110010 | counter = 0 Now we go from the right and move every 1 all the way to the right and count the moves (we don't need to actually move anything but you can see everything better this way) 110001 | counter = 1[4->5] 100011 | counter = 1 + 3[1->4] 000111 | counter = 1 + 3 + 3[0->3] = 7 I got AC with this O(n) Thank all of you) Very helpful! Get my AC using this solution Moving? Overkill. Just count how many inversions are there. I don't remember exactly, which symbol, '<' or '>', should be considered as 1 and which as 0. Don't even try to memorize the sequence. Just have a counter and increment it each time when encountered 1 and add counter value to answer each time when encountered 0. For those who couldn't do straightforward O(n^2) with tricks. Think of < as 0 and > as 1. Every time you see >< (10) you replace (swap) it with <> (01). Which means, you stop as soon as you get sorted stuff, 0*1*. Doesn't it look like count of swaps in bubblesort? :) this solution wont pass TL on 15 with small tricks on wont pass 16 Есть кто нибудь которой решил с подсчётом количество инверсии. Edited by author 16.10.2015 11:01 After read the discussions, still get TLE in test 16, anyone got the idea of optimization? consider line breaks between inputs 15 <>><<> <<><<< >>< answer is : 28. my program is accepted. So what I am doing is to note 1 instead of > and 0 instead of <. Therefore if I have the configuration 10 then it will become 01. The 01 configuration doesn't change. Therefore if I take the example from the problem I have 110010 101001 010101 001011 000111 So I see there is a shifting of the zero's to the left and a of one's to the right. So I am saving in the beginning the positions of zero's in an array (zero[]) and the positions of the one's in another array (one[]). then I consider k = one[0]. Therefore the all algorithm (after reading the data) looks practically like this k=one[0]; for (int i=0;i<z;i++){ if ((zero[i]-k) >=0){ result+=(zero[i]-k); k++; } } I think the complexity of this is even O(z) where z is the numbers of zero's. The problem with this is that I obtain TL on test 15. Is there anything faster or is only my coding problme (java)? Edited by author 29.11.2012 19:22 Edited by author 29.11.2012 19:37 The problem is in your code. Next solution gets AC with O(n) complexity // obtaining bool array int pos = 0, res = 0; for (int i = 0; i < n; i++) if (!arr[i]) res += i - pos++; var i,n,L,R:longint; ch:char; begin readln(n); L:=0; R:=0; for i:=1 to n do begin read(ch); while not(ch in ['<','>']) do read(ch); case ch of '>':inc(R); '<':inc(L,R); end; end; writeln(L); end. Denote by R the number of recruits at the right end of the queue. When you get a new '>', simply increase R by 1. If you receive a '<', the process is like this: >>>>>< (Say R=5) >>>><> >>><>> >><>>> ><>>>> <>>>>> Now you see, it takes exactly R turns to send the '<' to the left of the '>'s, and the number of the '>'s, or R, stays the same. So it's easy to understand the prog. 10 >>>><>>>< What about this test? why do i get Time limit exceeded :( #include <cstring> #include <cstdlib> #include <cstdio> using namespace std; int main () { char * pch; char str[30005],str1[30005]; int number,i=0,j=0; scanf("%d",&number); while(i<number) { scanf("%s",str); i+=strlen(str); strcat(str1,str); } while(strstr(str1,"><")) { pch=strstr(str1,"><"); strncpy(pch,"<>",2); j++; } printf("%d",j); return 0; } I used very similar code and got AC (though there is a better solution if I recall correctly). What I did is: - If you have <<< at left end or >>> at right and, you can ignore those - they will never change again. Thus, you can keep treack of the left and right endings, and only parse those, instead of going from 0 to n every time. AC 0.625 #include <iostream> using namespace std; int main() { int n; cin >> n; char c; int t = 0, ans = 0; while (n--) { cin >> c; if (c == '>') ++t; else ans += t; } cout << ans << endl; return 0; } #include <iostream> #include <string> using namespace std; int main() { char s[30001]; int a; cin >> a; for(int i=0; i<a; i++) cin >> s[i]; int res=0; bool ok=false; while(!ok) { ok=true; for(int i=0; i<a-1; i++) { if(s[i]=='>' && s[i+1]=='<') { s[i]='<'; s[i+1]='>'; res++; ok=false; i++; }
} //cout << s << ' ' << ok << endl; } cout << res << endl; return 0; } I used very similar code and got AC (though there is a better solution if I recall correctly). What I did is: - Use stdio instead of iostream: it's faster - If you have <<< at left end or >>> at right and, you can ignore those - they will never change again. Thus, you can keep treack of the left and right endings, and only parse those, instead of going from 0 to n every time. AC 0.625 #include <iostream> using namespace std; int main() { char x[30005],l='<',r='>',p; int n,i,s=0,k=1; cin>>n; for(i=0; i<n; i++) cin>>x[i]; while(k!=0) { k=0; for(i=0; i<n; i++) if( x[i]==r && x[i+1]==l) { swap(x[i],x[i+1]); s++; k++;} } cout<<s; return 0; } i don't know how to minimize my prog I used very similar code and got AC (though there is a better solution if I recall correctly). What I did is: - Use stdio instead of iostream: it's faster - If you have <<< at left end or >>> at right and, you can ignore those - they will never change again. Thus, you can keep treack of the left and right endings, and only parse those, instead of going from 0 to n every time. AC 0.625 I passed for G (N ^ 2). Is this normal? What is the asymptotic behavior of a normal solution? Make program, which will find solution for test ><<<<<<<<...(29999 symbols '<'), and send it on timus. If it fails with WA1, then it's normal. If it fails with TL1, then it's weak testing. Sorry for bad english. Power of timus server not equal power of contest server. TL on thimus is not indicator. If you got TL then tests on this task should be harder and such solutions must fail. Better try test >>>...(15000 times)..>>><<<...(15000 times)..<<< If your solution passes it in time - then limitations of the problem are already too weak for modern computation facilities =( If it gets TL - then timus tests are just weak. Anyway, there exists correct O(N) algo... Where I can read about algorithm or idea? That's the main idea of the problem - not to read about an algorithm or idea but to turn your brains on and create it. This is possible (and even not difficult), try it! Anybody knows? Edited by author 25.05.2010 20:52 There is no answer like NO; N=30000, the rest of file contains characters '<' and '>' each on separate line (total 30001 lines in file). This test may lead to TLE for programs that concatenate all lines into one and do it with complexity O(n^2). Know what? That problem has the solution of 10 strings. Cool,yeah? The hint is that here's no 'NO' answer here. Beautyful problem Yes the solution is very simle. att Edited by author 20.09.2006 14:31 Yes you are right. When I am read (cin >> s), where s is string, I got WA13. When I am read by getchar, and bring in string '>' or '<', I got AC You can not use cin >> s because there are CR/LF characters in the input. For example such test is correct: 4 >> << P.S. Test 13 is correct now. Edited by author 23.07.2007 22:31 |
|