spirited_away_'s blog

By spirited_away_, history, 9 days 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, 4 weeks 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, 5 weeks 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, 2 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, 2 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, 2 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