I have WA in test 13

Edited by author 21.02.2023 01:48

Please Help and give me some tests!

Я долго бился с этой проблемой несмотря на то,что сложность <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).

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? :)

Есть кто нибудь которой решил с подсчётом количество инверсии.

Edited by author 16.10.2015 11:01

After read the discussions, still get TLE in test 16, anyone got the idea of optimization?

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

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.

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;
}

#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;
}

#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 passed for G (N ^ 2). Is this normal? What is the asymptotic behavior of a normal solution?

Anybody knows?

Edited by author 25.05.2010 20:52

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

att

Edited by author 20.09.2006 14:31