Any idea ?
Le mardi 21 avril 2020 18:21:29 UTC+2, Quentin a écrit :
>
> 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 google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/9e0be492-2eff-4394-8f14-7420cc17452c%40googlegroups.com.
