yashsaha555's blog

By yashsaha555, history, 10 months ago, In English

Jack has invited her friend Tina to play a game of numbers.The game is as follows:

There are a total of 'N' numbers (1,2,3....N) with Jack. He has to share 'X' of them with Tina. After sharing 'X' numbers, Jack has a set of '(N-X)' numbers and Tina has a set of 'X' numbers. Consider Jack's set as J and that of Tina 'T'. Now, the distribution should happen in such a way that each number from set 'J' should have a GCD of '1' from set of numbers in 'T'. Formally, GCD(x,y) = 1, where 'x' are the elements of set 'J', and 'y' are the elements of set 'T'.

Input: Value of N and X

Output: If the above condition is possible, print "Yes". Followed by (separated by SPACE), the number of components of 'T' (X number of components from set). If condition is not satisfied then print "No".

Example 1:

Input:

N = 4, X = 1

Output: Yes 3

Let us try to understand it with and example. Consider a set of N = 4 and X = 1. It means that the entire set Contains S= [1,2,3,4], and 'J' contains number from this set. He also needs to make sure that each number from his, set and Tina's set have a GCD of '1'.

By looking into the elements of the Jack's set, we can clearly see that element '2' and '4' should be in same set otherwise they will make a GCD of 2, which will ultimately not satisfy the above condition.

If we take the element '3' from the Jack's set, and give to Tina, then we can have all the conditions satisfy because the remaining element of Jack's set (1, 2, 4) will have a common GCD of 1 with the element of Tina's set which is 3.

Hence the output is : Yes 3

Example 2:

Input:

N = 6, X = 3

Output:

No

Explanation:

In this scenario, we have to give 3 elements to Tina. Initially Jack's set contains [1, 2, 3, 4, 5, 6]. The best case which we can think of is to share the prime numbers to Tina and leave the rest with Jack, or vice- versa.

In that case, Jacks's set = [2, 4, 6] Tina's set = [1, 3, 5]

But, if you see closely the element '6' and '3' will have a GCD of 3, hence the conditions will fall.

And the result will come out to be No.

Hence the output is: No

Example 3:

Input:

N = 4, X = 3

Output: Yes 1 2 4

Someone kindly solve this with explanation. Thanks.

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it

By yashsaha555, history, 14 months ago, In English

A teacher takes an array of numbers and asks the students to perform the following operation: pick two adjacent positive numbers, ai and ai+1, and replace the two numbers with either (ai%(ai+1)) or (ai+1)%ai ,where x%y denotes x modulo y. Thus, after each operation, the array's length decreases by 1.

The task is to find the minimum possible length of the array, which can be achieved by performing the above operation any number of times

Example

Consider the array's length to be n=4 and the array of numbers to be arr=[1,1,2,3]. The following sequence of operations can be performed (considering 1-based indexing):

  1. arr=[1, 1, 2, 3]: Choose i=3, thus arr[i]= 2 and arr[i+1]=3. We get the new value to be given by 2%3

=2 or 3 % 2=1. The resulting array can thus be [1, 1, 2] or [1, 1. 1]. We consider the former one to minimize the array length.

  1. arr=[1,1,2]: Choose i= 2, thus arr[i]=1 and arr[i+1]=2. We can get the new array as [1, 1].

3 arr=[1, 1]: Choose i=1 to get the array [0].

Thus the minimum possible length for the above array would be 1.

Could someone please help me in solving this?

Full text and comments »

  • Vote: I like it
  • +5
  • Vote: I do not like it

By yashsaha555, history, 15 months ago, In English

Given a board with an integer 'n' written on it, select an integer 'x' from the board. For each, 'i' from 1 to 'x', if the remainder when 'x' is divided by 'i' is 1, add the integer (x-i) to the board. Find out the maximum number of distinct integers that can be present on the board.

Example- n = 4

Initially, only the given number 4 is on the board. There is one value that leaves a remainder of 1: 4%3=1. Add the value 4-3=1 to the board, so it now contains [1,4]. There is no longer 'i' such that 1%i=1. There are 2 distinct integers on the board, so return 2.

Constraints- 1<=n<=1000

If someone could explain the approach then it would be very helpful. Thanks.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By yashsaha555, 22 months ago, In English

Link to the problem: https://cses.fi/problemset/task/1192/

I am getting time limit exceeded for Test cases #10 and #17 for this question. I am stuck with this for a long time and unable to figure it out as to why this is occuring. Need some help. My code is given below. Thanks in advance.

import java.util.*;
public class Crooms
{
    static int direction[][]={{1,0},{0,1},{-1,0},{0,-1}};
    static char ch[][]=new char[1001][1001];
	static int vis[][]=new int[1001][1001];
	static int n=0,m=0;
	public static void main(String[] args) {
	    Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
	    int count=0;
	    for(int i=0;i<n;i++)
	    {
	        ch[i]=sc.next().toCharArray();
	    }
	    for(int i=0;i<n;i++)
	    {
	        for(int j=0;j<m;j++)
	        {
	            if(ch[i][j]=='.' && vis[i][j]!=-1)
	            {
	                vis[i][j]=-1;
	                dfs(i,j);
	                count++;
	            }
	        }
	    }
	    
		System.out.println(count);
	}
	public static boolean boundary_check(int x, int y)
	{
	    return x>=0 && y>=0 && x<n && y<m && ch[x][y]=='.' && vis[x][y]!=-1;
	}
		public static void dfs(int x, int y)
	{
	        for(int i=0;i<4;i++)
	        {
	            int nx=x+direction[i][0];
	            int ny=y+direction[i][1];
	            if(boundary_check(nx,ny))
	            {
	            vis[nx][ny]=-1;
    	        dfs(nx,ny);
	            }
	        }
	}
}

Full text and comments »

  • Vote: I like it
  • -1
  • Vote: I do not like it