Hello all,
I am facing MLE with the pascal triangle last test case but I do not
understand what is the cause of that.
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;
public class Solution {
public static void main(String[] args) {
Scanner scanner = new Scanner( System.in );
int T= scanner.nextInt();
for(int useCase = 0;useCase < T;useCase++) {
solve(scanner,useCase);
}
}
private static void solve(Scanner scanner,int useCase) {
int N= scanner.nextInt();
List<Cell> usedCells = new ArrayList<>();
Cell c = new Cell(0, 0);
c.findPath(N,usedCells);
System.out.println(String.format("Case #%s:", useCase+1));
//System.err.println("N : "+N);
int result = 0;
for(Cell ce : usedCells) {
result += ce.value;
System.out.println(String.format("%s %s",ce.row+1,ce.k+1));
//System.out.println(String.format("%s %s %s
%s",ce.row+1,ce.k+1,ce.value,result));
//System.out.println(result);
}
}
}
class valueComparator implements Comparator<Cell>
{
public int compare(Cell c1, Cell c2)
{
return c2.getValue().compareTo(c1.getValue());
}
}
class Cell{
private static List<int[]> pascalTriangle = new ArrayList<>();
public static List<int[]> generatePascalTriangle(long limit)
{
List<int[]> list = new ArrayList<>();
for(int line = 1;line<=limit; line++)
{
int[] arr = new int[line];
int C=1;// used to represent C(line, i)
for(int i = 1; i <= line; i++)
{
// The first value in a line is always 1
arr[i-1] = C;
//System.out.print(C+" ");
C = C * (line - i) / i;
}
list.add(arr);
// System.out.println();
}
return list;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + k;
result = prime * result + row;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Cell other = (Cell) obj;
if (k != other.k)
return false;
if (row != other.row)
return false;
return true;
}
int row;
int k;
int value;
List<Cell> adjacentCell = new ArrayList<>();
public Integer getValue() {
return this.value;
}
public Cell(int row,int k) {
if(pascalTriangle.isEmpty()) pascalTriangle = generatePascalTriangle(32);
this.row = row;
this.k = k;
this.value = row < pascalTriangle.size() ? pascalTriangle.get(row)[k] :
1_000_000_000;
//ncr(row, k);
}
public boolean findPath(long n, List<Cell> usedCells) {
if(usedCells.size() > 499) return false;
n = n - this.value;
if(n<0) return false;
usedCells.add(this);
if(n==0) return true;
this.addOthersCells();
for(Cell c:
this.adjacentCell.stream().filter(s->!usedCells.contains(s)).collect(Collectors.toList()))
{
if(c.findPath(n, usedCells)) {
return true;
}
}
usedCells.remove(this);
return false;
}
public void addOthersCells() {
int row = Math.max(this.row-1,0);
int col = Math.max(this.k-1,0);
//Row above
if(this.row != row) adjacentCell.add(new Cell(row,col));
col = this.k > row ? row : this.k;
if(this.row != row || this.k != col) if(!adjacentCell.contains(new
Cell(row,col))) adjacentCell.add(new Cell(row,col));
//Same row
row = this.row;
col = Math.max(this.k-1,0);
if(this.k != col) if(!adjacentCell.contains(new
Cell(row,col)))adjacentCell.add(new Cell(row,col));
col = Math.min(this.k+1,row);
if(this.k != col) if(!adjacentCell.contains(new
Cell(row,col)))adjacentCell.add(new Cell(row,col));
//Row below
row = this.row+1;
col = this.k;
if(!adjacentCell.contains(new Cell(row,col)))adjacentCell.add(new
Cell(row,col));
col = this.k+1;
if(!adjacentCell.contains(new Cell(row,col)))adjacentCell.add(new
Cell(row,col));
Collections.sort(adjacentCell,new valueComparator());
}
}
I thought it was the generation of the pascal triangle that cause issue
but if so I should have MLE for test set 1 and 2 and not only for the 3.
Do you have any idea ?
Regards
Quentin
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/8b37ba92-57c8-467d-ac89-4d9401ebad24%40googlegroups.com.
