art-hack's blog

By art-hack, 4 years ago, In English

Hi Everyone, I encountered this subproblem in a problem.

Suppose we are given an array of integers of size N and want to generate subsets of size K from it. I used this simple backtracking approach to generate the combinations of size K.

Backtracking Code

I was wondering if there is a possible approach to do this by using bits, a simple approach is generating all subsets and processing only the ones that have size K, but in this, we have to generate all 2N subsets.

Bits Solution

Is there a way to do this using bits without generating all the possible subsets?.

Full text and comments »

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

By art-hack, history, 4 years ago, In English

Hey Everyone, I am trying to solve a problem and got stuck at this subproblem.

Problem

You are given an initial array a with N elements.

There are a series of update operations, Let's say there are K operation, such that in each operation ai is replaced with xi.

Now there are Q range sum queries, and in each query, you're given L, R, and P.

You have to find the sum of range in [L, R] after the pth update has occurred.

Constraints

  1. N<=2*105
  2. ai <= 109
  3. K <= 105
  4. Q <= 105
  5. L,R <= N

The solution should preferably be with preprocessing and not be with offline queries.

Example

Full text and comments »

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

By art-hack, history, 5 years ago, In English

Hello Everyone,

I have created a handy tool for running two codes against an input or stress testing them against random inputs. This can be helpful in hacking some simple problems and get possible faults, and also in finding wrong test cases for your solutions.

Link to Github Repo: Link

Video Showing its working Watch the video

I know this isn't perfect so if you feel that I can improve something or add some feature then do let me know and feel free to contribute as well.

Full text and comments »

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

By art-hack, history, 5 years ago, In English

Hey Everyone, So I saw this problem in one of the contests on Codechef(link)

Problem Statement

You are given two integers N and M. Find the number of sequences A1, A2,…,AN, where each element is an integer between 1 and M (inclusive) and no three consecutive elements are equal. Since this number could be very large, compute it modulo 109+7.

So I used my general code for Matrix Exponentiation but got a TLE.

My submission

People have used matrix exponentiation for the same and got a full score.

Selected submission

Things that I have tried already are

  • Switching ll with int
  • Reserving the size of the vector already.

Please tell me what I can optimize more in my code so that we do not face this problem in any of the Matrix Exponentiation problems?

Full text and comments »

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

By art-hack, history, 5 years ago, In English

I created a problem, but I couldn't solve it and need some help.

Problem You have N blocks with an array a in which a[i] represents the weight of ith item. You are also given the maximum weight that the knapsack can handle as W.

You have to find the maximum possible weight that you can achieve by filling these blocks in the knapsack.

Now the different part is that you can either take any block as whole or you can split it into two blocks(only once) such that atleast one of the two block has weight between [80,100%) and you can take either of the blocks into the knapsack.

Sample Input
2
200 100
285

Sample Output
285
Sample Input
2
200 100
230
Sample Output
220

Explaination: In the first sample input we take the first block as whole and the second partially with one piece of 85 and one of 15 and take the one with weight 85 to achieve the total of 285.

In the second sample input we take the first block as whole and the second partially with one piece of 80 and one of 20 and take the one with weight 20 to achieve the total of 220.

I wanted to know if it is solvable or not.

If possible can we extend this question with another given array v representing the values of the blocks and we want to achieve the maximum possible value by putting blocks in the knapsack. Note: when we split a block its value gets split in the same ratio as it's weight.

Full text and comments »

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