Hello all,
My code for Pascal Walk is throwing me a WA for the test set 2 but I don't
know why.
I check that there is not twice the same element used and that two elements
are 'touching' in the triangle but my test have shown no error on eclispe
even if I tested from 1 to 1000.
Here is the code
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);
for(Cell ce : usedCells) {
System.out.println(String.format("%s %s",ce.row+1,ce.k+1));
}
}
}
class valueComparator implements Comparator<Cell>
{
public int compare(Cell c1, Cell c2)
{
return c2.getValue().compareTo(c1.getValue());
}
}
class Cell{
@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) {
this.row = row;
this.k = k;
this.value = ncr(row, k);
}
public boolean findPath(int 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());
}
static int factorial(int n) {
int f;
for(f = 1; n > 1; n--){
f *= n;
}
return f;
}
static int ncr(int n,int r) {
return factorial(n) / ( factorial(n-r) * factorial(r) );
}
}
If you have any clue ?
Thank you.
--
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/acbdd1d9-7ddc-4c44-9269-aee5bd9f0c02%40googlegroups.com.
