art-hack's blog

By art-hack, history, 5 weeks 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

Read more »

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

By art-hack, history, 5 months 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.

Read more »

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

By art-hack, history, 6 months 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?

Read more »

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

By art-hack, history, 11 months 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.

Read more »

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