arnav2004's blog

By arnav2004, history, 5 months ago, In English

I was solving this problem Problem Link

Here is my code

Now I don't want to know the logic of how to solve the problem or whether my logic is wrong or not.

It's just that when I am compiling this code is giving RE (Specifically : Runtime error: exit code is 2147483647)

Now when I comment out the line in which I unite two sets (Mentioned in the code), it does not give RE.

But I don't know how can my unite function be wrong(It's just merging two sets [DSU]).

Can anyone tell me the flaw?

EDIT : Found the error. Tbh it was a silly one. In my unite function when (p[x] != x) I call the function again with the same argument instead of p[x].

Read more »

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

By arnav2004, history, 5 months ago, In English

I was solving this problem on the CSES Problemset Longest Flight Route.

Here is my code

The code is getting Accepted in all but 2 testcases(TLE in those 2) .

I cannot debug with those testcases since they are HUGE.

I reckon that the problem is in my BFS Code but I can't seem to find why it would go in an infinity loop.

If anyone could provide a testcase or something it would be incredibly helpful.

Thanks.

Read more »

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

By arnav2004, history, 7 months ago, In English

I solving this problem Link to problem. I could not solve it hence checked other people's code. I saw this AC Code. AC Solution. I changed it just a little bit and it got runtime error. Runtime Error Code. As you can see the only difference is in the for loop in the 'dfs' function. Can anyone tell me the reason for the code to receive a runtime error.

Read more »

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

By arnav2004, history, 13 months ago, In English

I was solving this bugabooLink to the bugaboo.

Here's my code:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const ll INF = 1e18;
const int MOD = 1e9+7;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		int a,b,c;
		cin>>a>>b>>c;
		if(c==a){
			cout<<1<<"\n";
			continue;
		}
		if(c <= (a+b) / 2){
			cout<<2<<"\n";
			continue;
		}
		ll start = 1;
		ll high = (1LL<<40);
		ll mini = 0;
		double te = 0;
		while(start<=high){
			ll mid = (start+high)/2;
			ll sum = (1LL * mid * a) + (1LL*(mid-1)*b);
			double avg = (0.0000+sum) / (0.0000+mid+mid-1);
			if(avg>=c){
				mini = mid;
				start = mid+1;
			}
			else
				high = mid-1;
		}
		te = (a+b)/2;
		ll ans = 2;
		for(ll mid = mini;mid<=mini+100;mid++){
			ll sum = (1LL * mid * a) + (1LL*(mid-1)*b);
			double avg = (0.0000+sum) / (0.0000+mid+mid-1);
			if(abs(avg-c)<abs(te-c)){
				te = avg;
				ans = mid+mid-1;
			}
		}
		cout<<ans<<"\n";
	}
}

This code got AC in C++14 and WA in C++17(64). Is it this happening maybe because of some precision errors or is there any other reason?

Read more »

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

By arnav2004, history, 13 months ago, In English

I was solving problem C of Educational Round 109 which was held yesterday.The link to the question.

Here is my code:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int INF = 1e9;
const int MOD = 1e9+7;
struct point{
	int x,idx;
	char dir;
};
int n,m;
int ans[300005];
bool cmp(point a,point b){
	return a.x<b.x;
}
void helper(vector<point>&v){
	sort(v.begin(),v.end(),cmp);
	for(auto i:v)
		cout<<i.dir<<endl;
	deque<point>right,left;
	for(int i = 0;i<v.size();i++){
		if(v[i].dir=='R')
			right.push_back(v[i]);
		else{
			if(!right.empty()){
				point topmost = right.back();
				right.pop_back();
				int dist = (v[i].x - topmost.x)/2;
				ans[v[i].idx] = dist;
				ans[topmost.idx] = dist;
			}
			else
				left.push_back(v[i]);
		}
	}
	while(left.size()>=2){
		point l = left.front();
		left.pop_front();
		point r = left.front();
		left.pop_front();
		int dist = l.x+(r.x-l.x)/ 2;
		ans[l.idx] = dist;
		ans[r.idx] = dist;
		if(dist==6){
			cout<<l.x<<" "<<r.x<<endl;
		}
	}
	while(right.size()>=2){
		point l = right.front();
		right.pop_front();
		point r = right.front();
		right.pop_front();
		int dist = m-(l.x+r.x) / 2;
		ans[l.idx] = dist;
		ans[r.idx] = dist;
	}
	if(!left.empty() && !right.empty()){
		point l = left.front();
		point r = right.front();
		int dist = m+(l.x-r.x)/2;
		ans[l.idx] = dist;
		ans[r.idx] = dist;
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		cin>>n>>m;
		vector<point>a(n);
		vector<point>odd,even;
		for(int i = 0;i<n;i++){
			cin>>a[i].x;
			a[i].idx = i;	
			if((a[i].x)&1)
				odd.push_back(a[i]);
			else
				even.push_back(a[i]);
		}
		for(int i = 0;i<n;i++){
			cin>>a[i].dir;
		}
		memset(ans,-1,sizeof ans);
		helper(odd);
		helper(even);
		for(int i = 0;i<n;i++){
			cout<<ans[a[i].idx]<<" ";
		}
		cout<<"\n";
	}
}

I made a struct point which contains x(coordinate of point), idx(index of point) and dir(direction — L or R).

Now as you can see in my helper function I have sorted the vector according to their x coordinates. But after sorting the points when I print some arbitrary points dir(direction) the output comes out to be hexadecimal(I think) like this : 000d 0a00 0d0a 000d 0a00 0d0a 3520 370d.

Can anyone tell me why is this happening and how to fix this?

Read more »

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

By arnav2004, history, 16 months ago, In English

I was recently solving this question using binary search(https://codeforces.com/problemset/problem/1201/C). I came to know about my mistake as my formula for calculating mid was low+(high-low)/2 but instead when I use low+(high-low+1)/2 I get AC.

My questions is when(and why) do we use low+(high-low+1)/2. I tried to google it and could not find any link which answers my question.

Read more »

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