Use dp + bitmask. I got AC in 0.015 and 1M

Edited by author 14.03.2024 00:30

It was due to overflow. I changed a few variables to long long and it got accepted.

Edited by author 25.08.2015 13:20

Edited by author 25.08.2015 13:20

somebody faced this problem? somebody has a test data?

My sulution a has n^2 * 2 ^ n and get TL
accepted solution supposed to be O(n * 2^n), right?

B)

I got tl5 using recursion solution, and i dont know how to optimize it.
Please give me some hints how to solve it better

Thanks :)

Recursion solution - tl5, recursion with non-asymptotic optimization - ac 0.046

I solved this problem by used recursion without DP.
I'm trying to find a solution using DP, I found a public solution using DP + Bitmark, but it's hard to me to understand.
How can I solve this problem using DP without Bitmark???

Я решил стандартно с помощью маски: Dp[mask], где mask - очередное состояние. Рассмотрел все переходы с потерями и выбрал минимальный из них. Асимптотика O(N*2^N). Как решить эффективней (кроме оптимизации в переходах,т.е. не рассматривать,скажем три нуля подряд в маске) не знаю. Может,кто-нибудь даст идею,как кроме стандартной лобовой маски решить?

Hi,
I'm interested if there is solution for larger N like 1000 and even more?

Thanks.

Edited by author 25.03.2013 01:28

I've wrote recursion and got AC with 0.109 s ..... Can anybody tell me how to solve it using DP ?

Please give me some tests. I use DFS,but WA4.

Edited by author 19.05.2011 17:52

I am getting wrong answer for test case 12 again and again. Any idea where can be the problem or what can be the test case?

I don’t know how, but my solution (brutforce) get AC with time 0.031 and memory 216 KB))

why WA 7 ?
var
  n,k,t,p,sum,inf,c,k2,w:integer;
  a:array[0..25] of integer;
  d:array[0..5048576] of integer;
  i,j,q:integer;

begin
  read(n);
  inf := maxint div 2;
  for i := 0 to n - 1 do
    read(a[i]);
  k := 1 shl n;
  k2 := k shl 1;
  for i := 1 to k do
    d[i] := inf;
  d[0] := 0;
  Dec(k);

  for i := 0 to k do begin
    if (d[i] = inf) then
      Continue;
    sum := 0;
    for j := 0 to n - 1 do begin
      t := i or (7 shl j);
      if (t > k) and (t < k2) then begin
        t := t shr 1;
        t := t and (not(1 shl (n - 3)));
        t := t or 1;
      end;
      if (t >= k2) then begin
        t := t shr 2;
        t := t and (not (1 shl (n - 3)));
        t := t and (not (1 shl (n - 2)));
        t := t or 3;

      end;
      sum := 0;
      for q := 0 to n - 1 do
      if (t shr q) and 1 = 0 then
        sum := sum + a[n - q - 1];

      if d[t] > d[i] + sum then
        d[t] := d[i] + sum;
      c := d[k];
    end;
  end;
  writeln(d[k]);

end.

I already got AC using the same code but only changing a little thing .....
that's why I deleted the code....

Edited by author 27.05.2011 09:48

I'm using brute search with pruning, and all the cases which I tested
seems alright, but I still get WA. Is there any trick?

My code:

[code deleted]


Edited by moderator 28.07.2006 10:35

I have WA3. May be I don't understand this problem.
#include <stdio.h>

int main()
{
    int n,a[20],i,s=0,rez=0;
    scanf("%i",&n);
    for (i=0; i<n; i++)
    {
        scanf("%i",&a[i]);
        s=s+a[i];
    }

    /*for (i=0; i<n; i++)
        printf("%i",a[i]);*/

    int maxs,maxi,j,sdop,k;
    bool ok=true;

    while (ok)
    {
        maxs=0;

    for (i=0; i<n; i++)
    {
        sdop=0;
        for (j=i; j<=i+2; j++)
        {
            if (j>n-1) sdop=sdop+a[j%n];
            else sdop=sdop+a[j];
        }
        if (sdop>maxs)
        {
            maxs=sdop;
            maxi=i;
        }
    }

    s=s-maxs;
    rez=rez+s;

    int d1,d2,d3;
    d1=maxi;
    if (maxi+1>n-1) d2=(maxi+1)%n;
    else d2=maxi+1;
    if (maxi+2>n-1) d3=(maxi+2)%n;
    else d3=maxi+2;

    a[d1]=0;
    a[d2]=0;
    a[d3]=0;

    ok=false;
    k=0;
    while (!ok && k<n)
    {
        if (a[k]!=0) ok=true;
        else k++;
    }

    }
    printf("%i",rez);

    return 0;
}

How to solve it faster and use less memory?

Edited by author 01.07.2009 17:14