DIANE - Editorial

PROBLEM LINK:

Practice
Contest

Setter: Shahjalal Shohag
Tester: Rahul Dugar
Editorialist: Ishmeet Singh Saggu

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Ad-hoc

PROBLEM:

You are given an integer D. Find an integer sequence A_1,A_2, …,A_N such that the following conditions are satisfied:

  • 1≤N≤10^5
  • 1≤A_i≤10^5 for each valid i
  • ∑_{i=1}^{N}∑_{j=i}^{N}(min(A_i,A_{i+1},…,A_j)−GCD(A_i,A_{i+1},…,A_j))=D

EXPLANATION:

Suppose, we have a sequence A which has value x and a sequence B which has value y (Note here by the value, I mean the value we get from the sequence after applying the operation given in the problem). Then we can easily construct a sequence that will contribute value = x+y by concatenating the sequence A and B with 1 between them, i.e. the new sequence will be (A 1 B) with value x+y.

So this observation gives us a hint that we can create several sequences with certain value and just concatenate them as described above so the values add up to D. So one way to do this is to consider the sequence with two elements (b+2, b+1) this sequence will have value b (Note that gcd(b+2, b+1) = 1 as they are consecutive integers) and b lie in the range [0, 10^5-2]. We can concatenate several sequences of the above type with 1 between them to construct a sequence with value D.

So basically you have to concatenate the sequence with b = 10^5-2 until D is greater than it and keep reducing the value of D and when D is reduced such that it lies in the range [0, 10^5-2] simply concatenate the last sequence(which will be (D+2, D+1)) and you are done.

int maxA = 1e5;  // 10^5
vector<int> ans;
while(true) {
	if(D > maxA-2) { // when D > 10^5-2
		ans.push_back(maxA);
		ans.push_back(maxA-1);
		ans.push_back(1); // for concatenating the sequences of two elements
		D -= (maxA-2);
	}
	else {
		ans.push_back(D+2);
		ans.push_back(D+1);
		break;
	}
}

TIME COMPLEXITY:

  • Time complexity per testcase is O(\frac{D}{10^5}).

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
 
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t; cin >> t;
  while (t--) {
    int n; cin >> n;
    vector<array<int, 3>> v;
    for (int i = 100000 - 2; n && i >= 1; i--) {
      while (n >= i) {
        v.push_back({i + 1, i + 2, 1});
        n -= i;
      }
    }
    v.push_back({1, 2, 1});
    cout << v.size() * 3 << '\n';
    for (auto x: v) {
      cout << x[0] << ' ' << x[1] << ' ' << x[2] << ' ';
    }
    cout << '\n';
  }
  return 0;
} 
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
const int mod=998244353;
//const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}
int powm(int a, int b) {
	int res=1;
	while(b) {
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}
 
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
 
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
 
 
void solve() {
	int d=readIntLn(0,1000000000);
	vi result={1};
	while(d>0) {
		int b=min(99999LL,d+1);
		d-=b-1;
		result.pb(b);
		result.pb(b+1);
		result.pb(1);
	}
	cout<<sz(result)<<endl;
	for(int i:result)
		cout<<i<<" ";
	cout<<endl;
}
 
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	cout<<fixed<<setprecision(8);
	int t=1;
//	cin>>t;
	t=readIntLn(1,10);
	fr(i,1,t)
		solve();
	assert(getchar()==EOF);
#ifdef rd
	cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
	return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
 
void Solve() {
	int D;
	cin >> D;

	int maxA = 1e5;
	vector<int> ans;
	while(true) {
		if(D >= maxA-2) {
			ans.push_back(maxA);
			ans.push_back(maxA-1);
			ans.push_back(1);
			D -= (maxA-2);
		}
		else {
			ans.push_back(D+2);
			ans.push_back(D+1);
			break;
		}
	}
	cout << ans.size() << '\n';
	for(auto i : ans) cout << i << ' ';
	cout << '\n';
}
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int test_case = 1;
	cin >> test_case;
	for(int i = 1; i <= test_case; i ++) {
		Solve();
	}
	
	return 0;
} 

VIDEO EDITORIAL:

Feel free to share your approach. In case of any doubt or anything is unclear please ask it in the comment section. Any suggestions are welcomed. :smile:

18 Likes

Thanks
If any one needs Hindi Video Editorial - Link

4 Likes

@psychik Could we do add max only one time and then only max-1 and could we ignore that 1 as I think above case same as adding 1. Please help me with this as I just got the wrong answer during the contest. Same logic but not able to solve this one although I solved first 3 in just 54 min.

(post withdrawn by author, will be automatically deleted in 24 hours unless flagged)

When I comment there is no link in the post, and why are u abusing me.

1 Like

I am sorry

Enjoyed solving this problem :smile: .

7 Likes

Very well explained, but I think it is substring not subsequence given in the question. In video and slides you have used subsequence in context everywhere.

2 Likes

I didn’t understand your construction, can you rephrase it or give an example of how you are constructing the sequence.

If D is a prime no. greater than 1e5 than you will not get the ans by this approach.

I also used somewhat similar approach and did this(After contest) in O(1) time. This is my solution. I tried explaining explaining my thought process in the code file itself. Pardon me if the explanation is bit annoying :sweat_smile:, as I am doing this for the first time.

2 Likes

@psychik I’m sharing my solution… in which I added 1 only 1 time when we want to break the sequence of 9999 and no more than that. https://www.codechef.com/viewsolution/39032366
Unfortunately, I missed just one error of adding 99999 but deduction 99998 and I’m getting into WA. I hope it goes in the right way in the next contest. Anyway good problem.

I don’t think that’ll make a difference. Correct me if I am wrong.

I think for any number -
min(d+1,d+2) = d+1;
gcd(d+1,d+2) = 1;

so for d > 1e5 + 2
we push_back(1e5-1);
then we push_back(1e5);
and pb(1);
and then we deduct (1e5-2) from d and continue it until d becomes smaller than 1e5-2

after that, we just push_back d+1 and d+2.

I think this works without any exceptions.

2 Likes

Kindly see which comment I replied to.
I was not talking about the approach mentioned in the editorial, I was talking about a comment.

We can also use the fact that min(2x,3x)-gcd(2x,3x)=x to solve this problem.
Submission Link here.
Any suggestions what will be the complexity of this code?

@bit_maniac I have done exactly same as editorial sol. but my code is giving WA.
can you tell where am i making mistake.
https://ide.geeksforgeeks.org/2Nxczbx5zP

Your code is not handling case of (d=0).

Oh sorry buddy, My bad.

1 Like

Can you please tell why we are including 1 for every substring like p+2,p+1,1
as p+2,p+1 is also giving same answer
My submission:
https://www.codechef.com/viewsolution/39037641
@ssrivastava990 bro help please

Hey Just have a look at my approach.https://www.codechef.com/viewsolution/39027467