PROBLEM LINK
Problem Setter:
Problem Tester
Editorialist- Abhishek Pandey
DIFFICULTY
EASY
PRE-REQUISITES
Greedy Algorithm, Basic knowledge of data types, Looping and Arrays
PROBLEM
Given an initial pile with money S, we are given relation to form N additional piles. The cash in a pile is equal to {\sum}(Cash in all previous piles) + a given value {C_i}. Now we have to see if we can find a subset of piles such that their sum is exactly X.
QUICK EXPLANATION
We form the piles only till required, after which we greedily choose the piles for an AC.
EXPLANATION
The question must be appreciated for at how many levels it can get you a WA. Going to tackle the question head-on is bound to give a Wrong Answer verdict.
Observation 1:
The first thing we must notice is that how the series grows. It grows faster than fibonacci series. If you want some rough idea, the 100th term of fibonacci series is somewhere around {10}^{20}.
Whats the significance of series growing too fast?
The significance is hidden in constraints.
1${\le}$ S, X, {C_i} {\le} {10}^{18}
We ought to ask ourselves two simple, yet crucial questions.
-
Do we really need to compute and store all terms?
-
Can we even store all the terms comfortably in conventional data types?
The answer to both the questions is NO!
Its obvious that, if X {\le}{10}^{18}, its no sense storing any term greater than that. Also, even if you wish to store, you cannot do so without a overflow. Overflow is bound to happen if you go storing every term upto {10}^{5} , even for the smallest series. Also, if you’re thinking about BigInteger libraries, you should note that the given series grows very fast- you guys are risking a TLE as numbers this big need more time for operations/computations.
Hence, in light of above arguments, we will store only those terms which are {\le}X or {\le}{10}^{18}, as convenient for ourselves. I chose {\le}{10}^{18} in my solution.
Observation 2:
Let f(n) denote the n'th term of series. We know that f(n)= f(n-1)+f(n-2)...+{C_i} (Ci given in input).
Its clear that f(n) is strictly greater than sum of all the terms before it. This makes solving this question comparatively easier, because now we can simply use Greedy approach to arrive at answer.
Lets take an example. Let the series be {1,3,6,15,30,70} for some given value of {C_i}. Lets have a look at pile with value 30. The sum of all piles before it is 1+3+6+15=25 which is less than 30. Let me use the term “pile 30” to denote “pile whose value is 30.”
Now, what will you do if X has a value in range (30,70)? Observe that, if we leave out pile 30, we cannot form any value between 30 and 70. The piles before pile 30 cannot be used to form a value between piles 30 and 70 if we exclude pile 30. This is because even on including all piles before 30, we cannot form a value more than that. We are completely dependent on pile 30 to form values between 30-70.
Generalizing this observation, we can formally state-
Theorem 1: If value of X lies between value of 2 adjacent piles P and Q, such that P{\le}X{\lt}Q, we cannot reach X if we exclude P.
We can confirm that the above holds for even the smallest series in the question.
Clearly, it is formed for S=1 and {C_1}={C_2}=...={C_n}=1. The series is a very familiar series! On computing you will find that it is nothing other than {1,2,4,8,16,32....{2}^{n-1}}. And obviously, the theorem I stated above holds here!
My theorem holds even for the smallest series, so it is obviously holding for the bigger ones as well. It is all a matter of thinking on the question instead of immediately tackling it head-on.
Once you make this observation, this question becomes really trivial to solve. We make a simple loop, starting from the greatest term we computed (because i emphasize, we are NOT computing all {10}^{5} terms!). From there, we include all piles of value P for which P{\le}X. If after reaching the end of loop, we X is 0, this means a subset exist, else if X is non-zero, it means such a subset does not exist.
But I want to stress again, take care in implementation. There is a good scope of doing errors, which can easily invite unwanted penalties. For more details, check editorialist’s solution.
Time Complexity- O(N)
SOLUTIONS-
PROBLEMS TO PRACTICE GREEDY
I gave a link in pre-requisites. Do check it out!!
Equal - A bit of observation and greedy will make your day! Take care of final Test Case though 
Temple of Snakes - Its a problem from Snackdown Pre-Eli round A. A very decent problem, which can be beautifully solved using the concept. However, it might not be a beginner friendly question.
CHEF VIJJU’S CORNER
Well, there are a few interesting things we can discuss about this question.
1.I said that series grows quickly, and even in lowest series of {1,2,4...} we can only store ~60 terms. Why not use standard exponential algorithm of “Subset of sum K in an array” with meet in middle algorithm?
Well, honestly, I will recommend not risking it. In lowest series of {1,2,4...}, the number of terms is around ~60, and this means that you need to do atleast {2}^{30} computations. That too, for a single test case. Its really easy to frame a test case to give this approach a TLE. Its given that 1{\le}sum of N over all test cases{\le}10^5 . So it means, I can set N=100 and give T=1000, and then this approach will surely time out. Its better safe than sorry.
2.I mentioned that greedy holds because of the fact that f(n)> f(n-1)+f(n-2)....+f(1). What if this condition doesnt hold? Can we still use above approach?
No. An easy counter example is, take piles as [7,16,22]. 7+16=23>22. Lets say I give X=23. Clearly, our pretty approach fails here. Greedy algorithm isnt exactly applicable to huge number of problems, but where ever its applicable, it makes our life easy
3.The reason why we were able to use greedy here is because of f(n)> f(n-1)+f(n-2)....+f(1). If you see this property being satisfied anywhere, then give greedy a shot! One of the good examples is-
Given an equation a{X_1}+b{X_2}+c{X_3}...=K, find if there exists a solution to the equation such that {X_i} is either 1,0. It is guaranteed that b{\gt}a,c{\gt}a+b and so on. One example is-
6x+2y+z=7
Can we solve this using greedy? Why/Why not? What if we change the Q to X can be -1,0,1. Will the property still hold? Why/Why not? (10-25 karma to whosoever answers this decently 
)