Skip to content

Instantly share code, notes, and snippets.

@ksraj123 ksraj123/Fire and Ice
Last active Nov 10, 2018

Embed
What would you like to do?
FICE problem codechef, logic seems to be correct but getting TLE on submission. Need to make code faster. One way could be to implement memoization to reduce the number of recursive calls but facing trouble implementing the same because we will have to count the total ultimate leaves originating from each node in the recursion tree and store tha…
// link to the problem statement - https://www.codechef.com/problems/FICE
#include <bits/stdc++.h>
using namespace std;
int total_globe = 0;
void recursion(int left, int total, int done) //total is the value of n, done is the sum till now and left is the sum to be calculated in terms of odd numbers
{
int temp = left;
if (total==left) //initial call to the function
{
if (total%2!=0) //doing this because we dont want to select all of the people from one kingdom
temp--;
}
if ((left == 0)&&(total==done)) // i.e. number is completely expressed as sum of odd numbers
{total_globe++;
//cout << "reached the end case" << endl;
return;}
for (int i = 1; i <= temp; i++){
if (i%2 != 0){
recursion(left-i, total, done+i);
}
}
}
int main()
{
int num_test; cin >> num_test;
for (;num_test; num_test--){
int n, m; cin >> n >> m;
total_globe = 0;
recursion(n, n, 0);
total_globe *= 2; //as for each permutation we can start either with fire kingdom or ice kingdom
cout << (total_globe % m) << endl;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.