Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### pritishn's blog

By pritishn, 2 years ago,

demoralizer and I were discussing our 2+ years old code and I thought it'd be a good motivation for newbies and pupil who write cancer currently.

Please contibute by sharing code(in spoiler tag) or links to your of your big brain moments from back when you were low rated.

My biggest big brain moment was when I assumed inbuilt std::sort must be slower, so copied merge sort from gfg. https://www.codechef.com/viewsolution/23270721

• +121

| Write comment?
 » 2 years ago, # |   +33 This is where this discussion began: When I was too dumb to use loops
•  » » 2 years ago, # ^ |   +6 Ultimate toga moment for all programmers.Bravo Napoleon.
•  » » 2 years ago, # ^ |   +167 What about gauss elimination by hand? pic
•  » » » 2 years ago, # ^ |   +29 I really love panic in your code.
•  » » 2 years ago, # ^ |   +61 You were too dumb to even spell eight correctly back then XD
•  » » 2 years ago, # ^ | ← Rev. 3 →   0 I had the opposite problem, I was trying to solve a puzzle where you needed to fill in around 30 cells with either 0 or 1, so I wrote 30 nested for loops
 » 2 years ago, # |   +60 assumed inbuilt std::sort must be slower atleast you had knowledge of stl,I used to write gcd ,sort functions on my own and instead of pair I was using 2d array.
 » 2 years ago, # |   +74 newbies and pupil who write cancer currently. Don't underestimate me, I still write cancer solutions to simple problems. (I remember spamming maximum bipartite matching on a div2 B in-contest.)
•  » » 2 years ago, # ^ |   +14 I once used Backtracking + CircularLinkedList + Sets and Randomization to solve a div2 A, felt empty despite the AC, but at that moment, not solving A would've been harder to digest. submission
 » 2 years ago, # | ← Rev. 2 →   +66 As someone already pointed out, all of us write cancer solutions from time to time.For example, this problem from the ICPC WF Invitational mirror had a trivial $O(n^2)$ solution, but I didn't read the constraints and used lex and yacc to generate this monstrosity of a solution that works in $O(n)$ instead.Edit: since someone said the submission isn't visible, here you go.
•  » » 2 years ago, # ^ |   +2 scrolled mouse wheel 28 times to reach bottom of your solution . [on ideone]E P I C :)
 » 2 years ago, # |   +13 I remember one time I solved a rather tough problem for my level but ended up not implementing it because I thought time complexity for nCr is O(n) and not O(r).
 » 2 years ago, # |   +100 I thought writing a $O(n^2)$ in cpp instead of java would get me an Accepted solution.
•  » » 2 years ago, # ^ |   -24 In some special cases you can actually do it as there are some optimization tricks available on C++
•  » » » 2 years ago, # ^ |   0 Not quite sure why am I wrong here. It is not all the cases but rather than special cases.Such as: The case when $O(n^2)$ is enough and intended solution yet your constant factor is bigger than the author. There is a difference in some functionalities that you can use to improve the speed Not kidding but some C++ template functions is actually very good compared to some java functions that you can use for problem like flow, matching, fft, or geometric, polygon stuffs for one that dont have Friendly Cache Implementation Constant Optimization Pragma Vectorization Bit-hack Tricks
 » 2 years ago, # |   +4 I thought that binary search is so slow in special cases so I use random middle pivot to boost it in those cases :)
 » 2 years ago, # |   +61 I thought inserting #pragmas in my code will magically make my code fast, so I should not bother about time complexities anymore!
 » 2 years ago, # |   +33 I thought maps are magical. Just insert elements into a map, and voila, you have sorted the input in O(n). I remember telling this to my friend and then proceeding to have a clown moment for the rest of the day.
•  » » 2 years ago, # ^ |   -7 Well, if you consider frequency array as map... int mpp[maxN]={0}; for(int i=0;i
 » 2 years ago, # |   +9 I thought most of the $O(n^2)$ solutions would pass if I use correct pragma :(
•  » » 2 years ago, # ^ |   +39 Knowing generic_placeholder_name, that is most likely the case.
 » 2 years ago, # |   +45 I thought printing sample test cases output will give me accepted
 » 2 years ago, # |   +18 I used to think set operators like |(Union),&(Intersection) in python has O(1) time complexity.
 » 2 years ago, # |   +17 I used to learn Z-function by heart without understanding how it works at all before I attended offline competitions. I was afraid of tasks about strings and thought that somehow z-function might save me. It did not work out even once)
 » 2 years ago, # |   +17 string a, b; 1. a = a + b; 2. a += b; I used to think both 1 and 2 were equally efficient.
•  » » 2 years ago, # ^ |   -19 I still think they are equally of same time complexity :( Aren't they?
•  » » » 2 years ago, # ^ |   0 Let $n$ be the size of $a$ and $m$ the size of $b$, then the first one is $O(n + m)$ and the other is $O(m)$.This is because it returns a new string by doing a + b. a += b on the other hand, just appends b to a, it's like push back in vector. As a side note, push back also works there: a.push_back(b).
•  » » » » 2 years ago, # ^ |   +6 It's not strictly $O(m)$, but it's $O(m)$ on average and $O(n+m)$ at max. That's also important to know, though I don't have a sample of code, where it matters.
•  » » » » » 2 years ago, # ^ |   +1 Are you talking about the case when a reaches its maximum capacity by doing a += b?
•  » » » » » » 2 years ago, # ^ |   +7 I am
•  » » » » 2 years ago, # ^ |   +3 Thanks for clarification
 » 2 years ago, # |   +51 Younger me refuses to acknowledge the existence of arrays...The naming was adequate though
 » 2 years ago, # |   +159 Wrote an solution with exponential complexity where $n = 2e5$, got TLE, searched Google: How to speed up program in C++ then added ios_base::sync_with_stdio(false); cin.tie(NULL);, spent the rest of the contest wondering why I still got TLE...
 » 2 years ago, # |   +37 Will let you know once I become high rated :).
 » 2 years ago, # |   +84 When in my first contest on codeforces (div3 round) I got +500, I thought I will become red after few more contests.
 » 2 years ago, # |   0 Anyone else once thought that vector.insert works in $O(1)$?
 » 2 years ago, # |   +32 me thinking that $O(n^2)$ is faster than $O(n log n)$
 » 2 years ago, # |   0 Those cases in which I was getting TLE or WA on gfg, I just copy those cases, and put if condition for those and print the result in O(1) SpoilerI solved nearly 10-12 problems in similar manner on interviewbit and gfg :):
 » 2 years ago, # |   +15 I had some weird obsession with macros.. warning: disturbing content below lookin case the image doesnt show up, click here
•  » » 2 years ago, # ^ |   +20 long long :D
•  » » 8 days ago, # ^ |   0 man I'm not high rated bt I still use a looooong macro. Is that bad :(? First: Second:
 » 2 years ago, # | ← Rev. 2 →   +1 I used to think that std::lower_bound in a set was $\mathcal{O}(\log N)$ and surprisingly solved many problems, until the day when I TLE'd
•  » » 2 years ago, # ^ |   +20 Didn't you mean std::lower_bound on set?
•  » » » 2 years ago, # ^ |   0 Yes, thanks for pointing it out.
•  » » 2 years ago, # ^ |   0 Umm.. Noob here ! Isn't lower_bound operation on a set or sorted vector O(log n) ??
•  » » » 2 years ago, # ^ |   +1 For sorted vectors it's logarithmic but for sets it's linear std::lower_bound on set
•  » » » » 2 years ago, # ^ |   0 Are you sure?, I still think that it's logn and used it many times and didn't got TLE.
•  » » » » » 2 years ago, # ^ |   +1 As mentioned here, std::set doesn't has random access iterators, so the time complexity is linear.
•  » » » » » 23 months ago, # ^ | ← Rev. 2 →   +9 If you have a set S, then "S.lower_bound(number)" is O(logN), but "lower_bound(S.begin(), S.end(), number)" is O(N). One is a member function, the other is a generic function in the "algorithm" header. Make sure to not mix these up!
•  » » » » » » 8 days ago, # ^ |   0 True
•  » » 2 years ago, # ^ |   +5 Lesson: use std::set::lower_bound instead of std::lower_bound on set
 » 2 years ago, # |   +3 Another edition of "I still write cancer": Switch case is something that I will not use in 100 years. If else it is. So at my latest test at the university, we had a trivial problem with dates (day,months,years) and some operations with them. So my code has like a million of: if (m == 1 || m == 3 || m == 5 || m == 7 || ) ... 
 » 2 years ago, # |   +6 Not high rated, but in my first contest which was a google kickstart, I didn't knew that godly things like std::sort exist, and as I just completed the MIT course on algorithms (because for some reason I thought I'd clear IOI by watching it), I know heap sort is the fastest thing I know so I copied the heap sort code from gfg (that too in java cuz aman dhotarchor said java is better) and ended up in getting an RTE which I spent whole hour figuring out.Second one: my first contest on CF was by coincidence an April Fools round and I ended up solving three problems, so I thought I am cyan level from the start
 » 2 years ago, # | ← Rev. 2 →   +48 Binary searchwhile(hi - lo > 5) { mid = (lo + hi) / 2 if(check(mid)) hi = mid else lo = mid } // now linear search between lo and hi. 
•  » » 2 years ago, # ^ |   0 I still do this for ternary search. :P
•  » » 9 days ago, # ^ |   0 Valid
 » 2 years ago, # | ← Rev. 3 →   +9 learning not basic data structures while being greenalso tried reading about splay tree when i was 1300 to flex on my friends with it
 » 2 years ago, # |   +70 When I heard people talking about "node", I thought it was some graph shits. Turned out to be nodeJS.
 » 2 years ago, # |   +34 I used to think rating was directly proportional to how many macros you used. Viewer discussion is advised#define in std::cin #define out std::cout #define endl std::endl #define Max(a, b) std::max(a, b) #define Max3(a, b, c) std::max(a, std::max(b, c)) #define Min(a, b) std::min(a, b) #define Min3(a, b, c) std::min(a, std::min(b, c)) #define MaxE(a, b) a = std::max(a, b) #define MinE(a, b) a = std::min(a, b) #define Getbit(a, n) ((a >> n) & 1) #define Bitcount(a) __builtin_popcount(a) #define Gcd(a) __gcd(a) #define S std::string #define Ss std::stringstream #define VI std::vector #define VS std::vector #define VPII std::vector > #define VPSI std::vector > #define VPIS std::vector > #define VPSS std::vector > #define Mp(a, b) std::make_pair(a, b) #define PII std::pair #define PSI std::pair #define PIS std::pair #define PSS std::pair #define SI std::set #define SS std::set #define SPII std::set > #define SPSI std::set > #define SPIS std::set > #define SPSS std::set > #define VII std::vector::iterator #define VSI std::vector::iterator #define VPIII std::vector >::iterator #define VPISI std::vector >::iterator #define VPSII std::vector >::iterator #define VPSSI std::vector >::iterator #define MsI std::multiset #define MsS std::multiset #define SII std::set::iterator #define SPIII std::set >::iterator #define SPSII std::set >::iterator #define SPISI std::set >::iterator #define SPSSI std::set >::iterator #define MsII std::multiset::iterator #define MsSI std::multiset::iterator #define MapII std::map #define MapSS std::map #define MapIS std::map #define MapSI std::map 
 » 2 years ago, # |   +3 Wrote an exponential solution to this problem and it passed pretests and FSTed. I thought I solved a Div2 C for the first time :(
 » 2 years ago, # |   +9 I used to believe std::lower_bound and std::upper_bound is all that binary search algorithm is.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +3
•  » » 23 months ago, # ^ |   +3 Well , I believe that too even today as noob coder
 » 2 years ago, # |   +13 i thought $\frac{10^6}{2} = 10^3$ in a contest and proceeds to spend whole contest wondering why my code got TLE.and this has happened more than once :)
 » 2 years ago, # |   +5 I thought the compiler on cf wont be able to tell what the result of program was. So I quoted with the output Spoilercout<< "The answer is : " << ans << endl;
 » 2 years ago, # |   0 And then also you got WA :)
•  » » 2 years ago, # ^ |   0 Me doing binary search as: checking mid element and if mid
 » 2 years ago, # |   +3 To get the minimum integer of an array I used *min(vec.begin(), vec.end()). To test this I took a "random" array in which the first element was the minimum of the array :). So it took me a long time to figure out what was wrong.
•  » » 9 days ago, # ^ |   0 Fun fact: You can now use std::ranges::min(vec) from C++20 onwards.
 » 2 years ago, # |   +6 I used to think that stl size() function has complexity of O(n) and always stored the size in a variable before writing a loop.
 » 2 years ago, # | ← Rev. 2 →   +26 I once thought I had invented an O(n) sorting algorithm. Didn't know time complexity of map back then. Spoilervector sort(vector ar) { map mp; for(int i=0;i sorted_array; for(auto x : mp) while(x.second--) sorted_array.push_back(x.first); return sorted_array; } 
•  » » 23 months ago, # ^ | ← Rev. 2 →   0 -
•  » » » 23 months ago, # ^ |   0 You can't maintain sorted order in unordered_map :p
•  » » » » 23 months ago, # ^ |   +3 And that's what happens when you comment before coffee! Yeah no way that works
 » 2 years ago, # |   0 56589098, I solve this during the contest when I was newbie, a Few days later I got that this was a "prefix sum" approach.
 » 2 years ago, # | ← Rev. 2 →   +9 A fairly long time ago I had no idea functions exist and wrote everything in the main()Without an understanding how to do functions, when I encountered any problem with some graphs, I would be trying to make graph traversal algorithms using for loops, gotos(yeah...), and bools, all in main(), and it was WILD.I remember how I would have 5 nested for loops and a million ifs inside and would be thinking "why does it have to be so complicated". Debugging was a total nightmare, and it was more or less like "if i don't fix this within an hour i give up". Unfortunately i cant get any code from that time cause it was on an old laptop that doesnt work anymore lol.You can imagine how it felt to find out about recursions and dfs lmao.
 » 2 years ago, # |   +8 I once had an $O(n)$ solution to a problem. Complexity was ok but the problem had $1e5$ testcases(so solution must be calculated in a single $O(n)$ pre-processing). Got a TLE on pretests so I made a global map which stores the values after printing them in each testcase. Passed pretests and FSTed.
 » 2 years ago, # | ← Rev. 2 →   +33 More than 6.5 years ago. Must've been doing competitive programming for 7-8 months or so, I didn't know about digit dp. Was trying to solve https://projecteuler.net/problem=164, so I ended up writing code whose output was the code that solves this problem. https://ideone.com/XgqZDh
•  » » 2 years ago, # ^ |   0 Did it work?
•  » » » 2 years ago, # ^ |   0 Oh yeah, it did :)
•  » » 2 years ago, # ^ |   0 That's hilarious XD
 » 23 months ago, # |   +3 I used Pascal
 » 23 months ago, # |   +81 Recently I invented centroid decomposition on array(I forgot that it's called segment tree)
 » 23 months ago, # |   +1 Back when I didn’t know what the Sieve of Eratosthenes was, I used to make an array with all the prime numbers within a range for any solution that required them. Ex. 104820322Needless to say, the speed at which I came up with this type of solution was awfully slow.
 » 23 months ago, # | ← Rev. 3 →   +4 I used t think that we need to learn whole C++ along with all the Data Structures and Algorithms in the world before starting Competitive Programming, as the word Competitive seemed too scary. I used to think that only the best coders need to compete in order to deicide the best of the best, like in the Olympics.Thanks to my college seniors for kicking my ass right from the beginning, I didn't end up making that mistake.
 » 23 months ago, # | ← Rev. 5 →   +1 never trusted function swap(a, b); I always wrote: my code:void my_swap(int a, int b){ int c; c=a; a=b; b=c;}
 » 23 months ago, # |   0 Used to generate short permutations without using array. codeprogram Permutation_12; var a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12,i,m,n:byte; k:integer; begin randomize; readln(n); i:=0; a1:=0;a2:=0;a3:=0;a4:=0; a5:=0;a6:=0;a7:=0;a8:=0; a9:=0;a10:=0;a11:=0;a12:=0; if (n>0) and (n<13) then begin write('('); repeat begin k:=i; m:=random(n)+1; if (m=1) and (a1<>1) then begin write(m); a1:=1; i:=i+1; end; if (m=2) and (a2<>1) then begin write(m); a2:=1; i:=i+1; end; if (m=3) and (a3<>1) then begin write(m); a3:=1; i:=i+1; end; if (m=4) and (a4<>1) then begin write(m); a4:=1; i:=i+1; end; if (m=5) and (a5<>1) then begin write(m); a5:=1; i:=i+1; end; if (m=6) and (a6<>1) then begin write(m); a6:=1; i:=i+1; end; if (m=7) and (a7<>1) then begin write(m); a7:=1; i:=i+1; end; if (m=8) and (a8<>1) then begin write(m); a8:=1; i:=i+1; end; if (m=9) and (a9<>1) then begin write(m); a9:=1; i:=i+1; end; if (m=10) and (a10<>1) then begin write(m); a10:=1; i:=i+1; end; if (m=11) and (a11<>1) then begin write(m); a11:=1; i:=i+1; end; if (m=12) and (a12<>1) then begin write(m); a12:=1; i:=i+1; end; if (i<>n) and (i>k) then write(','); end; until i=n; writeln(')'); end else writeln('[>12]'); end. 
 » 23 months ago, # |   +3 I thought printing sample cases brings me above those who do not attempt the questions and gives me + rating.
 » 23 months ago, # |   +8 I used to be obsessed with doing the XOR trick to swap two integers w/out a dummy variable. I thought it was a galaxy brain thing to do.
 » 23 months ago, # |   +7 Once doing a problem during some contest I was too amateur to understand what sum of k over test cases meant . So had an idea to solve the problem using two nested for loops one for N and another for K . Thought the complexity was O(N*K) and it would Tle , so didnt proceeded with the solution only to find out editorial had the same solution and spent like two weeks wondering why it would not Tle Later on understood complexity was O(N+K) because it was written sum of K over all test cases was less than 1e5
 » 23 months ago, # |   0 I used to assign whatever phrase came to mind at the time to strings whenever I needed a way to set them to null.I also thought array indices started from 1.Enjoy: 26783948
 » 23 months ago, # |   0 thought that problems were stupid and C++ was too slow because my O(n^2) solution gives TLE.
 » 23 months ago, # |   +11 learned dinic's flow algo while struggling to get out of green!
 » 8 days ago, # | ← Rev. 2 →   +3 wrote this to find max of 3 numbersint a,b,c,x,y,z; cin>>a>>b>>c; if(a>b) { if(a>c) { x=a; y=b; z=c; } else { x=c; y=a; z=b; } } else { if(b>c) { x=b; y=a; z=c; } else { x=c; y=a; z=b; } } 
 » 8 days ago, # |   0 I remember reading about what union find does and then thinking "oh that sounds easy enough to implement".I then went on to code some $O(n^2)$ algorithm for the unite and find functions and was confused why it was too slowThat was the day I learnt about the importance of time complexity.