padfoot1717's blog

By padfoot1717, history, 3 years ago, In English

A few times while solving a problem where we need to compute ceil values, i have encoured WA when i use ceil(var1/double(var2)) type of expression, for example in this problem a submission of mine was failing on just 2 TCs because of using that expression, and soon as i used a different approach for calculating ceil, i got AC. I wanted to know, what is the fundamental issue behind this inaccuracy?

Full text and comments »

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

By padfoot1717, history, 3 years ago, In English

I am trying to solve this problem, but don't know why i am getting WA judgement and unfortunately the test cases on which my code is failing are big, therefore i am not able to find the logical error in my solution.

In my approach I firstly find the maximum element(it's first occurence) in the array. Let's call the maximum element mx and it's index in the array as ind. Now as per me this should be the maximum number of marks on the wall during the entire process. Now firstly I move towards the left of ind. If I find any number(m[i]) which is smaller than the current max(mx) then I update mx by mx-1 and add (mx-m[i]) to the answer. After this I start moving towards right of ind. Here we will simply add mx-m[i] to the final answer(here mx is the original maximum element in the array). Below i am pasting my code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()                                         //i guess the code is clean enough for anyone to understand.
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin>>n;
	vector<int>m(n);
	for(int i=0; i<n; i++){
		cin>>m[i];
	}
	int mx=*max_element(m.begin(),m.end());
	int ind=max_element(m.begin(),m.end())-m.begin();
	ll sum=0;
	int curr=mx;
	for(int i=ind-1; i>=0; i--){
		if(m[i]<curr){
			curr--;
			sum+=(curr-m[i]);
		}
	}
	for(int i=ind+1; i<n; i++){
		sum+=(mx-m[i]);
	}
	cout<<sum;
	return 0;
}

Kindly help me to find out the error in my solution.

Full text and comments »

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

By padfoot1717, 4 years ago, In English

I was practising some atcoder problems and i really got fed up. In almost every third problem i had to ensure that no overflow is occuring while dealing with huge numbers. This really screws up your interest in the problem and significantly makes it more laborious without any reason. This makes using C++(which is quite a cp friendly language) in atcoder problems more difficult.

Full text and comments »

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

By padfoot1717, history, 4 years ago, In English

I am stucked at the problem Shortest subsequence. Can someone kindly explain an optimal algorithm to solve this problem?

Full text and comments »

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

By padfoot1717, history, 4 years ago, In English

Can someone kindly take the pain of checking my submission on which i am getting RE verdict and help me to sort the error?

Full text and comments »

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

By padfoot1717, history, 4 years ago, In English

Friends during the previous contest (656 div-3) for problem-1385D - a-Good String i had submitted this solution 87151676 and it gave TLE, after looking at the model solution in the editorial i changed my normal "string" argument to "const string&" argument in the function that i had written and submitted this solution 87188378 which got easily accepted. Can anyone please explain the reason because of which such huge difference in execution time came just by changing the "string" argument to "const string&" argument"?

Full text and comments »

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

By padfoot1717, history, 4 years ago, In English

Kindly try this problem and provide a detailed algorithm for solving it, i will be extremely thankfull. Link to the problem Edit-Seems to be extremely strange, that people rather than helping are delibrately downvoting just for the sake of fun.

Full text and comments »

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

By padfoot1717, history, 4 years ago, In English

Suppose we have a string and we want to find the longest palindromic subtring which is also a prefix of the original string. Is there any way to solve this problem faster than the bruteforce technique?

Full text and comments »

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