How many problems will be there

Iterate over the number of colours you use (let it be x). You fix the colour of the root. Then you simply choose x-1 vertices out of n-1. And multiply it by ncr(k, x) * x!. Sum up the values for all possibilities of x, ranging from 1 to k. :)

Subset sum. O(N * MaximumPossibleSum)

If author sets 50 tests with maximum contraints, I think many accepted submissions will fail!

u can make it 32 times faster with bitset

We will have a replay on Monday. Editorials will be posted afterwards.

It can also be done by using a merge sort-tree and binary search.

We had included a note section specifically for this reason. We will try to get the stack size increased though.

Yes, but once you notice it (which wasn't easy — putting note at top and bolding it would help), the fix is trivial. Just google "codechef stack size", and you find out that you're allowed to perform setrlimit() call.

I did this and got WA, then found my mistake after contest. I don't know if it is right or not.

We will take all numbers greater than 31 which are prime(at most once). Now we are left with 2 types of numbers, 1.) Those less than or equal to 31 and 2.) those which have 1 prime greater than 31 and others less than or equal to 31 in its prime factorization. Lets call this prime which is greater than 31 in the second kind of numbers as big prime. Now we can do a bitmask DP in which we either take a element or not take it. There is an additional condition, we can take only 1 element from all numbers which have the same big prime. And if we take a number, we set the corresponding primes less that 31 in our mask.

First, notice that any number is divisible by at most one prime larger than 31. For each prime larger than 31, create a bucket of all numbers divisible by it. Also create a separate bucket for number not divisible by any of them. Now for the primes less than or equal to 31 (there is only 11 of them), use dp + bit mask. If you used a number add the mask of the primes less than or equal to 31 that divide this number and go to the next bucket (except if it's the bucket where the numbers are not divisible by any prime larger than 31).

Hope this helped.

Verdict: WA.

I considered primes less than 1000 (168 of them) and then considered all a[i]'s as single element such that prime divides a[i].

example: 2 2 7 7 12

loop from 168th prime till 1st prime and check.

prime 7 divides 3rd and 4th so our array becomes : 2 2 1 1 12 and cur_ans = 1.

prime 2 divides 1st , 2nd , 5th so our array becomes : 1 1 1 1 1 and cur_ans = 2.

I don't know why this does'nt work. I got WA with this approach.

Complexity: O(168*n)

First add prime numbers to the set, then random_shuffle and greedy algorithm. Solution accepted :)

My approach is not so clean but this is how I did it:

1. If n is odd, then the progression looks like ... a-r a a+r ... as you can see, the sum of the progression is a*n. So a=C/n, and a-(n/2)*r>0

2. If n is even, then we have something similar: ... a-r a+r a+2*r ... a+(n/2)*r, the sum of the progression is an+(n/2)*r, so 2*a+r=(2*c)/n, we should also check that the first element is positive.

Given sum, we need to find some positive start and delta, such that:

sum = (2 * start + delta * (n - 1)) * n / 2 // sum of arithmetic sequence

If answer exists, then delta is either 1 or 2.

If you manipulate with the the standard AP sum formula, it is easy to see that we basically need to find a(first value) and d(common difference) such that ((2·C) / n - (n - 1)·d) = 2·a. So basically you need to come up with d such that ((2·C) / n - (n - 1)·d) is divisible by 2 and ((2·C) / n) > (n - 1)·d). This can be done using some simple if else based on parity of ((2·C) / n) and (n - 1)·d. You can see the code for the conditions, they are straightforward.

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

typedef long long int lli;

int main(void)
{
	lli t;
	scanf("%lld", &t);
	while(t--) {
	lli n, c;
	scanf("%lld%lld", &n, &c);
	lli x = (2*c)/n;
	bool done = false;
	if(x < n)
	{
		printf("No\n");
		done = true;
		continue;
	}
	if((2*c)%n != 0)
	{
		printf("No\n");
		done = true;
		continue;
	}

	if((n-1)%2 == 0)
	{
		if(x%2)
		{
			printf("No\n");
			done = true;
			continue;
		}
		else if(x > (n-1))
		{
			printf("Yes\n");
			done = true;
			continue;
		}
	}
	else
	{
		if(x%2)
		{
			if(x > (n-1))
			{
				printf("Yes\n");
				done = true;
				continue;
			}
		}
		else
		{
			if(x > 2*(n-1))
			{
				printf("Yes\n");
				done = true;
				continue;
			}
		}
	}
	if(!done) printf("No\n"); }
}

We know that the sum of an A.P. can be written as (n/2)*(2*a + (n-1)*d) = c ,

So rearranging terms we get 2*a + (n-1)*d = (2*c/n) , if (2*c isn't divisible by n) , answer is NO.

So, the problem amounts to checking if it's possible to get a >= 1 , d >= 1 integers, such that 2*a + (n-1)*d = (2*c/n) , this could be easily checked by taking gcd of (2,n -1) and using extended euclid's.

its TLE

This happened with me as well. I changed it to scanf() and it passed :/

because of cin.tie(0) all the answers will be displayed at the end not after each query thats why you got tle.

kinda logical not to expect synchronisation when you explicitly turned it off.

Our solution is I believe

Mine solution with similar complexity passed (with treap for BST). It used hashes also. So those scary things with Aho-Corasick, 2d-stree and other complex stuff were not mandatory

After they move the problem to practice, remove the contest code name (in this case SNCKEL16) from the url to get the practice version.

One waits for them to add problems to practice.

They have replay contest today After that go to same problem and remove SNCKEL from url to go to practise version of same problem

Code

https://www.codechef.com/problems/COLTREE This problem is still not visible?

I faced the same issue during contest and this wasted some 20-25 minutes of mine, trying for a better approach. I finally gave up and tried this one expecting TLE, but it passed. The constraints should reflect the intended complexity more appropriately. :\