MULDIV - Editorial ( NCC 2014 )

editorial
, ,
1

PROBLEM LINK:

Contest

Practice

Author: Vaibhav Tulsyan, Aditya Sarode

Tester: Aditya Sarode

Editorialist: Aditya Sarode

DIFFICULTY:

SIMPLE

PROBLEM:

F:

for i from 1 to M inclusive, do

if N is a multiple of K,

	divide N by K

else,

	multiply N by K

print N

Perform the operation F on N.

QUICK EXPLANATION:

The given pseudo code’s complexity will be O(M) and 1<=M<=10^10
Hence, directly implementing the pseudo code will result in TLE.

EXPLANATION:

If N is not divisible by K, then the answer for the problem will be either N or KN.
If M is odd, then the answer will be KN, else it will be N
If N is divisible by K, then we go on dividing N by K until it is no more divisible by K, once the value of N is not divisible by K, we can easily find out the answer. As, the answer now can be either N or N*K.

Note that while dividing N by K, it should not be divided more than M times.

The pseudo code will be:


if K == 1:
	answer = N
else:
	while N%K==0 and m!=0:
		N = N/K
		M = M-1
	if M%2==1:
		N*=K
answer = N

Complexity: O( log(M)/log(K) )

2 Likes
2

Why was this code TLEing?

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <climits>
#include <set>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t;
	cin >> t;
	while(t--)
	{
		long long int N,M,K;
		cin >> N >> K >> M;
		if(N%K == 0)
		{
			long long int KK = K*K;
			while(N%KK==0) { KK *= K*K;}
			N = N%KK;
			if(M%2==0)
				cout << N << endl;
			else
				cout << N/K << endl;
		}
		else
		{
			if(M%2==0)
				cout << N << endl;
			else
				cout << N*K << endl;
		}
	}
	return 0;
}

Any tips?

3

Your code will loop infinitely for k = 1.

1 Like
4

For K=1 your program will go into an infinite loop.

1 Like
5

i got this code whixh is producing a TLE… please help

#include<stdio.h>
int scan(){
long long int t=0;
char c;
c=getchar_unlocked();
while(c<'0' || c>'9')
c=getchar_unlocked();
while(c>='0' && c<='9'){
t=(t<<3)+(t<<1)+c-'0';
c=getchar_unlocked();
}
return(t);
}

int main(void)
{
 long long int t,n,k,m;
 t=scan();
 getchar();
 while(t--)
 {
  n=scan();
  getchar();
  k=scan();
  getchar();
  m=scan();
  getchar(); 
 if(k==1)
 {
  printf("%lld\n",n);
 }
 else if(k!=0){ 
 if(n%k==0)
  {
   if(m%2==0)
    printf("%lld\n",n);
   else
    printf("%lld\n",n/k);
  }
  else
  {
   if(m%2!=0)
    printf("%lld\n",n*k);
   else
    printf("%lld\n",n);
  }
}
}
 return 0;
}
6

do cout.tie(NULL) as well

7

your code give wrong for test case
243 3 2
ans is 27 your code gives 243(which is wrong).

8

@karankapoor you have to divide n by k till you dont get it is divisible…but in any case you are diving only by once! so correct that and read editorial once you will get it :slight_smile:

Happy coding. :slight_smile:

9

I am getting a wrong answer for this code. I have tried almost all corner cases. still not able to understand where I am going wrong. Please help.

#include <stdio.h>
int main() 
{
unsigned int t;
unsigned long int u,n,m,c,k,i,count;
scanf("%d",&t);
while(t--)
{	
	count=0;
	scanf("%ld %ld %ld",&n,&k,&m);
	u=m;
	if(k==1)
	printf("%ld\n",n);
	else
	{
		if(n%k!=0)
		{
			if(m%2==0)
			printf("%ld\n",n);
			else
			printf("%ld\n",k*n);
		}
		else
		{	
			while((n%k==0)&&(m!=0))
			{
				n=n/k;
				m--;
				count++;
			}	
			c=u-count;
			if(c%2==0)
			printf("%ld\n",n);
			else
			printf("%ld\n",k*n);
		}
	}	
}
return 0;

}