Right now, I'm trying to solve https://codeforces.com/problemset/problem/4/A. Im new to codeforces but I am super experienced at competive programming. I think it is a very hard question. The time constraints suggest an O(n^4) soution and iam pretty sure that my solution is O(n^4 but it tle on the sample case. Is there some way to improve my existing solution or am i mising something really beig with my solution?
void isCurrentNumberEvenOrNot(int currentNumber) {
bool isEven = false;
for (int numberOfTwos = 0; numberOfTwos <= currentNumber; numberOfTwos++) {
int totNumber = 0;
for (int currentNumberOfTwos = 0; currentNumberOfTwos < numberOfTwos; currentNumberOfTwos++) {
totNumber = totNumber + 2;
}
if (isCurrentNumberEvenOrNot(totNumber) && totNumber == currentNumber) { // to make sure totNumber is even or not
isEven = true;
}
}
if (isEven)
return true;
else
return false;
}
int main(void) {
int weight; cin >> weight;
bool yes = false;
for (int pile1 = 0; pile1 <= weight; pile1++) {
for (int pile2 = 0; pile2 <= weight; pile2++)
if (isCurrentNumberEvenOrNot(pile1) && isCurrentNumberEvenOrNot(pile2) && pile1+pile2 == weight)
yes = true;
}
if (yes)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
any Help would be greatly appreciated. Also this is my first try at a codeforces blog post so it may be weirdly formatted.
Everyone who downvoted is gay