Contest Page | CodeChef <------- I tried this question and ran my test cases i dont see why there is a problem in my code both my subtask have failed can some1 tell me why and what changes do i have to make
Here’s my code:-
for i in range(int(input())):
l = []
n = int(input())
for i in range(1, n + 1):
l.append(i)
if len(l)==1:
print(‘1’)
else:
while (len(l) > 2):
s = l[0] + l[-1] + l[0] * l[-1]
del l[-1]
del l[0]
l.append(s)
print(l[0] + l[-1] + l[0] * l[-1])
My solution for the same logic : Solution: 43310158 | CodeChef
im not sure why you have used -1? you should not be able to access l[-1] under any scenario i think, so maybe that is the issue. Anyways, i hope my code helps a bit
can you expalin to me what is ‘‘For each test case, print a single line containing one integer ― the maximum possible value of the final number in the list modulo 10^9+7’’ And i used l[-1] to get the last element I took the last and the first element from the list then removed the last and first element and appended the result of sum and product of the numbers back into the list its a simple logic why is it wrong can u explain to me what do these subtask want in this case
right i forgot python allows list[-1] to target the last element.
for the first question you ask.
if you look at the constraints, you will see that 1 <= N <= 10^6.
meaning if you take the 2 highest values in the array, and perform the required operation (a+b+ab), you get an ans of the order 10^12.
now this IN ITSELF is a huge value. imagine doing this over every single element. Now imagine the number of digits that ans will have.
Since this is a very large number, they have asked you to calculate it modulo 10^9+7 or 1000000007, to reduce the digits.
if you dont know what x modulo y is, it basically means divide x by y and return the remainder, or more precisely, x % y which returns the remainder.
what this does is limits how big a number can be.
for eg, 2%10 = 2 (since 2 is less than 10, the number remains unchanged)
but 13%10 = 3( since the number is greater than 10, it gets brought down to a more considerable number).
I hope you see what this means. Basically doing modulo 10^9+7(which is the smallest prime above 10^9), ensures that every number remains under 10^9(which is the range of int in c++).
Since python doesnot have any limits on how big its numbers can be, you dont really have to worry about things till the end. In c++ this would have been a different story.
for your second question, you had 2 mistakes.
firstly, if the list already has only 1 element, you should be printing the element(which is l[0]) and not “1”.
secondly, in the end you need to print (the whole value) % 1000000007, because the question asked you to do it this way (i explained above pls read)
This is your solution corrected : Solution: 43316524 | CodeChef
if you need a better understanding of what subtasks are, i wrote in a bit detail here : Doubt regarding subtasks - #5 by aadarshrawat20
i hope this helps 
Happy Coding
THANK YOU SO MUCH much much appreciated
Not to be rude or anything I’m just curious why your solution failed the last 2 subtasks and passed the first what is the cause of this
dont worry dude curiosity is always good its a great community out here
well i just corrected your solution so you understand what YOU did wrong, i didnot try to make it the a fully correct one.
Here is the full solution : Solution: 43324840 | CodeChef
If you read the thread i mentioned above, you can read about what subtasks are and why they are provided, so go read that first.
Now, if you look at the constraints given,
1 <= T <= 10^5
1 <= N <= 10^6
for subtask 1,
1 <= T, N <= 25
now you see, your solution required you to do all the operations over every element of an array over all test cases.
so your time complexity is O(T * N).
T * N = 10^11
Python takes 5 sec to run 10^8 operations (this is taken as the standard, but im sure it does more), meaning your code in the worst case would take 10^11 / 10^8 s or 1000s.
but for the subtask, it will take 25 * 25 = 625 operations <<< 10^8, so pretty much no time needed. This allows the first and second cases to get accepted, since they have lower input numbers.
Now, 1000s is CLEARLY greater than 5s which is the time limit. Hence the TLE(Time Limit Exceeded).
Now it is time to improve the solution, which will just take basic observation.
If you see, the numbers donot change for the same input(meaning if N = 3, numbers will always be 1, 2, 3)
so if you start from the beginning, and perform the operations on the first 2 elements and so on, the answer will proceed this way.
1 * 2 + 1 + 2 = 5.
5 * 3 + 5 + 3 = 23
therefor for N = 3, your ans is 23. Remember this.
Now for N = 4, you get 1, 2, 3, 4
so 1 * 2 + 1 + 2 = 5
5 * 3 + 5 + 3 = 23
and now 23 * 4 + 23 + 4 = 119
although this took you 3 operations, you can see that the answer of 3 came somewhere in the solution of 4. This will always be true.
The solution for N will always be the solution of N-1 * n + n-1 + n
This is called DP(Dynamic Programing), where you store the solutions to previous questions to calculate the subsequent answers.
Now using this method, you can simply first calculate the solution for every number from 1 to 10^6+1(since 1 <= N <= 10^6), and then simply return the corresponding solution to whatever the test case asks.
You can look at my solution for how its done. Dont be afraid of asking for any clarification if needed
Hope this helps,
Happy Coding