Блог пользователя skpro19

Автор skpro19, 7 лет назад, По-английски

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?

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор skpro19, история, 7 лет назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор skpro19, история, 7 лет назад, По-английски

Let's discuss the hackerearth december circuits here.

The link to the competition is this.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

Автор skpro19, история, 7 лет назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

Автор skpro19, 7 лет назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

Автор skpro19, история, 7 лет назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор skpro19, история, 7 лет назад, По-английски

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

Codechef October Lunchtime

Problem 3

Problem 4

Полный текст и комментарии »

  • Проголосовать: нравится
  • -20
  • Проголосовать: не нравится

Автор skpro19, история, 7 лет назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

Автор skpro19, история, 7 лет назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор skpro19, история, 7 лет назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • -10
  • Проголосовать: не нравится

Автор skpro19, история, 7 лет назад, По-английски

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.

Полный текст и комментарии »

Теги dfs
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор skpro19, история, 7 лет назад, По-английски

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 ?

Полный текст и комментарии »

  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

Автор skpro19, история, 7 лет назад, По-английски

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

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

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

Автор skpro19, история, 7 лет назад, По-английски

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор skpro19, история, 7 лет назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • -14
  • Проголосовать: не нравится

Автор skpro19, история, 7 лет назад, По-английски

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!

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор skpro19, история, 7 лет назад, По-английски

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 :-(

Полный текст и комментарии »

  • Проголосовать: нравится
  • +21
  • Проголосовать: не нравится

Автор skpro19, история, 7 лет назад, По-английски

The question is this-> 757C

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • -20
  • Проголосовать: не нравится

Автор skpro19, история, 7 лет назад, По-английски

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?

Полный текст и комментарии »

  • Проголосовать: нравится
  • -7
  • Проголосовать: не нравится

Автор skpro19, история, 7 лет назад, По-английски

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 ?

Полный текст и комментарии »

  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

Автор skpro19, история, 7 лет назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор skpro19, история, 7 лет назад, По-английски

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?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

Автор skpro19, история, 8 лет назад, По-английски

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?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

Автор skpro19, история, 8 лет назад, По-английски

I am getting a WA on testCase 6.

Question — Div 2C

My Submission

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • -6
  • Проголосовать: не нравится

Автор skpro19, история, 8 лет назад, По-английски

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • -12
  • Проголосовать: не нравится