UNITGCD - Editorial

editorial
, , , ,
14

Here, read this.

15

Can someone tell me why my answer is wrong? I have read all prime pages on day 1 itself and then read one or two pages depending on the condition of co prime pages.
https://www.codechef.com/viewsolution/31816312
I tried running every test case possible but acc to me it gives correct output.
Please help, I am stuck on this!

2 Likes
18

Can anyone tell what’s wrong in my code for N <= 100.
Here is my code :
#include <bits/stdc++.h>
#include
#include
#include
#define ll long long
using namespace std;

const ll MAX_SIZE = 1e6 + 1;

vector isprime(MAX_SIZE , true);
vector prime;
vector SPF(MAX_SIZE);
std::map<ll, vector > m;

// function generate all prime number less then MAX_SIZE in O(n)
void manipulated_seive()
{
isprime[0] = isprime[1] = false ;
// SPF[1] = 1;
// prime.push_back(1);

for (ll int i=2; i<MAX_SIZE ; i++)
{
	if (isprime[i])
	{
		prime.push_back(i);
		SPF[i] = i;
	}

	for (ll int j=0; j < (int)prime.size() && i*prime[j] < MAX_SIZE && prime[j] <= SPF[i]; j++)
	{
		isprime[i*prime[j]]=false;
		SPF[i*prime[j]] = prime[j];
        // cout << i*prime[j] << " " << prime[j] << endl;
		m[prime[j]].push_back(i * prime[j]);
	}
}
// for(int i = 0; i < MAX_SIZE; i++)
	// cout << SPF[i] << " ";

//Reversing all the vectors of SPF
// for(int i = 1; i < MAX_SIZE; i++)
// {
//     reverse(m[i].begin(), m[i].end());
// }
return;

}

void print_answers(vector<vector > ans, ll it)
{
cout << it << endl;
for(int i = 0; i < it; i++)
{
cout << ans[i].size() << " ";
for(int j = 0; j < ans[i].size(); j++)
cout << ans[i][j] << " ";
cout << endl;
}
return ;
}

void schedule(ll n)
{
ll visited = 1;

int l = 0;
while(prime[l] <= n and l < prime.size())
{
	visited++;
	l++;
}
std::vector<vector<ll> > ans(MAX_SIZE); //vector to store answers

//pushing those numbers
ans[0].push_back(1);
for(int i = 0; i < visited - 1; i++)
	ans[0].push_back(prime[i]);

ll idx = 0;
ll it = 1;
while(!m.empty() and visited != n)
{
	bool flag = false;
    for(ll i = 2; i * i <= n; i++)
    {
        if(m.count(i) == 0)
            continue;

        if(idx < m[i].size() and m[i][idx] <= n)
        {
        	flag = true;
            ans[it].push_back(m[i][idx]);
            visited++;
            // m[i].erase(m[i].begin());
        }
        else
        	continue;

        if(visited == n)
        	break;
    }

    idx++;
    if(flag)
    	it++;
}
print_answers(ans, it);
return;

}

// ll find_largest_diff()
// {
// ll diff = -1;
// for(ll i = 0; i < prime.size() - 1; i++)
// {
// diff = max(diff, prime[i + 1] - prime[i]);
// }
// return diff;
// }

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

manipulated_seive();
// cout << prime.size() << endl;
// cout << find_largest_diff() << endl;
int t;	cin >> t;
while(t--)
{
	ll n;	cin >> n;
	schedule(n);
}
return 0;

}

19

#include
using namespace std;

int main() {
int test;
cin>>test;
while(test–)
{
int n;
cin>>n;

if(n==1)
printf("%d",n);
else
printf("%d ",n/2);

printf("\n");


if(n<=3)
{
    int ans=min(n,3);
    printf("%d ",ans);
    for(int i=0;i<min(3,n);i++)
    {
        printf("%d ",i+1);
    }
    printf("\n");
}
else
{
    int count=0;
    printf("3 ");
    for(int i=0;i<3;i++)
    {
        printf("%d ",i+1);
        
        count++;
    }
    printf("\n");
    
    int ans=1;
    for(int i=2;i<=(n/2);i++)
    {
        if(i==(n/2) && count==n-1)
        printf("%d ",ans);
        else
        printf("%d ",ans+1);
        
        for(int j=0;j<2 && count<n;j++)
        {
           int ans1=2*i+j;
            printf("%d ",2*i+j);
           // scanf(" %d ",ans1);
            count++;
        }
        printf("\n");
    }
}

// printf("\n");
}
return 0;
}

can anyone tell why the error SIGXFXZ is coming in my code??

20

why code in c++ was showing tle and same code in c worked

21

My approach consisted of printing all primes including 1 on the first day and then printing co-primes pair from remaining non-primes. With this approach I was able to get AC for 1st subtask. Can someone help me optimize this further, to find the co-prime pairs in less than O(n^2) ?
Thanks!

My solution link : link

22

Yes, I have implemented the same approach printing all prime numbers on the first day and 2 pages & 1 single page on other days. I don’t know why it shows WA. I have wasted too much time to find the case where program gives wrong output. Please help me out.
https://www.codechef.com/viewsolution/31779859

23

See endl performs two operations

  1. Next line \n
  2. Flush the stream

However \n performs just 1 operation.

And when program terminates platform automatically flushes the stream thats why \n is faster than endl

For more tricks you can check this article

24

Try for n=15

25

Seperating all prime numbers to first day ,
This was my approach

26

just add
#define endl “\n”
and your code will be accepted
endl slows the performance because it unnecessarily flush, and in this case you are using it n/2 times that significantly impacts the time.

27

i have try same approch but it shows TLE error CodeChef: Practical coding for everyone can anyone help please

28

@mohitz_007 I am getting correct output for n=15 as well, you can check for yourself. Still can’t figure out where am i going wrong. I need to figure this out! please help anyone.

29

Have u tried \ n instead of endl

30

i have written \n but it shows error

31

yes , now solution is accepted.

32

Thanks for the link

33

Here is the commented code for the solution.

34

no it is not accepted

35

My solution gets Runtime Error RE (SIGXFSZ). I found this error relates to printing more output lines. Here’s my solution. Could someone help?.

1 Like