spirited_away_'s blog

By spirited_away_, history, 5 weeks ago, In English,

The problem Red-Green Towers CF 478 d , we are given r red balls and g green balls. we have to find in how many ways we can make a tower of height h with given conditions.

A simple recursive dp with memoization is, suppose we are at level i, we can either fill it will red or green and recur for next. our state will be height till now and number of red balls. But it will give Memory limit exceeded.

While solving the same problem with iterative dp, we see that i depends on only i-1(editorial) so we can easily maintain dp[2][N] state and fill the dp array accordingly. But how to solve this problem with recursion using memoization.

Do we need to pass cnt variable as a reference in recursive function, where cnt is the level right now. Can this be solved using recusion + memo? what will be the parameters?

Read more »

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

By spirited_away_, history, 3 months ago, In English,

Can anyone provide a detail approach on how to solve the problem 766E xor trip

editorial is not well clear. i understood that we can handle bits independently but how can we computs their n2 xor sums.

Please help!. Thanks.

Read more »

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

By spirited_away_, history, 3 months ago, In English,

Here is the problem. Can anyone give me more detail proof of why the answer to the problem is always summation of min(S[v], 2*k - S[v]).

The editorial is not clear.

Read more »

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

By spirited_away_, history, 4 months ago, In English,

Why is the answer to this problem always ( N + K — 3) / (K — 1).

Can anyone please help me. editorial is not clear.

Read more »

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

By spirited_away_, history, 5 months ago, In English,

Hello! I am solving Pictures with Kittens (easy version).

My approach is pretty much like knapsack. Suppose we are at index i, we have 2 options either to not pick or to pick. If our last pick and current index different == k then we will have to pick it.

my dp state is dp[curr][taken][last] which is what is our answer if we are at index = curr, and have took taken elements and our previous taken = last.

But this approach is giving WA on test case 45. Can anyone please tell me what i am missing? The code is simple. Have a look at it.

Here is my solution: LINK

Thanks.

UPDATE: The solution got accepted when i declared res = minn instead of res = 0 which was earlier, can anyone tell me why this error.

AC

Read more »

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

By spirited_away_, history, 5 months ago, In English,

Problem

The problem asks you to find all pairs of edges not included in shortest path.

Here is my two submissions :

correct one : in this, what i did is i fixed the edges and iterated on the nodes and check whether the particular edge can be included in the answer or not. It gives right answer.

Second one : WA : in this, i fixed the nodes and iterated on the edges that is present in our graph and check whether this particular edge can be included in the answer or not. It gave WA.

why second one is giving wa, though i think both have the same intution.

This is making the difference :

correct
wrong

Read more »

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

By spirited_away_, history, 6 months ago, In English,

Given a number N, The problem asks you to find all such pairs u,v such that there exists another set of pairs a,b such that

  1. a ^ b = u

  2. a + b = v

where u , v <= N.

I finally concluded that basically we have to find a+b<=N, but how to proceed from here. Can we use counting principle to solve this problem, i mean count all a+b == N and a+b < N and to avoid repeatation we will considere a >= b.

Can anyone tell me the approach and intutition to solve it. Editorial is in japanese.

Read more »

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

By spirited_away_, history, 6 months ago, In English,

I want to delete some element in a priority queue not at the top, how should i do? can someone suggest any method, in constant or logarithmic time. How to handle duplicates while removing

Read more »

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

By spirited_away_, history, 7 months ago, In English,

In problem small multiple , you are asked to the smallest possible sum of the digits in the decimal notation of a positive multiple of K.

what i did was i ran a loop from 1 to 70000000 and compute answer for each i. It gave WA in some test cases. 16/66 MY solL:

The editorial mentions Construct a graph with K vertices, start from 1 and answer will be minimum distance from 1 to 0 , +1.

Though i understood the editorial, But i couldn't get the proof behind it. why it will give right answer. Why we are creating only k vertices and considering each number as x % k.

Can anyone who solved it, explain the logic behind it. Or any other approach for solving this problem.

Read more »

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

By spirited_away_, history, 7 months ago, In English,

Here are two submission for problem d , of ABC 087. one is giving due to declaration of int xdp[][] and int ydp[][] while other is passing using bool xdp[][] and bool ydp[][] .

Any idea, why its happening so!

AC : https://atcoder.jp/contests/abc082/submissions/5496820

int RE : https://atcoder.jp/contests/abc082/submissions/5496847

code :

Spoiler

Read more »

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