AjaySabarish's blog

By AjaySabarish, history, 2 years ago, In English

You are given an integer array Inventories representing the ribbon inventories, where Inventories[i] represents the length of the ith ribbon, and an array of orders.

Each order in orders is an array of integers, representing the ribbons needed with certain lengths for that order. For example, if order = [1,2], then that means this order need a ribbon with length 1 and a ribbon with length 2.

You may cut any of the ribbons in the inventory into any number of segments of positive integer lengths, or perform no cuts at all.

However, you cannot combine two ribbons in the inventory to form a longer ribbon and fullfil an order. Each segment/ribbon in the inventory cannot be reused. The question is, what is the maximum number of orders that can be fulfilled?

Example 1:

Input: Inventories = [1,8,7], orders = [[1, 2], [4, 3, 6]]

Output: 2

Explanation:

First cut inventories[1] into [2,6], then the inventory becomes [1, 7, 2, 6]. Use inventories[0] and inventories[2] for the first order. The rest of the inventories are [7,6], then cut the ribbon with the length of 7 into 4 and 3 to fulfill the second order. So in total 2 orders are fulfilled.

Example 2:

Input: Inventories = [1,2,3], orders = [[3, 3], [4]]

Output: 0

Explanation:

None of the orders can be fulfilled. Notice we cannot combine inventories[0] and inventories[1] for orders[0].

Example 3:

Input: Inventories = [3], orders = [[2]]

Output: 1

Explanation:

Cut the ribbon into 2 and 1, and use the first segment for that order.

I have been breaking my head over this, I thought of some greedy approaches, sorting orders by the max ribbon required by each item and processing it. Eg: [[4,3,6], [1,2]] becomes [[1,2],[4,3,6]]. But this fails when order max is less but the number of items in the order is huge.

Does anyone have any approach ?

Full text and comments »

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

By AjaySabarish, history, 3 years ago, In English

There are M objects of type 1 and N objects of Type 2. Given $$$Cost[i][j]$$$ where $$$i$$$ is an object of Type 1, and $$$j$$$ is an object of Type 2. What is the minimum total cost achievable after every type 1 object is mapped with exactly one type 2 object?

Total cost is defined as the summation of the individual costs incurred due to matching.

$$$M <= N$$$.

Example :

Type 1 : $$$A B$$$

Type 2 : $$$C D$$$

$$$cost[A][C] = 100$$$

$$$cost[A][D] = 10$$$

$$$cost[B][C] = 10$$$

$$$cost[B][D] = 100.$$$

It's optimal to match $$$(A, D)$$$ and $$$(B, C)$$$, the total cost incurred is 20.

I thought of a bit masking + DP approach, but the complexity is exponential, is there a better approach?

Full text and comments »

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

By AjaySabarish, history, 3 years ago, In English

You are given an array of N integers (N is even), at each round you have to select 2 numbers $$$(A[i],A[j])$$$, and do $$$ Sum = Sum + GCD(A[i], A[j]) * round $$$, post calculating sum remove those 2 numbers from Array. What is the maximum possible sum you can obtain?

Round's value starts from 1.

Constraints

$$$ 2 \leq N \leq 20 $$$

$$$ 1 \leq A[i] \leq 1e9 $$$

I tried Bitmasking Dp ( $$$ O(2 ^N * N ^2) $$$ ) but got TLE.

Example :

2 3 5 9

1st Round — 2 5, Sum = GCD(2,5) * 1

2nd Round — 3 9, Sum = GCD(3,9) * 2

The maximum possible sum is 7

Any insights?

Full text and comments »

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

By AjaySabarish, history, 3 years ago, In English

After figuring out the logic for the problem, while coding, have you guys experienced your thoughts wandering to some movies, songs, etc? It happens to me a lot, I make mistakes in the code, miss corner cases, etc. If yes, how do you stay focused?

Full text and comments »

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

By AjaySabarish, history, 3 years ago, In English

Let's say we have a Graph, with N nodes and M edges, each edge has a weight associated with it, now we have to find the minimum possible, maximum edge weight in a path.

Does Dijkstra work for this scenario?

Sample problem https://leetcode.com/problems/path-with-minimum-effort/

Dijkstra works for this, but I have no idea why, can anyone help me with proof or at least an intuitive idea?

Full text and comments »

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

By AjaySabarish, history, 3 years ago, In English

Chronology of events :

1) Solved problem 2, submitted, got "correct answer"

2) Solved problem 3, submitted, got "correct answer"

3) Coded problem 4, got some errors in testing, debugged it, clicked "test" button got Please wait, fetching code

4) Thought it is some server issue, moved to problem 1, coded it and clicked "test" button, got Please wait, fetching code

5) Moved to 5th problem, tried solving it, couldn't get a concrete idea

6) Tried submitting 1 and 4, got the same issue

7) Copy pasted the test link in a fresh window, continued with the contest and tried submitting again, this time got Error: Connection lost.

8) Tried minimizing the window and checking the internet connection, got warning "Go to fullscreen in 10s", checked internet connection worked fine.

9) Tried submitting multiple times but in vain.

I wasted a lot of time and was not able to submit 2 problems. Any help or guidance would be great ?

Did anyone else face this issue ?

Tagging people whom I think would be able to help Ashishgup

Full text and comments »

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

By AjaySabarish, history, 3 years ago, In English

In the wake of current contests, observation has become very crucial in every problem, thinking from the problem statement and trying to reach the solution is no longer easy, because the crucial observation is no longer easy to arrive from the problem statement alone, I think we have to start from random points and see if we can reach solution from there.

Let's take today's C (Edu round 99), the crucial observation here is Bob can't win more than y matches, and there is a way for him to always win y matches, this was not easy for me, I saw the high number of AC's lowered my thinking scope, saw the sample, observed the pattern then tried to justify it. If there had been no sample, and I had not seen the submissions, I probably would have taken more time.

And unpredictability factor has increased, sometimes you get the observation in a few seconds, and at times you never get it, this definitely has impacted the ratings.

Any suggestions or comments on this are welcome.

EDIT : Some have misinterpreted my post, I am not complaining nor am I urging the problem setters to change the format, my post is more about how to tackle these kinds of problems, before screaming practice, add me as your friend have a look at the number of problems I have solved in the standings. And regarding unpredictability, I think it makes sense, even experienced coders at times have a blind spot, and relatively young ones may get that observation immediately, that's why I said it's more about the thinking style.

Full text and comments »

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

By AjaySabarish, history, 3 years ago, In English

I would like to hide the problem tags in Mashups, is there any way to do that ?

I am talking about this

Screenshot-33

Full text and comments »

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

By AjaySabarish, history, 3 years ago, In English

I came across this site (https://kenkoooo.com/atcoder/#/table/ ) that quantifies the difficulty of atcoder problems,but I was wondering how it would relate to CF difficulty, Any inputs would be great

Full text and comments »

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

By AjaySabarish, history, 3 years ago, In English

How did so many people get D right ? more than 2000 ppl got AC, just curious, my Approach was F[i] be the answer if string starts from i,

if(str[i]==str[i+1]) 
F[i] = F[j] + 1

where j is the first index diff from i,

else 
F[i] = F[i+2] + 1 

, this approach though wrong, seemed extremely obvious, so those who sovled it in contest did you land on the right approach initially itself, or did you land on the above mentioned approach then realized it's wrong and then moved on ?

Full text and comments »

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

By AjaySabarish, history, 4 years ago, In English

MikeMirzayanov Problem 1183H - Подпоследовательности (усложненная версия) has difficulty rating of 1900, which is less than it's corresponding easier version 1183E - Подпоследовательности (легкая версия) of rating 2000, and the only difference between them is the constraints, can you please look into it?

Full text and comments »

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

By AjaySabarish, history, 4 years ago, In English

Given a binary array, convert all the elements to zero Array (array with only zeros) in minimum number of steps

In one step we can choose any 2 adjacent elements and flip them together, or you can choose the last or first element and flip that particular element alone.

Input : N ( 1 <= N <= 1e5) Array elements ( 0 <= a[i] <= 1)

Output : Minimum number of steps to convert the binary array to all zeros

Sample : [1,0,1] Anwer is 2 ( one possible way is choose the second and third elements, flip them and then choose the first and second elements and flip them)

Can anyone help me solve this?

Full text and comments »

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

By AjaySabarish, history, 4 years ago, In English

Problem Link

I understand the entire solution except the part " The probability of reaching any particular green square is the same for all but the green square in the last row", I don't get it why the last row is any different?

My understanding of the solution : We take all the squares which are the extension of the diagonal of the removed rectangle part. We have to pass through one of these squares in order to reach the destination and once we get to these squares the probability of reaching destination is 1. Since there cannot be interesction between these paths, we individually find the probability of reaching each of these squares and add them.

Can anyone please explain how the last row is any different?

My code : https://ideone.com/FIGKWD (got WA)

Full text and comments »

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

By AjaySabarish, history, 4 years ago, In English

Given an Array, find the maximum difference between the sum of elements in odd indices and even indices. To achieve this you can delete any number of elements from the array,after deleting the elements,the array will be re-numbered.

Example : 1 4 8 2 6

Upon deleting 1,4.

New array 8 2 6

Answer is 8+6-2 = 12.

Constraints : 1<=N<=1e5

Can anyone please help me solve this problem?

Full text and comments »

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

By AjaySabarish, history, 4 years ago, In English

I read the editorial,but the last part,the "second way" is not clear,can anyone please help me out? 962E - Byteland, Berland and Disputed Cities

Full text and comments »

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

By AjaySabarish, history, 4 years ago, In English

MikeMirzayanov Several of the old contests don't have solutions,and even some of the new ones like Codeforces Round 609 (Div. 2) don't have solutions.

Though the contestant is expected to implement the solution on his own after reading the editorial,but at times,when editorial isn't elaborate enough or if the contestant couldn't get the implementation part,a peek at the solution would be really helpful.

Though we can view other's submissions,but most of the code is not written for reading purpose,and the approach may be completely different from that given in editorial.

It maybe inessential for top coders,but for novices like me,it could be a boon.

Full text and comments »

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