Where do my solutions fail? (Fill the cube and Jogging ground from TCS Codevita)

Now that TCS Codevita is over I can finally get this off my chest. I cannot see where my solutions to these problems fail.

The questions are at this link (https://imgur.com/8wCo0DN)
I hope they’re readable.

1. Fill the cube

Here’s my solution to it:
I’ve put comments to guide you through the solution. I believe my macros are quite straight forward so that shouldn’t affect readability that much.

// Read this function after solve
int maxgap(vi &rem) {
    // The goal of this function is to find the length of
    // the largest square shaped empty space in the function.
    int res = 0, n = rem.size();
    foi(i, 0, n) {
        foi(j, i, n) {
            // i and j are the inclusive limiters for the current range
            // curr is the square cavity in the range
            int curr = INF;
            // This loop calculates the limiting vertical space of the range
            for (int x = i; x <= j; ++x) {
                curr = min(curr, rem[x]);
            }
            // (j - i + 1) is the length of the range or the limiting horizontal space
            curr = min(j - i + 1, curr);
            res = max(res, curr);
        }
    }
    return res;
}

void solve() {
    int n; cin >> n;
    vvi w(n, vi(n));
    
    // Changing C's to 1 and D's to 0 to make the calculations ahead a bit simpler.
    char temp;
    foi(i, 0, n) {
        foi(j, 0, n) {
            cin >> temp;
            if (temp == 'C') w[i][j] = 1;
            else  w[i][j] = 0;
        }
    }

    // Only two rotations matter one "upright" and one "sideways".  
    // I calculate the number of bricks in each column in u and row in s. 
    // After that I change from number of bricks to number of empty spaces
    vi u(n), s(n);
    foi(i, 0, n) {
        foi(j, 0, n) {
            u[j] += w[i][j];
            s[i] += w[i][j];
        }
    }
    iter(i, u) i = n - i;
    iter(i, s) i = n - i;

    // Now read the maxgap function
    cout << max(maxgap(u), maxgap(s));
}

2. Jogging ground

Here’s my solution to it:
It’s really straight forward python code so shouldn’t be a problem understanding it. I can’t see why this one would fail. Note that in the original solution I replaced dist with my own function because turns out python 3.6.x, the version used by the contest compiler didn’t have it

from math import sin, cos, radians, dist

r, d1, d2, d3 = [int(x) for x in input().split()]
angles = [int(x) for x in input().split()]
velocs = [int(x) for x in input().split()]
direcs = [1 if x == '1' else -1 for x in input().split()]
n = int(input())

a1, a2, a3, a4 = [angles[i] + (direcs[i]*velocs[i]*n)
        for i in range(0, 4)]

def xyd(angle, radius, distance):
    angle = radians(angle)
    y = radius * sin(angle)
    x = radius * cos(angle) + distance
    return x, y

x1, y1 = xyd(a1, r, 0)
x2, y2 = xyd(a2, r, d1)
x3, y3 = xyd(a3, r, d2)
x4, y4 = xyd(a4, r, d3)

z1 = dist((x1, y1), (x2, y2))
z2 = dist((x2, y2), (x3, y3))
z3 = dist((x3, y3), (x4, y4))

print(round(z1 + z2 + z3), end="")

Both my solutions did pass the “Public” tests so am I missing something?

1 Like

In the first problem, what is vi?
can you share the full code?
what INF?

Those are my macros,
vi is vector of ints, vvi is vector of vector of ints
INF is 1e5 + 5
foi(i, 0, n) is for (int i = 0; i < n; ++i)
iter(i, d) is for (auto &x: d)

@puipuituipui puipuituipui I want to solve your problem but after looking your code, I’m way beyond to understand because I’ve never used these terms (ie) in your code. I’m surprised to see that your solution is looks very small.
Below is my code for Fill the Cube: [You’d be surprised to see my code’s length and it took me more than 4 hours to solve this lol:) ]

import java.util.*;

class Cube{
	// anti-clockwise direction 
    public void rotateMatrix( int N, int mat[][]) 
    { 
        // Consider all squares one by one 
        for (int x = 0; x < N / 2; x++) { 
            // Consider elements in group 
            // of 4 in current square 
            for (int y = x; y < N - x - 1; y++) { 
                // Store current cell in 
                // temp variable 
                int temp = mat[x][y]; 
                // Move values from right to top 
                mat[x][y] = mat[y][N - 1 - x]; 
                // Move values from bottom to right 
                mat[y][N - 1 - x] 
                    = mat[N - 1 - x][N - 1 - y]; 
                // Move values from left to bottom 
                mat[N - 1 - x][N - 1 - y] = mat[N - 1 - y][x]; 
                // Assign temp to left 
                mat[N - 1 - y][x] = temp; 
            } 
        }
    } 
    
    //For melting of matrix
    /* Melting is done by taking the first column
     * Then two variables top and down
     * top point to the first element of the first column
     * down points to the last element of the first column
     * top and down moves towards each other by iterating the elements in the first column from their position
     * if top founds a 'D' (ie) zero in our case, then it'll change it to -1 to denote space and move to next element
     * if top founds a 'C', top will get assigned to C and wait for down to find a 'D'
     * if down finds a 'D' iterating from the bottom , then down will change the 'D' to 'C' and top will change it's 'C' to space (ie) '-1'
     * and then top will continue to search for another C while continuously changing 'D' to space
     * Thus the first column will be melted and it'll be repeated for the remaining columns
     */
    public void melting(int N, int mat[][]) {
    
    	for(int i=0;i<N;i++) {
    		int top=0;
    	    int down=N-1;
    	  for(int loop=0;loop<N;loop++) {
    		  if(top>down) {
    			  break;
    		  }
    		for(;top<N;top++) {
    			if(mat[top][i]==0) {
    				mat[top][i]=-1; //To denote the space as -1 after C drops
    			}
    			else if(mat[top][i]==1) {
    			   break;
    			}
    		}
    		for(;down>0;down--) {
    			if(mat[down][i]==0) {
    				mat[down][i]=1; //changes down to 1 and top to -1 to make the matrix look melted
    				mat[top][i]=-1; //To denote the space as -1 after C drops
    				top++;
    				down--;
    				break;
    			}
    		}
    		
    	  }
    	}

    }
    
    
    /*For finding the square wall to be fit inside the melted matrix
     * We'll create a 1D array of size N which is the wall_size given as input 
     * Assign all the elements of array from 1 to the input N ex: arr[0]=1, arr[1] = 2 ......arr[N-1]=N
     * We'll use each element of the array as the square wall size to fit into our melted matrix
     * and assign -1 to the respective array[i] if it fits inside our matrix
     * Atlast we'll iterate our fully checked array from the last index arr[N] and if arr[i] matches -1 
     * then we'll return the correspinding array element position as the biggest square to be fitted to our matrix
     * To check if a square fits our matrix, we'll take the first column and iterate from top
     * We'll continue our iteration and count the no.of iterations of spaces in our first column
     * If we find a C instead of a space then we'll stop the iteration and check if no.of iteration == array[i]
     * If it satisfies then we'll increment a new variable called loop and check whether loop == array[i]
     * If it equals then we've successfully fitted a square and assign array[i]=-1 and move on the next element in our array
     * if not then we'll move on to next column till loop==array[i]
     * if no.of iterations < array[i] then we'll move to next column while setting loop back to 0 and check from first 
     * whether we can fit a square. If not we'll not assign -1 to our array.
     */
    public int wall_size(int N,int mat[][]){
    	
    	   int[] arr = new int[N];
    	    for(int i=0;i<N;i++) {
    	    	arr[i]=(i+1);
    	    }
    	    
    	    
    	    
    	    for(int i=0;i<arr.length;i++) {
    	    	int loop=0;
  
    	    	for(int col=0;col<N;col++) {
    	  	    	int count =0;
    	    		for(int row=0;row<N;row++ ) {
    	    			if(count==arr[i]) {
    	    				break;
    	    			}
    	    			if(mat[row][col]==-1) {
    	    			    count++;
    	    			    //For Debugging
    	    			    //System.out.println("column: "+col +"Row: "+row);
    	    			}
    	    			else  if(mat[row][col]==1)
    	    			{
    	    				//For Debugging
    	    				//System.out.println("same");	
    	    				break;
    	    			}
    	    		}
    	    	    if(count<arr[i]) {
    	    	    	//For Debugging
    	    	    	//System.out.println("COUNT:"+count);
    	    	    	loop=0;
    	    	    	
    	    	    }
    	    		if(count==arr[i]) {
    	    			loop++;
    	    			if(loop==arr[i]) {
    	    				//For Debugging
    	    				//System.out.printf("\n Array: %d , column: %d, loop: %d, count: %d \n",arr[i],col,loop,count);
    	    				arr[i]=-1;
    	    				
    	    				break;
    	    			
    	    			}
    	    		}
    	    		
    	    	
    	    	}
    	    }
    	    
    	    
    	    for(int i=(arr.length)-1;i>=0;i--) {
    	    	if(arr[i]==-1) {
    	    		return (i+1);
    	    	}
    	    }
    	    return 0;
    }
    
    //for debugging printing of the matrix 
    public void print(int size,int[][] mat) {
    	System.out.println();
    	for(int i =0;i<size;i++	) {
    		for ( int j=0;j<size;j++) {
    			System.out.print("  "+mat[i][j]+"  ");
    		}
    		System.out.println();
    	}
    }
  
}


//Main class
public class Cube_Fill {
 public static void main(String[] args) {
	 Scanner input = new Scanner(System.in);
	 int wall_size = input.nextInt();
	 input.nextLine();
	 String[] bricks = new String[wall_size];
	 int[][] bmatrix = new int[wall_size][wall_size];
	 int[][] bmatrix1 = new int[wall_size][wall_size];

	 
	 //For converting the input to matrix form C=1 and D=0
	 for(int i=0;i<bricks.length;i++) {
		 bricks[i] = input.nextLine();
		for(int j=0;j<bricks.length;j++) {
			if(bricks[i].charAt(j)=='C')
						bmatrix[i][j] = 1;
			else
				bmatrix[i][j]=0;
		}
	 }
	 
	 Cube cubObj = new Cube();
	 
	 int[][] k = new int[2][2];
	 k[0][1]=1;
	 int[][] j = new int[2][2];
	 
	 for(int i=0;i<k.length;i++) {
	 System.arraycopy(k[i]	, 0, j[i], 0, k[0].length);
	 }
	 j[0][1] = 0;
	 System.out.println(k[0][1]);
	 
	
	//Copying bmatrix for rotation and storing it in another bmatrix1
	for(int i=0;i<bmatrix.length;i++) {
	 System.arraycopy(bmatrix[i], 0, bmatrix1[i], 0, bmatrix[0].length);
	}
     cubObj.rotateMatrix(wall_size, bmatrix1);  //rotation happens
	 	 
     //cubObj.print(wall_size, bmatrix);  -- Print the matrix form of the input
			
	 //Melting 
	 cubObj.melting(wall_size, bmatrix);
	 cubObj.melting(wall_size,bmatrix1);
	 
	 //cubObj.print(wall_size, bmatrix);  -- Print the melted matrix
		
	 int notRotated =  cubObj.wall_size(wall_size, bmatrix); //Identifies the wall_size
	 int rotated = cubObj.wall_size(wall_size, bmatrix1);    //Identifies the wall_size of the rotated matrix
	 
	 //To check the wall_sizes and print the bigger one.
	 if(notRotated>=rotated) {
		 System.out.println(notRotated);
	 }
	 else {
		 System.out.println(rotated);
	 }
   }

}

It works but it’s not compact as your code. It’ll be helpful if you explain the logic behind your code and how long you took to solve. Thank you.

My code may be compact but it doesn’t work :sweat_smile:

#include <bits/stdc++.h> 
# define ll long long int
using namespace std; 

int main()
{
ll r,d1,d2,d3;

cin>>r>>d1>>d2>>d3;

ll fs=d1;
ll st=d2-d1;
ll tf=d3-d2;

ll ang1,ang2,ang3,ang4;

cin>>ang1>>ang2>>ang3>>ang4;

ll s1,s2,s3,s4;

cin>>s1>>s2>>s3>>s4;

ll d11,d22,d33,d44;

cin>>d11>>d22>>d33>>d44;

ll tt;
cin>>tt;

map<int,int>c;

c[0]=0;
c[90]=1;
c[180]=2;
c[270]=3;

ll deg=s1*tt;
ll c1,c2,c3,c4;

ll l1,l2,l3,l4;

if(d11==0)
{
c1=abs(360+ang1-deg)%360;
l1=c[c1];
}

else
{
c1=abs(ang1+deg)%360;
l1=c[c1];
}

deg=s2*tt;
if(d22==0)
{
c2=abs(360+ang2-deg)%360;
l2=c[c2];  
}

else
{
c2=abs(ang2+deg)%360;
l2=c[c2];  
}



deg=s3*tt;
if(d33==0)
{
c3=abs(360+ang3-deg)%360;
l3=c[c3];  
}

else
{
c3=abs(360+ang3+deg)%360;
l3=c[c3];  
}


deg=s4*tt;
if(d44==0)
{
c4=abs(360+ang4-deg)%360;
l4=c[c4];  
}

else
{
c4=abs(ang4+deg)%360;
l4=c[c4];  
}





float ans=0;
if(l1==0 and l2==0)
{
    ans+=fs;
}

if(l1==0 and l2==1)
{
    ans+=sqrt(pow((fs-r),2)+r*r);
}

if(l1==0 and l2==2)
{
    ans+=(fs-2*r);
}

if(l1==0 and l2==3)
{
    ans+=sqrt(pow((fs-r),2)+ r*r);
}




if(l1==1 and l2==0)
{
    ans+=sqrt(pow(fs+r,2)+r*r);
}

if(l1==1 and l2==1)
{
    ans+=fs;
}

if(l1==1 and l2==2)
{
    ans+=sqrt(pow((fs-r),2)+r*r);
}

if(l1==1 and l2==3)
{
    ans+=sqrt(pow((fs),2)+ 4*r*r);
}



if(l1==2 and l2==0)
{
    ans+=(fs+2*r);
}

if(l1==2 and l2==1)
{
    ans+=sqrt((fs+r)*(fs+r)+r*r);
}

if(l1==2 and l2==2)
{
    ans+=(fs+r);
}

if(l1==2 and l2==3)
{
    ans+=sqrt((fs+r)*(fs+r)+r*r);
}


if(l1==3 and l2==0)
{
    ans+=sqrt((fs+r)*(fs+r)+r*r);
}

if(l1==3 and l2==1)
{
    ans+=ans+=sqrt(pow((fs),2)+ 4*r*r);;
}

if(l1==3 and l2==2)
{
    ans+=sqrt(pow((fs-r),2)+r*r);
}

if(l1==3 and l2==3)
{
    ans+=fs;
}


////////////// 

if(l2==0 and l3==0)
{
    ans+=st;
}

if(l2==0 and l3==1)
{
    ans+=sqrt(pow((st-r),2)+r*r);
}

if(l2==0 and l3==2)
{
    ans+=(st-2*r);
}

if(l2==0 and l3==3)
{
    ans+=sqrt(pow((st-r),2)+ r*r);
}


fs=st;
if(l2==1 and l3==0)
{
    ans+=sqrt(pow(fs+r,2)+r*r);
}

if(l2==1 and l3==1)
{
    ans+=fs;
}

if(l2==1 and l3==2)
{
    ans+=sqrt(pow((fs-r),2)+r*r);
}

if(l2==1 and l3==3)
{
    ans+=sqrt(pow((fs),2)+ 4*r*r);
}



if(l2==2 and l3==0)
{
    ans+=(fs+2*r);
}

if(l2==2 and l3==1)
{
    ans+=sqrt((fs+r)*(fs+r)+r*r);
}

if(l2==2 and l3==2)
{
    ans+=(fs+r);
}

if(l2==2 and l3==3)
{
    ans+=sqrt((fs+r)*(fs+r)+r*r);
}


if(l2==3 and l3==0)
{
    ans+=sqrt((fs+r)*(fs+r)+r*r);
}

if(l2==3 and l3==1)
{
    ans+=ans+=sqrt(pow((fs),2)+ 4*r*r);;
}

if(l2==3 and l3==2)
{
    ans+=sqrt(pow((fs-r),2)+r*r);
}

if(l2==3 and l3==3)
{
    ans+=fs;
}

///////////////

fs=tf;
if(l3==0 and l4==0)
{
    ans+=fs;
}

if(l3==0 and l4==1)
{
    ans+=sqrt(pow((fs-r),2)+r*r);
}

if(l3==0 and l4==2)
{
    ans+=(fs-2*r);
}

if(l3==0 and l4==3)
{
    ans+=sqrt(pow((fs-r),2)+ r*r);
}




if(l3==1 and l4==0)
{
    ans+=sqrt(pow(fs+r,2)+r*r);
}

if(l3==1 and l4==1)
{
    ans+=fs;
}

if(l3==1 and l4==2)
{
    ans+=sqrt(pow((fs-r),2)+r*r);
}

if(l3==1 and l4==3)
{
    ans+=sqrt(pow((fs),2)+ 4*r*r);
}



if(l3==2 and l4==0)
{
    ans+=(fs+2*r);
}

if(l3==2 and l4==1)
{
    ans+=sqrt((fs+r)*(fs+r)+r*r);
}

if(l3==2 and l4==2)
{
    ans+=(fs+r);
}

if(l3==2 and l4==3)
{
    ans+=sqrt((fs+r)*(fs+r)+r*r);
}


if(l3==3 and l4==0)
{
    ans+=sqrt((fs+r)*(fs+r)+r*r);
}

if(l3==3 and l4==1) 
{
    ans+=ans+=sqrt(pow((fs),2)+ 4*r*r);;
}

if(l3==3 and l4==2)
{
    ans+=sqrt(pow((fs-r),2)+r*r);
}

if(l3==3 and l4==3)
{
    ans+=fs;
}

cout<<ceil(ans)<<endl;
    


}

Solution for jogging round , when I was submitting answer time was over, but it gives correct answer for public test case.

Bro I too made a similar solution in python, both the public test cases were passed but private test cases showee wrong answer. I’m too surprised to see where could I have been wrong.

Yup I’m extremely suspicious too. I wrote a python version of my code and wrote a small script to test against the code which my friend wrote which passed. The script basically generates random inputs and compares both the results. It ran for 1,00,000 iterations and I still haven’t found the breaking condition.

from random import random, randint

def me(n, l):
    l = [[1 if i == 'C' else 0 for i in j] for j in l]

    u, s = [0]*n, [0]*n
    for i in range(n):
        for j in range(n):
            u[j] += l[i][j]
            s[i] += l[i][j]

    u = [n - x for x in u]
    s = [n - x for x in s]

    def maxgap(rem):
        res = 0;
        n = len(rem)
        for i in range(n):
            for j in range(i, n):
                curr = float('inf');
                for x in range(i, j+1):
                    curr = min(curr, rem[x]);
                curr = min(j - i + 1, curr);
                res = max(res, curr);
        return res;

    return max(maxgap(u), maxgap(s))

def working_code(n, l):
    P=[]
    c=0
    for i in range(n):
        t=[]
        c=0
        for j in range(n):
            if l[j][i]=='C':
                t.append('C')
                c+=1
        t.extend(['-']*(n-c))
        P.append(t)

    Q=[[0 for i in range(n+1)] for j in range(n+1)]
    m1=0
    for i in range(1,n+1):
        for j in range(1,n+1):
            if (P[i-1][j-1]=='-'):
                Q[i][j] = 1+min(Q[i][j-1], Q[i-1][j],Q[i-1][j-1])
                if(Q[i][j]>m1):
                    m1=Q[i][j]
            else:
                Q[i][j] = 0

    P=[]
    c=0
    for i in range(n):
        t=[]
        c=0
        for j in range(n):
            if l[i][j]=='C':
                t.append('C')
                c+=1
        t.extend(['-']*(n-c))
        P.append(t)

    Q=[[0 for i in range(n+1)] for j in range(n+1)]
    m2=0
    for i in range(1,n+1):
        for j in range(1,n+1):
            if (P[i-1][j-1]=='-'):
                Q[i][j] = min(Q[i][j-1], Q[i-1][j],
                            Q[i-1][j-1]) + 1
                if (Q[i][j] > m2):
                    m2 = Q[i][j]
            else:
                Q[i][j] = 0

    return max(m1,m2)


def test():
    i = 0
    while True:
        i += 1
        print(i)
        n = randint(1, 99)
        l = [['C' if round(random()) == 1 else 'D' 
            for i in range(n)]
            for j in range(n)]
        if working_code(n, l) != me(n, l):
            print(n)
            print(*[''.join(x) for x in l], sep="\n")
            break

test()

Indeed that’s suspicious. I was very sure of my solution. But was very much shocked to see WA. My solution ran successfully in the first try btw😂

And also bro…how did you take the full screenshot of the question?

“One Click Full Page Screenshot” it is a chrome extension

Tx bro :slightly_smiling_face: