Amit9's blog

By Amit9, 3 months ago, In English

0/1 Knapsack — Type 1 : (https://atcoder.jp/contests/dp/tasks/dp_d)
Solution :

Spoiler

0/1 Knapsack — Type 2 : (https://atcoder.jp/contests/dp/tasks/dp_e)
Solution:

Spoiler

0/1 Knapsack — Type 3 : (https://codeforces.me/gym/101064/problem/L)

How to solve the 3rd one where constraints on both Max capacity(W) of knapsack and (val[i]) is large enough that traditional methods won't work ?
I don't think DP will work here, so what is the other approach we can use?

Full text and comments »

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

By Amit9, 4 months ago, In English

Submission : (https://codeforces.me/contest/1692/submission/275124032)
Problem : (https://codeforces.me/contest/1692/problem/E)

Why this approach fails, can anyone give some counter test case?

Full text and comments »

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

By Amit9, history, 4 months ago, In English

This is the question from a recent online assessment by a company. Need your help in solving it, thank you for your time!

Problem Statement

Alice and Bob are playing a game in a town with houses arranged in a straight line. Houses are numbered from 1 to N.

Alice is standing at house x, and Bob is standing at house y . Each minute, Alice and Bob can decide individually to either move to the next house on the left (if they are not already at the first house), move to the next house on the right (if they are not already at the last house), or stay at their current house.

The goal of the game is for Alice and Bob to ensure that every house in the town is visited by at least one of them. Your task is to determine the minimum number of minutes required for Alice and Bob to achieve this goal in several games.

Input format

  • The first line of input contains one integer t, the number of games.

  • The next t lines describe each game and contain three integers n, x and y, the number of houses in the town, Alice's starting position, and Bob's starting position, respectively.

  • The combined length of all arrays (10^6 (∑n ≤ 10^6)) does not exceed 10^6.

Constraints

  • 1 <= t <= 2.10^4

  • 2 ≤ n ≤ 10^6; 1 ≤ x, y ≤n; x≠y

Output format:

  • For each game, print one integer the minimum number of minutes required for Alice and Bob to visit every house in the town.

Example 1

1
993

Output
4

Explanation
Total number of houses are 9
Alice is at 9th house and Bob is at 3rd house
1st min -> Alice moves to left 8th position, Bob moves to right 4th position
2nd min -> Alice moves to left 7th position, Bob moves to 3rd position
3rd min -> Alice moves to 6th position, Bob to 2nd
4th min -> Alice moves to 5th position, Bob to 1st

My code(Not sure if it is correct, but it passed most of test case i took)

Edit: The above solution is wrong.

Edit 2:
Correct solution (as of now) by mrxaid

Spoiler

Also thanks to xQConqueror and Sahu_1402 for their explaination.

Full text and comments »

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