Show all threads Hide all threads Show all messages Hide all messages | memory limit | ahmed ezz | 1167. Bicolored Horses | 27 Feb 2023 02:01 | 1 | 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? | Here is my, well commented, O(n^3) solution for reference | Abhishek Gupta | 1167. Bicolored Horses | 22 May 2022 10:19 | 1 | deleted Edited by moderator 23.07.2022 20:36 | getting TLE with python | Yash Sinha | 1167. Bicolored Horses | 28 Sep 2020 14:26 | 1 | did anyone solve it with python? | Does there exist any O(n^2) solution to this problem? | sak3t | 1167. Bicolored Horses | 13 Dec 2017 18:46 | 1 | I have used O(k*n^2) approach. Please explain O(n^2) approach if it exists. | Why WA? (my solution included) So... Simply say what traps are in this problem. PLEASE! | Igor Zubchenok (Belarus SU) | 1167. Bicolored Horses | 24 Sep 2017 19:28 | 5 | 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? Why not ? :"> I have answers to all your questions :) 18 Dec 2001 23:24 Isn't the correct answer 4? 7 2 1 1 0 0 1 1 1 | WA15,hint | LLL | 1167. Bicolored Horses | 28 Sep 2016 17:17 | 1 | 5 2 1 1 1 0 1 ========= 5 2 1 0 1 1 1 | Tip for WA2 - wrong limits | Juve45 | 1167. Bicolored Horses | 17 Sep 2016 14:21 | 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). | Got my AC with C++ solution, the same Python3 solution gets TL2 | renat-nasyrov | 1167. Bicolored Horses | 10 Aug 2016 20:31 | 2 | 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. | I use O(N^3) and got AC in 0.156, why??? | hoan | 1167. Bicolored Horses | 23 Apr 2016 00:56 | 4 | 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? | java AC 1st place | esbybb | 1167. Bicolored Horses | 12 Jul 2015 09:59 | 1 | 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()); } } } | n^2 tle? | Vishal Sharma | 1167. Bicolored Horses | 12 Jun 2014 18:11 | 1 | n^2 tle? Vishal Sharma 12 Jun 2014 18:11 #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; } | Some hint | svg2003 | 1167. Bicolored Horses | 21 Mar 2014 05:53 | 1 | 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 конюшне и считаем заново все варианты заполнения уже для неё | CAN ANYONE TELL ME TEST#2?? GREEDY STRATEGY | Ashwin Kumar | 1167. Bicolored Horses | 30 Dec 2013 14:38 | 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 | So why n^3 algo can finish in 0.078s? | tiancaihb | 1167. Bicolored Horses | 18 Jun 2013 13:47 | 3 | 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 wonder why somebody passed it only used less than 0.1 sec ! | XueMao | 1167. Bicolored Horses | 11 May 2013 23:09 | 5 | 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? | Why my solution WA#1? Help Me! Thanks! | pswgoo | 1167. Bicolored Horses | 15 Jan 2013 09:35 | 1 | #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; } | Could you give me some tests??? I have WA#1!!! PLEASE!!!!! | BOyKA | 1167. Bicolored Horses | 15 Nov 2012 12:07 | 1 | | Why my algorithm WA #2? | vietlong | 1167. Bicolored Horses | 11 Aug 2011 17:04 | 2 | 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. | I Wonder | muhammad | 1167. Bicolored Horses | 25 May 2010 20:36 | 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. | my algo with O(N) get WA#1!! | Bobur | 1167. Bicolored Horses | 30 Jan 2009 02:58 | 2 | 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; }
|
|
|