658 - It's not a Bug, it's a Feature!

[Dracoola]

I don't know whats wrong with my program.
It pass all my test cases, but Judge don't want to accept it(Wrong Answer).
Could anyone help me?

[pascal]


type
str1=string[20];
var
n_patches,n_bugs,n_iteration:integer;
str2,s3:str1;
mas:array [1..3,1..100] of str1;
time_max:integer;
r:boolean;
t:integer;
mas2:array [1..200] of str1;
max,ik:integer;
str23:string;
k,sch,temp,product:integer;
number_bugs,number_patches:integer;
nexit:boolean;
x1,x2,x3:string;
k3,p3,j:integer;

function povtor(s1:char;max_n:integer):string;
var
i:integer;
s2:string;
begin
s2:='';
for i:=1 to max_n do
begin
s2:=s2+s1;
end;
povtor:=s2;
end;


function sravn(p1,p2:str1):boolean;
var
temp:boolean;
i:integer;
begin
temp:=true;
i:=1;
while (temp and (i<=n_bugs)) do
begin
if not(((p1='-') and (p2='-')) or ((p1='0') and (p2='0')) or
((p1='+') and (p2='+')) or ((p1='+') and (p2='0')) or
((p1='-') and (p2='0'))) then temp:=false;
i:=i+1;
end;
sravn:=temp;
end;

procedure primenim(var s1,s2:str1);
var
i:integer;
begin
for i:=1 to n_bugs do
begin
if s2[i]='+' then s1[i]:='+';
if s2[i]='-' then s1[i]:='-';
end;
end;

function odinak(s1:str1):boolean;
var
i:integer;
result1:boolean;
begin
result1:=true;
odinak:=true;
i:=1;
while ( result1 and (i<=max)) do
begin
if mas2[i]=s1 then result1:=false;
i:=i+1;
end;
if result1 then
begin
max:=max+1;
mas2[max]:=s1;
odinak:=false;
end;
end;



procedure rek(var s2:str1;var time:integer;var result:boolean);
var
is_el:boolean;
op:integer;
u,c:integer;
s2_old:str1;
time_old:integer;
begin
is_el:=true;
result:=true;
op:=1;
while ( result and (op<=n_patches)) do
begin
if sravn(s2,mas[2,op]) then
begin
val(mas[1,op],u,c);
s2_old:=s2;
primenim(s2,mas[3,op]);
if not odinak(s2) then
begin
time_old:=time;
time:=time+u;
if (s2=povtor('-',n_bugs)) and (time<time_max) then
begin
s2:=s2_old;
max:=max-1;
time_max:=time;
time:=time-u;
end
else
begin

rek(s2,time,is_el);
time:=time_old;
s2:=s2_old;
end
end
else
s2:=s2_old;

end;
op:=op+1;
end;
result:=false;
if time_max<32767 then result:=true;
end;




begin
product:=0;
nexit:=false;

repeat
readln(input,str23);
if str23<>'0 0' then
begin
inc(product);
sch:=0;
k:=pos(' ',str23);
val(copy(str23,k+1,(length(str23)-k)),number_patches,temp);
val(copy(str23,1,k-1),number_bugs,temp);

for ik:=1 to 100 do
begin
mas[1,ik]:='';
mas[2,ik]:='';
mas[3,ik]:='';
end;
for ik:=1 to 200 do
mas2[ik]:='';

for ik:=1 to number_patches do
begin
sch:=sch+1;
readln(input,str23);
k:=pos(' ',str23);
mas[1,sch]:=copy(str23,1,k-1);
mas[2,sch]:=copy(str23,k+1,number_bugs);
mas[3,sch]:=copy(str23,k+2+number_bugs,number_bugs);
end;


n_patches:=number_patches;
n_bugs:=number_bugs;
t:=0;
time_max:=32767;
s3:=povtor('0',n_bugs);
mas2[1]:=s3;
max:=1;
rek(s3,t,r);
if product>1 then writeln(output,'');
writeln(output,'Product ',product:1);
if r then
writeln(output, 'Fastest sequence takes ',time_max:1,' seconds.')
else
writeln(output,'Bugs cannot be fixed.');

end


else
nexit:=true;

until nexit;


end.

[/pascal]

PS: Sorry 4 my English.[/quote]

[DJY]

I try to use Dijkstra's algorithms to solve this problem
but it's too slow...............

Could someone help me or give me some hint
THX.

[Kyku]

I'm having a real trouble with this problem. My solution is based on Dijkstra's algorithm. I think I've tested it thouroughly, but I always get Wrong Answer after a very short time. Could you please give me some hints or test cases that could be tricky?

Here's the prog, for the interested, I've put some comments in it to ease browsing:

Code: Select all

Program BugFeature;

Var
  (* Keeps track of nodes positions in priority queue (which is binary heap) *)
  IdxToHeap: Array[0..1 Shl 20 - 1] Of LongWord;

Type
  (* Pair of cost and value, i.e. shortest path and state number. *)
  TCostValue = Record Cost, Value: LongWord End;

  (* Binary heap based priority queue. *)
  TPQueue = Object
    Procedure Initialize;
    Function Size: LongWord;
    Function Get: LongWord;
    Procedure Put(C, V: LongWord);
    Procedure Decrease(V, C: LongWord);
    Function Empty: Boolean;
    Procedure Clear;

   Private
    m_PQ: Array[0..1 Shl 20 - 1] Of TCostValue;
    m_Size: LongWord;

    Procedure MoveDown(I: LongWord);
    Procedure MoveUp(I: LongWord);
    Procedure SwapItems(I, J: LongWord);
  End;

Procedure TPQueue.Initialize;
Begin
  m_Size := 0
End;

Procedure TPQueue.Decrease(V, C: LongWord);
Begin
  m_PQ[IdxToHeap[V]].Cost := C;
  MoveUp(IdxToHeap[V])  
End;

Function TPQueue.Size: LongWord;
Begin
  Size := m_Size
End;

Function TPQueue.Get: LongWord;
Begin
  If m_Size = 0 Then
    Begin
      WriteLn('Proba pobrania elementu z pustej kolejki.');
      Halt
    End;
  Get := m_PQ[0].Value;
  m_PQ[0] := m_PQ[m_Size - 1];
  IdxToHeap[m_PQ[0].Value] := 0;
  Dec(m_Size);
  MoveDown(0)
End;

Procedure TPQueue.Put(C, V: LongWord);
Begin
  m_PQ[m_Size].Cost := C;
  m_PQ[m_Size].Value := V;
  IdxToHeap[V] := m_Size;
  Inc(m_Size);
  MoveUp(m_Size - 1)
End;

Procedure TPQueue.MoveUp(I: LongWord);
Var
  P: LongWord;
Begin
  While I > 0 Do
    Begin
      P := (I - 1) div 2;
      If m_PQ[P].Cost > m_PQ[I].Cost Then
        Begin
          IdxToHeap[m_PQ[P].Value] := I;
          IdxToHeap[m_PQ[I].Value] := P;
          SwapItems(P, I);
          I := P
        End
      Else
        I := 0
    End
End;

Procedure TPQueue.MoveDown(I: LongWord);
Var
  B, L, R, Last: LongWord;
Begin
  If m_Size > 1 Then
    Begin
      Last := m_Size div 2 - 1;
      While I <= Last Do
        Begin
          L := 2 * I + 1;
          R := L + 1;
          B := I;
          If m_PQ[L].Cost < m_PQ[I].Cost Then B := L;
          If (R < m_Size) And (m_PQ[R].Cost < m_PQ[B].Cost) Then B := R;
          If B <> I Then
            Begin
              IdxToHeap[m_PQ[B].Value] := I;
              IdxToHeap[m_PQ[I].Value] := B;
              SwapItems(B, I);
              I := B
            End
          Else
            I := Last + 1
        End
    End
End;

Function TPQueue.Empty: Boolean;
Begin
  Empty := m_Size = 0
End;

Procedure TPQueue.SwapItems(I, J: LongWord);
Var
  T: TCostValue;
Begin
  T := m_PQ[I];
  m_PQ[I] := m_PQ[J];
  m_PQ[J] := T
End;

Procedure TPQueue.Clear;
Begin
  m_Size := 0;
End;


Const
  LONGWORDMAX : LongWord = LongWord(-1);

Type
  TPatch = Record
    (* What this patch requires & which bugs are unimportant in checking if this patch can be applied *)
    ReqPresentAbsent, ReqIndifferent: LongWord;
    (* What this patch changes & what it leaves alone. *)
    SetPresentAbsent, SetIndifferent: LongWord;
    (* How long it takes to apply this patch. *)
    Time: LongWord;
  End;

  TColor = (WHITE, GRAY, BLACK); {White - node processed, Gray - in frontier set, Black - not visited yet.}

Var
  (* Ordinal number of product, numbers of bugs and patches. *)
  Number, NumBugs, NumPatches: LongWord;
  (* Strings storing prerequisites and changes of a patch. *)
  Requires, Provides: String;
  (* Information about patches go here. *)
  Patches : Array[1..99] Of TPatch;
  (* Cache used for speeding up recursion. There is one cell for each possible state.
    The contens of a cell contains minimal time necesassary to remove all bugs in this
    state or ST_INIFINITY if the bugs present in thes state can't be removed. *)
  (* Temporary vars. *)
  Time, I, P: LongWord;
  (* Lengths to various states *)
  Lengths: Array[0..1 shl 20 - 1] Of LongWord;
  Colors: Array[0..1 shl 20 - 1] Of TColor;


Function Min(A, B: LongWord): LongWord;
Begin
  If A < B Then Min := A Else Min := B
End;

(* Returs true if patch with indexed by PatchNum can be applied to state BugState. *)
Function PatchCanBeApplied(PatchNum: Integer; BugState: LongWord): Boolean;

Var
  SameBits, Mask: LongWord;
Begin
  (* Zeroes those bits that are the same in patch ang bug. *)
  SameBits := Patches[PatchNum].ReqPresentAbsent Xor BugState;
  (* Additionaly don't take into account bugs that are unimportant for the patch. *)
  Mask := Not Patches[PatchNum].ReqIndifferent;
  PatchCanBeApplied := (SameBits And Mask) = 0
End;

(* Return state resulting from applying the patch indexed by PatchNum to a state. *)
Function ApplyPatch(PatchNum: Word; BugState: LongWord): LongWord;

Begin
  BugState := BugState Or (* Set necessary bits *)
    (Patches[PatchNum].SetPresentAbsent And Not Patches[PatchNum].SetIndifferent);
  BugState := BugState And (* Clear necessary bits *)
    (Patches[PatchNum].SetPresentAbsent Or Patches[PatchNum].SetIndifferent);
  ApplyPatch := BugState
End;


Procedure ParsePatch;

Var
  J, ReqA, ReqI, SetA, SetI, Mask: LongWord;
Begin
  Mask := 1; (* Mask of the bit that is currently being proccessed. *)
  ReqA := 0; (* Stores which bits are required to be present or absent for this patch to be applied. *)
  ReqI := 0; (* Which bits are unimportant for this patch *)
  SetA := 0; (* Which bits this patch changes.  *)
  SetI := 0; (* Which bits are left unaffected by this patch. *)
  For J := Length(Requires) Downto 1 Do
    Begin
      Case Requires[J] Of
        '+':
          ReqA := ReqA Or Mask;
        '0':
          ReqI := ReqI Or Mask;
      End;
      Case Provides[J] Of
        '+':
          SetA := SetA Or Mask;
        '0':
          SetI := SetI Or Mask;
      End;
      Mask := Mask Shl 1
    End;
  (* Store values in the patch array. *)
  Patches[I].Time := Time;
  Patches[I].ReqPresentAbsent := ReqA;
  Patches[I].ReqIndifferent := ReqI;
  Patches[I].SetPresentAbsent := SetA;
  Patches[I].SetIndifferent := SetI
End;

Var PQ: TPQueue;

Procedure ShortestPath(State: LongWord);
Var
  Y, Z: LongWord;
  I: Word;
Begin
  PQ.Initialize;
  Lengths[1 Shl NumBugs - 1] := 0;
  Colors[1 Shl NumBugs - 1] := WHITE;
  For I := 0 To 1 Shl NumBugs - 2 Do
    Begin
      Lengths[I] := LONGWORDMAX;
      Colors[I] := BLACK
    End;              
  PQ.Put(0, State);
  While Not PQ.Empty Do
    Begin
      Y := PQ.Get;
      Colors[Y] := WHITE;
      For I := 1 To NumPatches Do
        If PatchCanBeApplied(I, Y) Then
          Begin
            Z := ApplyPatch(I, Y);
            If Colors[Z] <> WHITE Then
              If Colors[Z] = BLACK Then
                Begin
                  Lengths[Z] := Patches[I].Time + Lengths[Y];
                  PQ.Put(Lengths[Z], Z);
                  Colors[Z] := GRAY
                End
              Else
                Begin
                  Lengths[Z] := Min(Lengths[Z], Patches[I].Time + Lengths[Y]);
                  PQ.Decrease(Z, Lengths[Z])
                End
          End
    End;
  PQ.Clear
End;


Begin
  Number := 1; (* number of test case *)
  ReadLn(NumBugs, NumPatches);
  While (NumBugs <> 0) And (NumPatches <> 0) Do
    Begin
      WriteLn('Product ', Number);
      For I := 1 To NumPatches Do (* Read all patches. *)
        Begin
          (* Parse info about a single patch. *)
          ReadLn(Time, Requires);
          Requires := Copy(Requires, 2, 255);
          P := Pos(' ', Requires);
          Provides := Copy(Requires, P + 1, 255);
          Requires := Copy(Requires, 1, P - 1);
          ParsePatch
        End;
      (* Start Dijsktra's algorithm with all bugs present. *)
      ShortestPath(1 Shl NumBugs - 1);
      If Lengths[0] = LONGWORDMAX Then
        WriteLn('Bugs cannot be fixed.')
      Else
        WriteLn('Fastest sequence takes ', Lengths[0], ' seconds.');
      WriteLn;
      Inc(Number); (* Prepare for the next case. *)
      ReadLn(NumBugs, NumPatches)
    End
End.

[little joey]

Code: Select all

  Patches : Array[1..99] Of TPatch; 

This array is too small, there can be as many as 100 patches

Your program gives up too soon on the 'horror' cases:

Code: Select all

18 18
10 000000000000000000 00000000000000000-
10 00000000000000000- 0000000000000000-+
10 0000000000000000-- 000000000000000-++
10 000000000000000--- 00000000000000-+++
10 00000000000000---- 0000000000000-++++
10 0000000000000----- 000000000000-+++++
10 000000000000------ 00000000000-++++++
10 00000000000------- 0000000000-+++++++
10 0000000000-------- 000000000-++++++++
10 000000000--------- 00000000-+++++++++
10 00000000---------- 0000000-++++++++++
10 0000000----------- 000000-+++++++++++
10 000000------------ 00000-++++++++++++
10 00000------------- 0000-+++++++++++++
10 0000-------------- 000-++++++++++++++
10 000--------------- 00-+++++++++++++++
10 00---------------- 0-++++++++++++++++
10 0----------------- -+++++++++++++++++
17 17
10 00000000000000000 0000000000000000-
10 0000000000000000- 000000000000000-+
10 000000000000000-- 00000000000000-++
10 00000000000000--- 0000000000000-+++
10 0000000000000---- 000000000000-++++
10 000000000000----- 00000000000-+++++
10 00000000000------ 0000000000-++++++
10 0000000000------- 000000000-+++++++
10 000000000-------- 00000000-++++++++
10 00000000--------- 0000000-+++++++++
10 0000000---------- 000000-++++++++++
10 000000----------- 00000-+++++++++++
10 00000------------ 0000-++++++++++++
10 0000------------- 000-+++++++++++++
10 000-------------- 00-++++++++++++++
10 00--------------- 0-+++++++++++++++
10 0---------------- -++++++++++++++++
16 16
10 0000000000000000 000000000000000-
10 000000000000000- 00000000000000-+
10 00000000000000-- 0000000000000-++
10 0000000000000--- 000000000000-+++
10 000000000000---- 00000000000-++++
10 00000000000----- 0000000000-+++++
10 0000000000------ 000000000-++++++
10 000000000------- 00000000-+++++++
10 00000000-------- 0000000-++++++++
10 0000000--------- 000000-+++++++++
10 000000---------- 00000-++++++++++
10 00000----------- 0000-+++++++++++
10 0000------------ 000-++++++++++++
10 000------------- 00-+++++++++++++
10 00-------------- 0-++++++++++++++
10 0--------------- -+++++++++++++++
15 15
10 000000000000000 00000000000000-
10 00000000000000- 0000000000000-+
10 0000000000000-- 000000000000-++
10 000000000000--- 00000000000-+++
10 00000000000---- 0000000000-++++
10 0000000000----- 000000000-+++++
10 000000000------ 00000000-++++++
10 00000000------- 0000000-+++++++
10 0000000-------- 000000-++++++++
10 000000--------- 00000-+++++++++
10 00000---------- 0000-++++++++++
10 0000----------- 000-+++++++++++
10 000------------ 00-++++++++++++
10 00------------- 0-+++++++++++++
10 0-------------- -++++++++++++++
0 0

The output should be

Code: Select all

Product 1
Fastest sequence takes 2621430 seconds.

Product 2
Fastest sequence takes 1310710 seconds.

Product 3
Fastest sequence takes 655350 seconds.

Product 4
Fastest sequence takes 327670 seconds.

But your program replies "Bugs cannot be fixed." for the first two cases.

Nice code, BTW.
One point of minor critique: don't use global ('temporary') variables I and Time to communicate with procedure ParsePatch. I'll bet it is the reason for your second bug: The procedure ShortestPath() declares and uses it's own variable I, and it's hard to see that this one is different from the global I.

Happy hunting!

PS. And another nit-pick: move the array IdxToHeap inside the object TPQueue. It realy belongs there and then you can re-use the object if you want more than one Queue in your code.

[Kyku]

Thanks for the tips man, you are my Idol now
The mistakes were rather stupid. Test cases helped me the most. The real source of the problem was that variable "I" in ShortestPath that I used to index Lengts and Colors arrays was declared as Word, and therefore it couldn't span all the elements. Therefore in large (in terms of numbers of bugs) input cases, not everything got initialized. I guess it's because of my lack of proficiency in Pascal. Usually I prefer C, but I just couldn't resist the temptation to write in some different language.

[trance8]

Hey!
I'm looking for sample input and correct output to this problem.

For example:
Input:

15 15
10 000000000000000 00000000000000-
10 00000000000000- 0000000000000-+
10 0000000000000-- 000000000000-++
10 000000000000--- 00000000000-+++
10 00000000000---- 0000000000-++++
10 0000000000----- 000000000-+++++
10 000000000------ 00000000-++++++
10 00000000------- 0000000-+++++++
10 0000000-------- 000000-++++++++
10 000000--------- 00000-+++++++++
10 00000---------- 0000-++++++++++
10 0000----------- 000-+++++++++++
10 000------------ 00-++++++++++++
10 00------------- 0-+++++++++++++
10 0-------------- -++++++++++++++
0 0

And my output:
Product 1
Fastest sequence takes 327670 seconds.


(in 30sec, is this long?)

I have still TLE
What's means: Running (5)? 5th test case?

[Kyku]

Look at: http://acm.uva.es/board/viewtopic.php?t=7179

[L I M O N]

pls someone help me to speed up this problem. i got tle again and again.
i use Dij...

thanks in Advance

L I M O N

[ral]

You have to use bitmask to avoid TLE.

[ral]

Hint: bitmask

[DD]

pls someone help me to speed up this problem. i got tle again and again.
i use Dij...

thanks in Advance

L I M O N

Be sure that your Dijkstra was implemented with heap, and use bitmask to speed up on patch.
My program implemented in this way and got A.C. about 1.5 secs.
Hope this can help you.

[wjomlex]

I'm getting WA, though I've tested it quite thoroughly. If someone has some good test cases, I'd greatly appreciate it. My code works with the ones already given in this thread.

The integers bp, bm, fp, and fm correspond to B+, B-, F+, and F-, as per the problem description.

I've overloaded Point to take longs, because I wanted to make sure that I handled cases where the shortest path might be greater than 2^31.

Code: Select all

import java.util.*;
import java.io.*;

public class Main
{
	public static Comparator<Point> cmp = new Comparator<Point>()
	{
		public int compare(Point a, Point b)
		{
			if(a.y < b.y)
				return -1;
			else if(a.y > b.y)
				return 1;
			else
				return 0;
		}
	};

	public static void main(String args[]) throws IOException
	{
		BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int cases = 0;

		while(true)
		{
			cases++;
			st = new StringTokenizer(scan.readLine());
			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());

			if(n == 0 && m == 0)
				break;

			Patch[] a = new Patch[m];

			for(int i=0;i < m;i++)
			{
				st = new StringTokenizer(scan.readLine());
				int t = Integer.parseInt(st.nextToken());
				String b = st.nextToken();
				String f = st.nextToken();

				int bm = 0;
				int bp = 0;

				for(int j=0;j < n;j++)
					if(b.charAt(j) == '+')
						bp |= (1 << j);
					else if(b.charAt(j) == '-')
						bm |= (1 << j);

				int fm = (1 << n)-1;
				int fp = 0;

				for(int j=0;j < n;j++)
					if(f.charAt(j) == '+')
						fp |= (1 << j);
					else if(f.charAt(j) == '-')
						fm -= (1 << j);

				a[i] = new Patch(t,bp,bm,fp,fm);
			}

			//Dijkstra
			long[] d = new long[1 << n];
			Arrays.fill(d, Long.MAX_VALUE);
			d[d.length-1] = 0;

			PriorityQueue<Point> q = new PriorityQueue<Point>(10,cmp);
			q.offer(new Point(d.length-1, 0));

			while(!q.isEmpty() && d[0] == Long.MAX_VALUE)
			{
				Point cur = q.poll();

				//System.out.println("Polling " + bits(cur.x) + ", " + cur.y);

				//Ignore deprecated points
				if(cur.y > d[cur.x])
					continue;

				for(int i=0;i < m;i++)
				{
					//Does this patch apply?
					if((cur.x & a[i].bp) != a[i].bp)
						continue;
					if((cur.x & a[i].bm) > 0)
						continue;

					//What will the result be?
					int res = cur.x;

					res |= a[i].fp;
					res &= a[i].fm;					

					//Is this an improvement?
					if(d[res] > d[cur.x] + a[i].t)
					{
						d[res] = d[cur.x] + a[i].t;
						q.offer(new Point(res, d[res]));
					}
				}
			}

			//Output
			System.out.println("Product " + cases);

			if(d[0] == Long.MAX_VALUE)
				System.out.println("Bugs cannot be fixed.\n");
			else
				System.out.println("Fastest sequence takes "+ d[0] +" seconds.\n");
			

		}
	}
}


class Patch
{
	public int t, bp, bm, fp, fm;

	public Patch(int t, int bp, int bm, int fp, int fm)
	{
		this.t = t;
		this.bp = bp;
		this.bm = bm;
		this.fp = fp;
		this.fm = fm;
	}
}


class Point
{
	public int x;
	public long y;

	public Point(int x, long y)
	{
		this.x = x;
		this.y = y;
	}
}

[LeChuck]

Hi, I get Wrong Answer for this code, and can not find an error. Its passes all testcases in this thread, can you pleeease give me more testcases? Really great would be a testcase where my code fails.

Code: Select all

import java.util.LinkedList;
import java.util.Scanner;



public class Main {

	static LinkedList<Patch> patches;
	static Heap warteschlange;
	static int[] buginfo;
	static int[] posinheap;
	static int tempcost;
	

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int produktNr = 0;
		while (true) {
			produktNr++;
			int bugs = sc.nextInt();
			if (bugs == 0)
				break;
			int patchn = sc.nextInt();

			patches = new LinkedList<Patch>();
			for (int i = 0; i < patchn; i++) {
				patches.add(new Patch(sc.nextInt(), sc.next(), sc.next()));
			}
			
			int zweihoch = 1 << bugs;

			warteschlange = new Heap(zweihoch);
			buginfo = new int[zweihoch];
			posinheap = new int[zweihoch];

			warteschlange.add(zweihoch-1);
			for(int i=0;i<zweihoch;i++){
				buginfo[i] = 1000000000;
			}
			buginfo[zweihoch-1]=0;
			
			
			int gesamtkosten = Integer.MAX_VALUE;

			while (!warteschlange.isEmpty()) {
				int aktZ = warteschlange.poll();

				if (aktZ == 0) {
					gesamtkosten = buginfo[0];
					break;
				}

				for (Patch pa : patches) {
					if(pa.isAppliable(aktZ)){
						int newZ = pa.doApply(aktZ);

						if (buginfo[newZ] > tempcost) {
							if (buginfo[newZ] < 1000000000) {
								buginfo[newZ] = tempcost;
								warteschlange.update(newZ);
							} else {
								warteschlange.add(newZ);
								buginfo[newZ] = tempcost;
							}
						}
					}
					
				}
			}

			if (gesamtkosten == Integer.MAX_VALUE) {
				System.out.println("Product " + produktNr);
				System.out.println("Bugs cannot be fixed.");
				System.out.println();
			} else {
				System.out.println("Product " + produktNr);
				System.out.println("Fastest sequence takes " + gesamtkosten
						+ " seconds.");
				System.out.println();
			}

		}

	}

	

	private static class Heap {

		int[] derHeap;
		int size;

		public Heap(int zweihoch) {
			super();
			derHeap = new int[zweihoch];
			size = 0;
		}

		public void update(int zustand) {
			heapyfyToRoot(posinheap[zustand]);
		}

		public void add(int zustand) {
			size++;
			derHeap[size] = zustand;
			posinheap[zustand] = size;
			heapyfyToRoot(size);

		}

		public int poll() {
			int result = derHeap[1];
			swap(1, size);
			size--;

			heapyfyToLeaf(1);
			return result;
		}

		public boolean isEmpty() {
			return size == 0;
		}

		private void heapyfyToRoot(int i) {
			if (i == 1) {
				return;
			}
			if (buginfo[derHeap[i / 2]] > buginfo[derHeap[i]]) {
				swap(i / 2, i);
				heapyfyToRoot(i / 2);
			}
		}

		private void heapyfyToLeaf(int i) {
			if (2 * i > size) {
				return;
			}
			if (2 * i == size) {
				if (buginfo[derHeap[i]] > buginfo[derHeap[2 * i]]) {
					swap(i, 2 * i);
				}
				return;
			}

			int tauschpartner = 2 * i;
			if (buginfo[derHeap[2 * i + 1]] < buginfo[derHeap[2 * i]]) {
				tauschpartner = 2 * i + 1;
			}

			if (buginfo[derHeap[i]] > buginfo[derHeap[tauschpartner]]) {
				swap(i, tauschpartner);
				heapyfyToLeaf(tauschpartner);
			}
		}

		private void swap(int i, int j) {
			int temp = derHeap[i];
			int tpos = posinheap[derHeap[i]];

			derHeap[i] = derHeap[j];
			posinheap[derHeap[i]] = posinheap[derHeap[j]];

			derHeap[j] = temp;
			posinheap[derHeap[j]] = tpos;

		}

	}

	private static class Patch {

		int cost = 0;
		int bp = 0;
		int bm = 0;
		int fp = 0;
		int fm = 0;

		public Patch(int cost, String req, String eff) {

			if (cost <= 0)
				throw new RuntimeException();
			this.cost = cost;

			for (int i = 0; i < req.length(); i++) {
				char c = req.charAt(i);
				if (c == '+') {
					bp += (1 << i);
				} else if (c == '-') {
					bm += (1 << i);
				}
			}
			if ((bp & bm) != 0)
				throw new RuntimeException();

			for (int i = 0; i < eff.length(); i++) {
				char c = eff.charAt(i);
				if (c == '+') {
					fp += (1 << i);
				} else if (c == '-') {
					fm += (1 << i);
				}
			}
			if ((fp & fm) != 0)
				throw new RuntimeException();
		}


		int doApply(int zustand) {
			tempcost = buginfo[zustand]+cost;

			zustand |= fp;
			zustand &= ~fm;
			return zustand;

		}

		boolean isAppliable(int zustand) {
			if ((~zustand & bp) != 0)
				return false;
			if ((zustand & bm) != 0)
				return false;
			return true;

		}
	}
}

[Farsan]

At first i tried bitmask DP but was getting RTE,may be pushing too much state on stack.Then tried dijkstra (using bitmask).Got AC,took time around 1.4s.

[just_yousef]

Why RTE ??

Code: Select all

Solved :D