TWOVRIBL - Editorial

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Anik Sarker, Ezio Auditore

Tester: Teja Vardhan Reddy

Editorialist: Taranpreet Singh

DIFFICULTY:

PREREQUISITES:

Binary Search, Math, Precomputation.

PROBLEM:

You have two integers X and Y both initialized to zero. Let’s define an operation as

  • Choosing any positive integer P such that P*P > Y
  • Set X = P
  • Set Y = Y+P*P

We need to answer queries, each query specifying a value V, we need to determine the maximum number of operations we can perform such that at the end, X = V.

EXPLANATION

Let us make some observations first.

For all operations except last, only the value of Y matters. It is obvious since past operations do not affect the current value of X. The only affected value is Y. For the last operation, we shall always choose the value given in the current query as P.

In every operation except the last operation, it is optimal to choose the smallest P such that P*P > Y.

The reason is that suppose R is the minimum value of P such that P*P > Y, then if we choose say R+1, then Y increases by (R+1)*(R+1) instead of R*R. This forces us to choose the higher value of P in future operations, which, combined with the fact that Y do not decrease, reduces the number of operations. Hence, at every operation, we choose the smallest P such that P*P > Y.

Now, the last thing we can notice is that performing all except the last operation is independent of the value of V as long as V*V > Y holds. So, we can just compute the minimum value of Y after q operations for each q. This sequence is always a strictly increasing sequence, and we need the rightmost position such that value at that position do not exceed V*V. Hence, we can perform a binary search to find out the rightmost position. This position gives the maximum number of operations we can perform. We need to add 1 for the final operation too.

Another solution is to just simulate the process, just by noticing the fact that the growth of the value of Y (By choosing the minimum value of P at each operation) ensures no more than approximately 59 iterations for each query, which also fits the time limit easily.

TIME COMPLEXITY

Time complexity is O(A+Q*log(A)) or O(Q*A) where A = 59 is the maximum possible answer. (Can add also be O(A*log(MX)+Q*log(A)) if we use binary search to find minimum value of P).

SOLUTIONS:

Setter 1 Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const ll INF = 2e9;
vector<ll> vec;

int main(){
	ll X = 0;
	ll Y = 0;

	while(X < INF){
	    X = sqrtl(Y);
	    while(X*X <= Y) X++;
	    while((X-1)*(X-1) > Y) X--;
	    vec.push_back(X);
	    Y += X * X;
	}

	int t;
	scanf("%d",&t);
	assert(1 <= t <= 1000000);

	for(int cs=1; cs<=t; cs++){
	    ll z;
	    scanf("%lld",&z);
	    assert(1 <= z <= 1000000000);

	    int idx = upper_bound(vec.begin(),vec.end(),z) - vec.begin();
	    printf("%d\n",idx);
	}
}
Setter 2 Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m, x, y, z;
ll t, cs = 1;

int main()
{
	cin >> t;
	if(t < 1 || t > 1000000) assert(false);

	while(t--){

	    scanf("%lld", &n);
	    if(n < 1 || n > 1000000000) assert(false);

	    ll x = 0, y = 0;
	    int cc = 0;
	    while(x <= n){
	        ll tmp = sqrt(y);
	        tmp++;
	        y += tmp * tmp;
	        x = tmp;
	        cc++;
	    }

	    printf("%d\n", cc - 1);
	}

	return 0;
}
Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
using namespace __gnu_pbds;

#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout) 
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// find_by_order()  // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

#define int ll
main(){
	//std::ios::sync_with_stdio(false); cin.tie(NULL);
	int t;
	//cin>>t;
	scanf("%lld",&t);
	int y=0;
	int x=0;
	vi vec;
	//vec.pb(0);
	while(x<inf){
		x=max((int)sqrt(y)-3,(int)0);
		while(x*x<=y)
			x++;
		y+=x*x;
		vec.pb(x);
	}
	int val;
	//cerr<<vec.size()<<endl;
	while(t--){
		//cin>>x;
		scanf("%lld",&x);
		val = lower_bound(all(vec),x+1)-vec.begin();
		printf("%lld\n",val);
		//cout<<lower_bound(all(vec),x+1)-vec.begin()<<endl;
	}
	return 0;   
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class TWOVRIBL{
	//SOLUTION BEGIN
	//Into the Hardware Mode
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    long Y = 0, X = 0;
	    long[] a = new long[100];int c = 0;
	    while(true){
	        X = sq(Y);
	        //Maximum value of X is 1e9
	        if(X > 1e9)break;
	        Y += X*X;
	        a[c++] = X;
	    }
	    for(int q = ni(); q>0; q--){
	        long x = nl();
	        int lo = 0, hi = c-1;
	        while(lo+1 < hi){
	            int mid = lo+(hi-lo)/2;
	            if(a[mid] <= x)lo = mid;
	            else hi = mid;
	        }
	        if(a[hi] <= x)pn(hi+1);
	        else pn(lo+1);
	    }
	}
	//Finds P such that P*P > x
	long sq(long x){
	    long lo = 1, hi = (long)1e9+1;
	    while(lo+1< hi){
	        long mid = lo+(hi-lo)/2;
	        if(mid*mid > x)hi = mid;
	        else lo = mid;
	    }
	    if(lo*lo > x)return lo;
	    return hi;
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	long IINF = (long)1e18, mod = (long)1e9+7;
	final int INF = (int)1e9, MX = (int)2e5+5;
	DecimalFormat df = new DecimalFormat("0.00000000000");
	double PI = 3.141592653589793238462643383279502884197169399, eps = 1e-6;
	static boolean multipleTC = false, memory = false, fileIO = false;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    if(fileIO){
	        in = new FastReader("input.txt");
	        out = new PrintWriter("output.txt");
	    }else {
	        in = new FastReader();
	        out = new PrintWriter(System.out);
	    }
	    //Solution Credits: Taranpreet Singh
	    int T = (multipleTC)?ni():1;
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    if(memory)new Thread(null, new Runnable() {public void run(){try{new TWOVRIBL().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
	    else new TWOVRIBL().run();
	}
	long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
	int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return in.next();}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(in.next());}
	long nl()throws Exception{return Long.parseLong(in.next());}
	double nd()throws Exception{return Double.parseDouble(in.next());}
 
	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }
 
	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }
 
	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	            try{
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException  e){
	                throw new Exception(e.toString());
	            }
	        }
	        return st.nextToken();
	    }
 
	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}

Feel free to share your approach, if you want to. (even if its same :stuck_out_tongue: ) . Suggestions are welcomed as always had been. :slight_smile:

9 Likes

https://www.codechef.com/viewsolution/25383212

My solution without binary search…

2 Likes

i understand the fact that we choose min p such that p*p>y but can’t understand that last operation is independent of the value of p???
plz explain…

2 Likes

can u explain me the 2 test case given in question??
according to me the sequence is 0->1->2->3->4->6->9…
Thanks…

@teja349 i print the vec u precompute before any query and is show the sequence 1 2 3 4 6 9 13 18 26 37 only 10 terms but in question it was given 1 2 3 6 8…
Can u explain???

one more thing why binary search x+1 not x

@teja349 i think val +1 is equalent to x+1 in binary search

Guys I did it like: 1->2->3->4/5->6/7/8->9/10/11/12->13/14/15/16/17->..... The concept was this that after 3, no. of steps for (4 and 5), (6,7 and 8) … will be same. So it is a sequence forming such that after 3 next 2 numbers will be having same answer, then next three, then next four and so on… But I got WA. What is the problem, can anyone explain me?

3 Likes

@code_25 No. of operation for 8 and 9 will be different. For 8 it will be 0->1->2->3->4->8 or 0->1->2->3->5->8 and for 9 this will be 0->1->2->3->4->6->9.

1 Like

This pattern vanishes as you go much higher.

1 Like

Here’s my approach: choosing P: P = sqrt(Y) + 1 :slightly_smiling_face:
AC Code
Click me here!

Can someone tell me the time complexity of my program.Thanks in advance

3 Likes

Help needed :

  1. https://www.codechef.com/viewsolution/25399009 --> WA
  2. https://www.codechef.com/viewsolution/25398939 --> AC

First one and second is exactly same code but in 1 i use scanf and in 2 i use cin but this shows WA.
Help @anon55659401 @sandy5858 @samarthtandon

Could anyone please tell me what is the problem with my code?
By observation for xf>=3 the answer is a sequence like 3,4,4,5,5,5,6,6,6,6,7,7,7,7,7 and so on which can be solved in constant time using AP properties.
Here’s my code: https://www.codechef.com/viewsolution/25393869
Thanks in Advance

How come this code passes the time constraints ?
https://www.codechef.com/viewsolution/25391464
10^8 operations = 1 sec right?
It performs more than 10^9 operations for input:
1
1000000000

format specifier is wrong in scanf

format specifier of long long int is %lld not %lli

@l_returns might help for sure :slight_smile:

I did the same bro. The pattern goes like an AP with common difference also in A.P. But, sadly the pattern vanishes as the numbers go high which we didn’t observe during the contest.

same as O(AQ) where A=59

2 Likes

Apne bhaai se puchh le na :rofl::rofl::rofl::rofl::rofl:

tourist ka to tuu bhai hai… hum sab aaam log…:grin::grin::grin:

Well jokes apart ; this AP pattern vanishes and does not hold true… I also thought of this kind of thing ; So I wrote a brute force solution to check if this pattern holds for long… but what I found out was that this pattern does not hold true ; so there is a problem in observation.

Bonus : The reason why I got a clue that this pattern might not be correct in the contest itself was the number of submissions of this problem ( A good number ). So I thought that maybe this AP might go wrong ; otherwise if the question was to be done like that ; then the number of submissions would have been much less…

So I tried to test this AP thing ; found that it fails ; and then thought of some other thing and bingo - I had the correct logic this time…

So you should always keep looking at number of submissions of a problem to find out its expected difficulty. And want to know where I read this…? In an interview of your bhaai tourist…:wink:

2 Likes