so in my solution i use o(N^3) space and i got mle ( i expected that) but what makes me confused that people says they passed wih o(n^3) time i know there is a different between memory and time complexity but i have some doubts they may also used o(n^3) space too so can someone tell me whether they added a new cases or whats is the problem? deleted Edited by moderator 23.07.2022 20:36 did anyone solve it with python? I have used O(k*n^2) approach. Please explain O(n^2) approach if it exists. const maxH=500; var N,K,q,w,e:longint; H:array[1..maxH] of longint; z:array[1..2,1..maxH,0..2] of longint; x:array[0..1] of longint; begin readln(N,K); for q:=1 to N do readln(h[q]); for q:=1 to K do begin z[2,q,0]:=0; z[2,q,1]:=0; z[2,q,2]:=0; end; z[2,1,h[1]]:=1; for q:=2 to N do begin z[1]:=z[2]; for e:=1 to K do begin z[2,e,0]:=0; z[2,e,1]:=0; z[2,e,2]:=0; end; z[2,1]:=z[1,1]; z[2,1,h[q]]:=z[2,1,h[q]]+1; e:=K; if q<K then e:=q; for w:=2 to e do begin x[0]:=z[1,w,0]; x[1]:=z[1,w,1]; x[h[q]]:=x[h[q]]+1; z[2,w,h[q]]:=1; z[2,w,2]:=z[1,w-1,0]*z[1,w-1,1]+z[1,w-1,2]; if z[2,w,2]>z[1,w,2]+x[0]*x[1] then begin z[2,w,0]:=x[0]; z[2,w,1]:=x[1]; z[2,w,2]:=z[1,w,2]; end; end; end; writeln(z[2,K,0]*z[2,K,1]+z[2,K,2]); end. Could you give me a test on which my solution gives wrong answer? 7 2 1 1 0 0 1 1 1 Isn't the correct answer 4? 7 2 1 1 0 0 1 1 1 5 2 1 1 1 0 1 ========= 5 2 1 0 1 1 1 I got WA2, but after that I changed limits for N and K from 501 to 503 and it worked. (indexing starting from 1). Dear admins (if any), I've encountered the subject. Please give me some hints how to speed up my Python solution, because I've tried all the performance tricks I know and I still get TL2. You can post some details about your solution, for example the complexity your program has. A solution with N^3 complexity should fit in time (with c++). Also post the core function (loops) of your code, maybe you have some mistakes and enter some endless loop. if you have a better algo please tell to me. plz help!!!!!!!!!!!!!!! The data is too weak, I use O(n^3) got an AC in 0.097ms~~ I use O(N^3) and got AC in 0.156 too It's not the problem of tests program which does exacltly n^3 operations work for 0.28, so why you hink tests are weak? package timus; import java.io.BufferedReader; import java.io.FileNotFoundException; import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader; import java.io.Reader; import java.util.Arrays; import java.util.StringTokenizer; public class p1167 { static int a[], totals[]; static int h, s; static int min = Integer.MAX_VALUE; public static void main(String[] args) throws FileNotFoundException { InputStream is = System.in; // is = new FileInputStream(new File("A.txt")); FastScanner sc = new FastScanner(new InputStreamReader(is)); h = sc.nextInt(); s = sc.nextInt(); int k[] = new int[h]; for (int i=0; i<h; i++) { k[i] = sc.nextInt(); } totals = new int[h+1]; totals[1] = k[0]; for (int i=2; i<h+1; i++) { totals[i]=totals[i-1]+k[i-1]; } int maxcap = h-s+1; int unhappines[][] = new int[h+1][h+1]; for (int i=1; i<=/*maxcap*/h; i++) { int up = Math.min(h, maxcap+i); for (int j=i; j<=up; j++) { int len = j-i+1; int ones = totals[j]-totals[i-1]; unhappines[i][j] = (len-ones)*ones; } } int a[][] = new int[h+1][s+1]; for (int i=1; i<=h; i++) { Arrays.fill(a[i], Integer.MAX_VALUE); } int maxes[] = new int[s+1]; for (int i=1; i<=s; i++) { maxes[i] = maxcap+i-1; } for (int i=1; i<=maxcap; i++) { a[i][1] = unhappines[1][i]; } for (int stable=2; stable<=s; stable++) { for (int i=stable; i<=maxes[stable]; i++) { for (int j=i; j<=maxes[stable]; j++) { int prev = a[i-1][stable-1]; a[j][stable] = Math.min(a[j][stable], unhappines[i][j]+prev ); } } } System.out.println(a[h][s]); } static class FastScanner { BufferedReader br; StringTokenizer st; FastScanner(Reader in) { br = new BufferedReader(in); } String next() { while (st == null || !st.hasMoreTokens()) { try { st = new StringTokenizer(br.readLine()); } catch (IOException e) { e.printStackTrace(); } } return st.nextToken(); } int nextInt() { return Integer.parseInt(next()); } } } #include<bits/stdc++.h> using namespace std; int horse[510],i; long long mem[501][501]; long long count(int index,int left) { if(index==i&&left==0) return 0; if((index==i&&left>0)||(index<i&&left==0)) return 1000000; if(mem[index][left]) return mem[index][left]; int v=0,j=0,k; long long mini=1000001; for(k=index;k<i;k++) { if(horse[k]) v++; else j++; mini=min(mini,v*j+count(k+1,left-1)); } return mem[index][left]=mini; } int main() { int j,k,l; cin>>i>>j; for(k=0;k<i;k++) cin>>horse[k]; cout<<count(0,j)<<endl; return 0; } 1. Инициализация Начинайте с 1 конюшни Пусть нам надо поставить туда I лошадей (I = 1..N) Коэффициент несчастья для I лошадей будет при этом равен White * Black для Horses = 0..i По итогу этого у нас будут оптимальные (потому что единственные) коэффициенты для всех лошадей в случае 1 конюшни 2. Итерации (меняем J-ую конюшню) Надо рассчитать минимальный коэффициент несчастья если в 1..J конюшни поставить I лошадей Для этого переберём все варианты, поставив в J конюшню K лошадей (K = 1..I лошади) и оптимально заполнив первые J-1 конюшни I-K лошадьми (этот коэффициент у нас уже рассчитан на предыдущем шаге итерации) Перебрав все варианты у нас получится оптимальное заполнение первых J конюшен первыми I лошадьми Переходим к J + 1 конюшне и считаем заново все варианты заполнения уже для неё I am using greedy strategy coeff = (unhappiness - possible reduced unhappiness)*length of line x is position to cut the line for min unhappiness ::::: add main list to priority queue with initial unhappiness while(cuts<K){ remove List with max coeff; cut in 2 parts for min unhappiness, calc coeff (for each list); add the 2 parts of list to queue; cuts++; } then poll all queue members(i.e. all cut lines) and add their unhappiness I'm getting all posted tests right.. I tried all variations I could, and I'm getting right answers, but I am getting WA#2, please help!!!! Edited by author 30.12.2013 21:16 My state is f(n,k) so it's obviously a n^3 algo. And the code is very short. But it works fast... Why? Bceause you can do almost 100*10^8 operations in 1 sec :) Are you sure ? 10 milliards ? or 100 millions ? I used DP , 0.8 sec , but some people only used 0.04 sec and uesd less than 100K memory ! why ? How can they do it ? can anybody tell me ? > I used DP , 0.8 sec , but some people only used 0.04 sec and uesd > less than 100K memory ! why ? How can they do it ? can anybody tell > me ? how? i managed a 0.09 O(n^3) but how do u do n^2?? i might have an N^2 ideea but it n^2 memory...... X[i]: how many black horses are in the first i horses Y[i]: how many white horses are in the first i horses We use Dp. F[i,j] = min { F[i-1,k] + (X[j]-X[k])*(Y[j]-Y[k]) } | K<J The answer is F[K,N]. Suppose F[i,j] get the minimal value when k=k0. Let W[i,j]=k0. You can prove : w[i,j-1]<=w[i,j]<=w[i+1,j] So you can solve this problem in o(n^2). Sorry, could you explain please what's k0? #include<cstdio> #include<string.h> #include<algorithm> using namespace std; const int M1 = 555; const int INF = 111111111; int N,K; int ans; int w[M1][M1];//w[i][j] is the number of white horses in the last stable when the first i horses were placed in 1st j stables with minimum unhappiness int b[M1][M1];//b[i][j] is the number of black horses in the last stable when the first i horses were placed in 1st j stables with minimum unhappiness int f[M1][M1];//f[i][j] means the minimum unhappiness when the first i horses were placed in 1st j stables //function: f[i][j] = min(f[i-1][j-1],f[i-1][j]+w[i-1][j] or b[i-1][j]); int main() { memset(w,0,sizeof(w)); memset(b,0,sizeof(b)); memset(f,0,sizeof(f)); scanf("%d%d",&N,&K); for(int i=0;i!=M1;++i) { for(int j=i+1;j!=M1;++j) f[i][j] = INF; f[i][0] = INF; } int tmp; scanf("%d",&tmp); if(tmp) ++b[1][1]; else ++w[1][1]; f[1][1] = 0; for(int i=2;i<=N;++i) { scanf("%d",&tmp); for(int j=1;j<=min(i,K);++j) { f[i][j] = f[i-1][j-1]; b[i][j] = 0; w[i][j] = 0; if(tmp) { ++b[i][j]; if(f[i-1][j]+w[i-1][j]<f[i][j]) { b[i][j] = b[i-1][j]+1; w[i][j] = w[i-1][j]; f[i][j] = f[i-1][j]+w[i-1][j]; } } else { ++w[i][j]; if(f[i-1][j]+b[i-1][j]<f[i][j]) { b[i][j] = b[i-1][j]; w[i][j] = w[i-1][j]+1; f[i][j] = f[i-1][j]+b[i-1][j]; } } } } ans = f[N][K]; printf("%d",ans); return 0; } This is my algorithm. Can anybody tell me why I'm wrong. F(i,j) is the function return to the minimal unhappiness when you consider to the i-th horse and you have used j stables. So that with any k between j and i-1. F(i,j) = F(k,j-1) + the number of white horse multiple to the number of black horse between k and i. So my algorithm is O(n^3). If you can tell me, please send the hint to my email vietlong2110@gmail.com k should be between j-1 and i-1. What I did was of course order 3 but it got AC in 0.062sec and 1133 kb memory. I wonder why n^3 would need .8 sec or TLE. I may do it in n^2 but please tell me about the infamous O(n) algo. please help, i can't find my mistake!!! My algorithm is O(n*(n-k)) but I can't pass test 1 too, Help me, if you can. this is my code. # include <iostream> using namespace std; int main () { char a; int min,num,n,k,i,ans=0; int w[510]={0}; int b[510]={0}; cin>>n>>k; for(i=0;i<n;i++) { cin>>a; if(a=='0') b[i]=1; else w[i]=1; } while(n>k) { min=2147483647; for(i=0;i<n-1;i++) if(min>w[i]*b[i+1]+w[i+1]*b[i]) { min=w[i]*b[i+1]+w[i+1]*b[i]; num=i; } w[num]+=w[num+1]; b[num]+=b[num+1]; for(i=num+1;i<n;i++) { w[i]=w[i+1]; b[i]=b[i+1]; } n--; ans+=min; } cout<<ans<<endl; return 0; }
|
|