Elshad Mustafayev
BAN USERWe want to guess the string not to implement getRandomTripplet() method. It is given to you.
- Elshad Mustafayev August 21, 2014I was able to compile it by including <cstring>. However, I tried to execute it with strings other than "wanderlayindustries" and I got segmentation fault all the time.
- Elshad Mustafayev August 21, 2014Most of the times your program's guess is wrong.
- Elshad Mustafayev August 21, 2014import java.util.Scanner;
public class Main {
/*
* Input: n and m
* then nxm matrix.
*
* ex: 3 4
* 1 2 2 2
* 2 2 2 1
* 1 2 2 2
* */
private int n;
private int m;
private int[][] grid;
private int[][] needsProcessing;
int[] upperLeftmostPoint;
int[] lowerRightmostPoint;
public void init(){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
while(n <= 0 || m <= 0) {
System.out.println("Insert valid n and m values");
n = sc.nextInt();
m = sc.nextInt();
}
grid = new int[n][m];
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < m ; j++){
grid[i][j] = sc.nextInt();
}
}
sc.close();
/* process method will determine which cells do not need processing
* in order to prevent repeating some operations and we will use needsProcessing for that.
* */
needsProcessing = new int[n][m];
for(int i = 0 ; i < n ; i ++){
for(int j = 0; j < m ; j ++){
needsProcessing[i][j] = 0;
}
}
/*Initially we assume cell at (0,0) as a submatrix is the result.*/
upperLeftmostPoint = new int[2];
lowerRightmostPoint = new int[2];
upperLeftmostPoint[0] = 0;
upperLeftmostPoint[1] = 0;
lowerRightmostPoint[0] = 0;
lowerRightmostPoint[1] = 0;
}
public void print(){
System.out.println("Upper leftmost: ( " + (upperLeftmostPoint[0] + 1) + " , " + (upperLeftmostPoint[1] + 1) + " )");
System.out.println("Bottom rightmost: ( " + (lowerRightmostPoint[0] + 1) + " , " + (lowerRightmostPoint[1] + 1) + " )");
for(int i = upperLeftmostPoint[0] ; i <= lowerRightmostPoint[0] ; i ++){
for(int j = upperLeftmostPoint[1] ; j <= lowerRightmostPoint[1] ; j ++){
System.out.print(grid[i][j] + " ");
}
System.out.println();
}
}
/*
* We iterate through each cell in the matrix.
* First, k is computed. If current cell's value is x, then k is the count of continuous
* x's below the current cell including x.
* Then we hold the "horizontals" array of k elements. Each of them represents the number of continous x's
* rightwards.
* ex: In matrix
* 2 2 1
* 2 2 2
* 2 1 1
* 1 2 2
* 2 3 1
* If current cell is the first cell which has the value 2. Then k is 3 and
* horizontals array is {2, 3, 1}.
*
* Then we compute the biggest submatrix assuming upper leftmost cell is the current cell
* using horizontals array. For example, here in the same example we first look at the
* horizontals[0]. Take 2 2 as the biggest sub matrix so far. Then look at the second element
* of the horizontals. We see that 2 2 is bigger and so on.
* 2 2
* After processing the current cell at the end we compare what we found with the current cell to
* maxSoFar. Then we update the needed parameters. Also in order to prevent repeating we use needsProcessing
* matrix. We do that by checking the minimum values. If horizontal[minValueIndexSoFar] >= horizontal[y] then we won't need to
* process grid[i + y][j] because grid[i][j] will have done the needed operations and process method will repeat some operations
* while processing grid[i+y][j].
* */
public void process(){
int maxSoFar = (upperLeftmostPoint[0] - upperLeftmostPoint[1] + 1)*(lowerRightmostPoint[0] - lowerRightmostPoint[1] + 1);
for(int i = 0 ; i < n ; i ++){
for(int j = 0; j < m ; j ++) {
if (needsProcessing[i][j] == 0){
int k = 0;
while (k + i < n && grid[i][j] == grid[k + i][j]) k++;
int[] horizontals = new int[k];
for (int s = 0; s < k; s++) {
int t = 0;
while (t + j < m && grid[i + s][j] == grid[i + s][t + j]) t++;
horizontals[s] = t;
}
int minValueIndexSoFar = 0;
int maxOfCurrentSoFar = horizontals[0];
int maxAreaLowerRightmostIndexY = 0;
for (int s = 0; s < k; s++) {
if (horizontals[minValueIndexSoFar] >= horizontals[s]) {
minValueIndexSoFar = s;
/*This means processing grid[i+s][j] is not necessary.*/
needsProcessing[i+s][j] = 1;
}
if (maxOfCurrentSoFar < (s + 1) * horizontals[minValueIndexSoFar]) {
maxOfCurrentSoFar = (s + 1) * horizontals[minValueIndexSoFar];
maxAreaLowerRightmostIndexY = s;
}
}
if (maxOfCurrentSoFar > maxSoFar) {
maxSoFar = maxOfCurrentSoFar;
upperLeftmostPoint[0] = i;
upperLeftmostPoint[1] = j;
lowerRightmostPoint[0] = i + maxAreaLowerRightmostIndexY;
lowerRightmostPoint[1] = j + maxOfCurrentSoFar / (maxAreaLowerRightmostIndexY + 1) - 1;
}
}
}
}
}
public void run(){
init();
process();
print();
}
public static void main(String[] args) {
new Main().run();
}
}
You loop through every cell and as you detect one black cell then you recurse on it to find the black shape holding that black cell. Of course, as you detect black shapes you make them white shapes to prevent repeating yourself.
import java.util.Scanner;
public class Main {
/*
* Input : Row count, Column count then
* the grid with 1's and 0's
* where 1 means black zero means 0.
*
* ex:
* 2 4
* 0 1 1 0
* 1 0 0 1
*
* */
private int n; //row count
private int m; //column count
private int[][] inputGrid;
public void init(){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
/*Surround the input grid with zeros.
* This makes checking neighbours easier.
*/
inputGrid = new int[n+2][m+2];
for(int j = 0 ; j < m+2; j++){
inputGrid[0][j] = 0;
inputGrid[n+1][j] = 0;
}
for(int i = 1 ; i < n+1; i++){
inputGrid[i][0] = 0;
inputGrid[i][m+1] = 0;
for(int j = 1 ; j < m + 1 ; j ++ ){
inputGrid[i][j] = sc.nextInt();
}
}
}
public void detectBlackShape(int i, int j){
inputGrid[i][j] = 0;
if(inputGrid[i][j-1] == 1) detectBlackShape(i, j-1);
if(inputGrid[i-1][j] == 1) detectBlackShape(i-1,j);
if(inputGrid[i+1][j] == 1) detectBlackShape(i+1, j);
if(inputGrid[i][j+1] == 1) detectBlackShape(i, j+1);
}
public int process(){
int count = 0;
for(int i = 1 ; i < n+1 ; i++){
for(int j = 1 ; j < m+1 ; j++){
if(inputGrid[i][j] == 1){
count++;
detectBlackShape(i,j);
}
}
}
return count;
}
public void print(int result){
System.out.println(result);
for(int i = 1 ; i < n+1;i++){
for(int j = 1 ; j < m+1;j++){
System.out.print(inputGrid[i][j] + " ");
}
System.out.println();
}
}
public void run(){
init();
int result = process();
// print(result);
System.out.println(result);
}
public static void main(String[] args) {
new Main().run();
}
}
It is simple dynamic programming problem.
import java.util.Scanner;
public class Main {
/*
* input: First length of array then the values at the indexes.
* n
* a1 a2 ... an
*
* ex:
* 4
* 1 0 0 1
* */
private int[] input;
public void init(){
Scanner sc = new Scanner(System.in);
int size = sc.nextInt();
input = new int[size];
for(int i = 0 ; i < size; i++) input[i] = sc.nextInt();
sc.close();
}
public boolean[] process(){
int size = input.length;
boolean[] others = new boolean[size];
others[size-1] = true;
for(int i = 0 ; i < size-1; i++) others[i] = false;
if(size == 1) return others;
for(int i = size-2; i >= 0; i--){
int radius = input[i];
radius = Math.min(i + radius + 1, size) - i - 1;
for(int j = 1 ; j <= radius; j++){
if(others[i+j] == true) {
others[i] = true;
break;
}
}
}
return others;
}
public void run(){
init();
boolean[] result = process();
// for(int i = 0 ; i < result.length; i++)
// System.out.print(result[0] + " ");
//
// System.out.println();
System.out.println(result[0]);
}
public static void main(String[] args) {
new Main().run();
}
}
This code works for most strings. If in the secret string there is not too much duplicating then this algo will work fine and in most cases it will be able to recover secret string as it is.
- Elshad Mustafayev August 21, 2014