skpro19's blog

By skpro19, 3 years ago, In English,

I have understood the sqrt decomposition + SOS DP approach to the problem. This is an accepted solution to the problem. However, on changing the size of the array Q_MAX to 'N_MAX + 100', I am getting WA. Why is that?

What am I missing?

Read more »

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

By skpro19, history, 3 years ago, In English,

I observed a weird thing today in the Visual Studio IDE while solving the second question of Hourrank 25. This the the code.

On my local machine, the value of pre[0][0], automatically becomes 1 randomly anywhere inside the while loop. However, the weird thing is, if I initialise the value of fact[0] to 0, then everything becomes normal again. This is weird because the computation of fact has nothing to do with the value of pre[0][0].

I feel silly asking this, but what am I missing? The code which is giving wrong answer on the local machine , gives the correct answer on Ideone, and also fetches full marks after submission.

Can someone please help.

Thanks. Peace.

Read more »

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

By skpro19, history, 3 years ago, In English,

Let's discuss the hackerearth december circuits here.

The link to the competition is this.

Read more »

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

By skpro19, history, 3 years ago, In English,

This problem was the 6th problem in the last Educational Round. It requires the use of bitmask dp. I read through the editorial, but I can't understand, how the dp states are being defined. It would be really nice, if someone could help me with that.

Div 2F

Peace.

Read more »

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

By skpro19, 3 years ago, In English,

This was the fourth question in the November Lunchtime. I am not able to understand it, even after reading the editorial. Can someone please explain it in a bit more detail?

Contest link Problem Link Official Editorial Link Unofficial Editorial Link

I can not udnerstand anything in the official editorial.

I can't understand the dp states in the unofficial editorial, and also how to use the treap data structure being discussed in the editorial.

Read more »

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

By skpro19, history, 3 years ago, In English,

Why am I getting WA in this code?

I am dividing 'x' by all the prime numbers. To find the prime numbers, I am using the sieve. I know, it can be done without using the sieve, but when I am using the sieve, I am getting WA. Can someone please help ?

Div 2E: Counting Arrays

My code

It would be really kind if someone could point out the bug.

Read more »

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

By skpro19, history, 3 years ago, In English,

Can someone give hints for the third and the fourth problems for the Codechef October Lunctime.

Codechef October Lunchtime

Problem 3

Problem 4

Read more »

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

By skpro19, history, 3 years ago, In English,

This is the problem link. This is my submission. It is getting TLE. I read another guy's recursive approach. It got full points. I don't understand, why this code is getting accepted, but mine is not.

Any help would be really appreciated.

Peace.

Read more »

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

By skpro19, history, 3 years ago, In English,

The problem is this.

After going through the tutorial, and through the discussions, and reading a lot of submitted solutions, I am not exactly able to grasp the concept behind this problem.

I am pretty sure, there's some underlying topic, which I am unaware of.

Can someone please suggest some underlying concepts to better understand this problem? It would be really kind.

Thanks.

Read more »

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

By skpro19, history, 3 years ago, In English,

This is the problem .

According to the accepted solution of other coders, the following test case gives a "Yes". But, shouldn't it give a "No" ?

6 1 2 1 1 1 1 1 1 6

Any help would be really appreciated.

Read more »

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

By skpro19, history, 3 years ago, In English,

The question is 459C.

I have understood the logic behind it. But, in order to generate the possible permutations, I am using DFS.

My submission

It gives a WA on test 7, saying that my code prints ":". But, I am not printing ":" anywhere in my code.

Any help would be really appreciated.

Read more »

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

By skpro19, history, 3 years ago, In English,

The problem is this.

The editorial says this:-

We need some observation: There exists an optimal solution such that: in any pile, the box on the higher position will have a smaller strength.

Let k be the minimal number of piles, then there exists an optimal solution such that: The height of all piles is n/k or n/k+1 (if n%k=0, then all of them have the height n/k).

We can prove them by exchange argument: from an optimal solution, swap the boxes in it to make above property holds, and we can ensure it will remain valid while swapping. Then for a given k, we can check whether there exist a solution: the i-th (indexed from 0) smallest strength needs to be at least i/k. So we can do binary search (or just enumerate, since n is only 100) on k.

Doubt:

Why does the ith index need to be atleast i /k ?

Read more »

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

By skpro19, history, 3 years ago, In English,

I am getting a WA on this problem. Can someone suggest, what is wrong with my logic?

Problem: http://codeforces.com/contest/85/problem/C

My submission: http://codeforces.com/contest/85/submission/30241748

Read more »

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

By skpro19, history, 3 years ago, In English,

I am getting a TLE on this problem using DFS. This is my submission. Can someone suggest some optimizations?

Read more »

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

By skpro19, history, 3 years ago, In English,

I am getting a WA on test 9 on this DIV 1A.

Is there a problem with my 'poss' function or the very dfs function itself?

This is my submission.

Read more »

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

By skpro19, history, 3 years ago, In English,

The question is this.

The solution is something like this:

dp[1] = 1, dp[2] =3 ;

for(int i =3; i <= n ; i++) dp[i] = dp[i — 1] + dp[ i- 2] + 2;

How did one come with the formulation dp[i] = dp[ i — 1 ] + dp[i — 2] + 2 ?

Any help would be really appreciated.

Peace!

Read more »

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

By skpro19, history, 3 years ago, In English,

Is anyone able to see the test cases on the submitted solutions?

Can someone from Codeforces comment on how long will we have to face this problem?

I thought this was a temporary glitch :-(

Read more »

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

By skpro19, history, 3 years ago, In English,

The question is this-> 757C

I am unable to understand anything in the editorial, as well as the given code. Can someone please help?

Read more »

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

By skpro19, history, 3 years ago, In English,

I am talking about this problem. My accepted solution is this.

If we assume that the length of the string is n, then my solution has a complexity of O(n * n) ;

Why is it not getting TLE instead?

Read more »

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

By skpro19, history, 3 years ago, In English,

I am solving this DIV 2C. This is my submission which got accepted.

My question is this:

Why isn't updating the parent of a node, an O(n) operation ?

Read more »

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

By skpro19, history, 3 years ago, In English,

I am solving the problem DIV 1A. My submission is getting a TLE error. I went through the successful submissions as well, but I don't see any other logic. Any help would be appreciated.

Read more »

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

By skpro19, history, 3 years ago, In English,

I have doing competitive programming for 2 years.I solved all the DIV 2B problems, and then, I have been solving the DIV 2C problems topicwise. Unfortunately, I have stuck between the 1300- 1500 level for the two years. I am feeling very discouraged. Can you guys please suggest me what am I doing wrong? How should I practice?

Read more »

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

By skpro19, history, 3 years ago, In English,

I am getting "Accepted" when I am using C++ lower_bound function -> Submission

I am getting wrong answer using the binary search -> Submission

Can somebody please help?

Read more »

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

By skpro19, history, 3 years ago, In English,

I am getting a WA on testCase 6.

Question — Div 2C

My Submission

Can someone please tell me what's wrong with the code?

Read more »

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

By skpro19, history, 3 years ago, In English,

In this problem Div 2C, how can the difference between the maximum visited and the minimum visted be more than 1 ?

Read more »

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