Note: The text editorials will be provided by the authors of the round. This video tutorial acts as an additional resource for those who prefer video over text, not as a substitute for the text editorial.
2050A — Line Breaks
Video
2050B — Transfusion
Video
2050C — Uninteresting Number
Video
2050D — Digital string maximization
Video
2050E — Three Strings
Video
2050F — Maximum modulo equality
Video
2050G — Tree Destruction
Video
How come this submission doesn't work for C problem: Submission to 2050C
I used a dp array of size (n x 9) so TC and SC is O(n) isn't it? It hit TLE somehow
recursion is computationally heavy
iterative:
295133603
Yeah, but then shouldn't question constraint be designed to handle these cases? It's technically the same answer porcelli
u are not using dp properly u are updating the matrix only when u find a valid combinations of operations, try to think at ur tree of calls
input : 33 every fork is a possible path and u are updating ur matrix to 1 only when u find a valid sum that is divisible by 9
in a bigger picture what u wrote is:
1) i try a path
if the sum of the digits on the path is not 0 mod 9 i'm going back and i m not updating the matrix [wrong]
if the sum of the digits on the path is 0 mod 9 i have found a solution
this is an exponential solution
try to use a 3th value {-1 : idk,1:found,0: ehi bro i have already try everything from this postion is usless that we are searching there}
sorry for bad english + it's 00:15 in my country + i'm sleeping
infact bro i challenge u to spot the difference between ur code and my version 295135560
btw a gigachad solution to this problems is:
the only 2 numbers that ^2 are less than 10 are 2 and 3 and change these digits is equal to adding 2 or 6 respectevely knowing that gcd(9,6) != 0 and gcd(9,2) == 1 u can exploit some properties of modular magic and bruteforce only a small set of value cuz without going deep in the modular math world:
from 0 if u add 6
0 — 6 — 12 % 9 == 3 — 9 % 9 == 0 and that's it [0,6,3,0] is usless adding more than 2 six instead for the 2
2 — 4 — 6 — 8 — 1 — 3 — 5 — 7 — 0 it's usless adding more than 8 two
u can bruteforce every possible combinations of six and two and u have ur answer :D
Oh yea typo in code sorry I messed up the return lol. I should've returned 0 instead of the -1 didn't notice that in a hurry haha
295039913
Can you tell me why it gave me TLE? Although it passes when I Used "vector<vector> dp" and pass it as a parameter
I need help with my recursive solution for problem C in memorization here is the submission 295071317
im ngl if you managed to tle on this you lowkey deserve it just take the extra 10 seconds to optimize
I wasn't trying to be rude I'm just actually curious as to why it didn't work. I am doing these questions not in the contest but in my own pace out of interest. Idm that it was tle'd but it's more or less trying to understand my solutions time complexity. My mistake was I didn't return 0 but -1 it was a silly mistake.
oh sorry didnt mean to be rude, i just think that you should have extra complexity for no reason if its not any harder to implement or think about, but it seems you had another problem. happy coding!
Yea it wasn't that hard, it's fine to be frank I'm doing this half asleep so I missed returning 0 and typed -1 there by mistake so it just lead to an exponential solution haha. porcelli thanks for pointing it out after you said 1,0,-1 it made me re-read the return part of the code and I saw that I forgot to return 0 xD.
Any idea on why this submission is causing a TLE for Problem D: 295113992. Could it be due to the i-- part? I don't think i-- is causing tle because the purpose of --i is to find a "better" digit that can be brought forward. This ensures that for the current position i, the best digit is brought to the front before proceeding but we bring forward k elements we will not reconsider them in constructing better digit. So number of element that can be brought forward also decrease for a given n
Firstly, this is D, not C. Secondly, I believe the TLE is from sorting (which takes nlogn) within the loop making
n^2logn
same story for skip
Lever So i-- is not an issue right? If I manage to optimize sorting part, the solution should work — not sure how but assuming ? I'm saying i-- is not a concern because, for example, If we're bringing forward 1e3 elements for each i, this operation will only be performed at most 200 times, given that n = max i.e. 2e5. For the first 200 iterations, we're bringing forward 1e3 better digits. After that, we can't repeat this process since there are no more elements left to bring forward.
Yeah, you can do by
Swapping repeatedly with cur,cur-1 until you're back to i for the best current position fit, as this would only be 9 at most, which is fine since that's still 9n this results in 1.8e6 which is fine, check my submission if needed
by doing this you dont need the i-- either
Thanks a lot, Lever. I was stuck trying to identify the cause of the TLE so I could avoid it in future contests. I really appreciate your help!
in problem B, why it says index picked must be 2 to n-1, i.e, the first two elements can't be picked. I can't understand the test cases also due to this condition.
because by picking a number ith u need to perform operation on number ith-1 and number ith +1 for index=1 ith-1 is not exist and for nth, nth+1 is not exist as size of array is n ,it is one based indexing
but index starts from 0, it should be 1 to n-1. Suppose for [3,2,1] array, I can only pick 1, so i can't change the first element. In test case they showed its possible to make every element equal but how?
okay so in this if u perform operation on index=1 in such like decrease the oth value by 1 then u need to increase 2th index value by 1 now see ur array becomes [2,2,2], if u consider o based indexing then how u can perform operation n-1 index ? in 0 based indexing n-1 would be the last one and in 1- based indexing n would be last one , (we can't pick start and end elements )
tbh, the problem statement sucks. "In one operation, you can pick an index I from 2 to n−1 inclusive", if I can't pick n-1, why its written like this? also generally arrays are 0 indexed. anyways got your point.
The problem statements don't care about 0 based indexing. The indexing starts from 1 and ends in N in every problem unless specified.
oh thanks. I didn't know about it. just a newbie.
No problem
why this submission for problem C give wrong answer : submission
You don't want to match the remainder in every case, just make sure the remainder is divisible by 9; considering we are converting some 2s and some 3s i.e (sum + delta) % 9 == 0
okay mine approach also got ac ,actually In this submission i take input as a integer ,but when i take input as a string it got ac
Shayan Bro, is there any way to do problem D with a custom comparator and exchange argument? I tried but failed.
I did it using custom comparator and exchanges . You can check out : https://codeforces.net/contest/2050/submission/295064096 Hope it helps.
thanks tan074
Can someone tell me why Submission: 295086417 or Submission: 295090777 didnt work?
295086417: Checking for the presence of 0 or 1 in the number is redundant if the sum of the digits is divisible by 9.
hmm