charan2628's blog

By charan2628, history, 17 months ago, In English

Hi, I remember in the site mentioning they created a archive in github, I forgot to save the URL can anyone please share the GitHub URL of problems archive.

Full text and comments »

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

By charan2628, history, 2 years ago, In English

A car is moving on a straight line of length N meters.

The car has a fixed fuel tank capacity of K liters and it spends 1 liter per meter. There are M fuel filling stations along the straight line where the ith station is located at position a[i] and sells 1 liter of fuel for b[i] dollars.

It is given that the car can only refill the tank fully when it stops at some station for refueling. This means that if the tank contains 3 liters and its capacity was 10 liters, the car can buy exactly7 liters of fuel (otherwise the car will not stop at the fuel station for refueling).

Given that the car starts at position 0 moving in one direction to the end of the line and it can buy fuel from any fuel station it stops at. Your task is to choose which stations to buy from in order to reach the end of the line with the minimum possible cost. If it’s impossible to reach the end of the line return -1.

Note: It is guaranteed that there is always a fuel station at position 0.

Input Format The first line contains an integer, N, denoting the length of the road.
The next line contains an integer, K, denoting the tank's capacity.
The next line contains an integer, M, denoting the number of elements in a (the number of stations).
Each line i of the M subsequent lines (where 0 ≤ i < M) contains an integer describing ai (stations' locations).
Each line i of the M subsequent lines (where 0 ≤ i < M) contains an integer describing bi (the cost of one liter in each station).

Constraints
1 <= N <= 10^5
1 <= K <= 10^5
1 <= M <= 10^3
1 <= a[i] <= N
1 <= b[i] <= 10^9

Sample Input Sample Output Explanation
10
5
4
0
4
5
8
1
2
3
4 16

10
5
3
0
1
4
1
3
2 -1

This is what I tried but giving wrong answer

static long[] dp;
	
	public static long car_recur(int N,int K,int M,int[] a,int[] b){
		dp = new long[M];
		Arrays.fill(dp, -1);
		
		long ans = Long.MAX_VALUE;
		for (int i = M - 1; i >= 0; i--) {
			if (a[i] != N && N - a[i] <= K) {
				long tmp = recur(i, K, a, b);
				if (tmp != -1) {
					ans = Math.min(ans, tmp);
				}
			}
		}
		return ans == Long.MAX_VALUE ? - 1 : ans;
	}
	
	private static long recur(int fuelStop, int K, int[] a, int[] b) {
		if (dp[fuelStop] != -1) return dp[fuelStop];
		if (fuelStop == 0) return (long)b[0] * K;
		long ans = Long.MAX_VALUE;
		for (int i = fuelStop - 1; i >= 0; i--) {
			if (a[fuelStop] - a[i] <= K) {
				long tmp = recur(i, K, a, b);
				if (tmp != -1) {
					ans = Math.min(ans, tmp + b[fuelStop] * (a[fuelStop] - a[i]));
				}
			}
		}
		return dp[fuelStop] = ans == Long.MAX_VALUE ? -1 : ans;
	}

Full text and comments »

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

By charan2628, history, 3 years ago, In English

This is the problem minimum-cost-to-connect-two-groups-of-points, please go through it. I'm stuck at this point:
1. At each level (here each level mean each point in group 1) if I'm iterating different subgroups of group2 to connect, how to efficiently calculate the cost for the new connections excluding the connections already connected in previous level?
2. Or is there another way to do it?

Full text and comments »

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

By charan2628, history, 5 years ago, In English

I saw this problem here challenge:

Painting buildings
There are N buildings in a locality. Each building must be painted with a type of paint. Initially, some buildings are painted with some type of paint. The building that is painted cannot be painted again. You are given M types of paints, 1 to M inclusive. The specialty of the locality is defined as the number of contiguous buildings that are painted with the same type of paint. For example, if six buildings apartment are painted from left to right are {1, 2, 1, 1, 3, 3}, then the likelihood of the apartment is 4 [{1}, {2}, {1, 1}, and {3, 3}]. You are given N x M matrix, where the ith row and jth column denote the painting cost of the ith building with the jth the type of paint.

You are required to determine the minimum cost to paint all the buildings such that the specialty of the apartment is exactly K. If it is not impossible to paint all buildings such that the likelihood of the apartment is exactly K, the print -1.

Input Format
1. The first line contains T denoting the number of test cases.
2. For each test case:
a. The next line contains N, M, and K where N is the number of buildings in locality, M is the number of type of paints, and K is the specialty of the locality respectively.
b.The next line contains N space-separated integers where the ith integer is either 0 or the type of paint from which the ith building is already painted. Here, 0 means that the building is not painted.
c. The next N lines contain M space-separated integers where the ith row and jth the column denote the painting cost (cost[i,j]) of the ith building with the jth type of paint.

Output Format Print the minimum cost to paint all buildings such that the specialty of the apartment is exactly K. If it is not possible to paint all building such that the likelihood of the apartment is exactly K, then print -1.

Constraints
1 <= T <= 10
1 <= K <= N <= 100
1 <= M <= 100
1 <= cost[i, j] <= 10^9

Sample Input:
1
4 2 1
0 0 0 2
100 20
30 59
71 81
9 200
Sample Output:
160

I couldn't able to figure out how to solve this problem. Is it a graph problem, disjoint sets, ..? Can anyone give me a idea on how to solve this problem.

Full text and comments »

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

By charan2628, history, 5 years ago, In English

This is my submission for 636 (Div 3) for Problem C, I made this submission during contest it's still in queue. Does it takes time?

Full text and comments »

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

By charan2628, history, 5 years ago, In English

I'm solving this problem By Elevator or Stairs, here is my solution Submission it's failed on test 11, My solution is similar to this editorial solution.

I know I did somewhere wrong but can't able to find it, please take a look at my solution.

Thank you.

Full text and comments »

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