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.

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.

if you have a better algo please tell to me.

plz help!!!!!!!!!!!!!!!

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?

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 ?

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

thanx!!!

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

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!!!