wcalgo4firstyearlog.txtlog.txt

<ishaan> : Hello! I'm Ishaan. 1st Year Comps
<Ashwin> : What's today's session about.? 
<vilas_m> : Hey guys! Sorry for the delay. Was waiting to see if your batchmates are going to join
<ishaan> : Competetive coding
<vilas_m> : So, we have a wonderful attendance today I see :P 
<vilas_m> : Are both of you comfortable with C++? 
<ishaan> : I am
<Anirudh_> : yes
<Ashwin> : Yes 
<vilas_m> : Great! :) 
<vilas_m> : So, did you guys try the problems posted on the group? Any issues?
<vilas_m> : Be quick in responding guys. Otherwise, this will get boring :P 
<ishaan> : sorry I couldn't try the problems
<Anirudh_> : No didnt try
<vilas_m> : Alright. But do try them soon and approach any of the mentors for help :) 
<ishaan> : Sure!
<Anirudh_> : OK
<vilas_m> : Ok, if you guys have seen the problems, you might have realised that many problems have several test cases for the input. 
<vilas_m> : What do you do for dealing with several test cases? 
<vilas_m> : Simple. Just write 
<vilas_m> : cin>>T; (or scanf("%d", &T); for C users )
<vilas_m> : while(T--)
<vilas_m> : {
<vilas_m> : }
<vilas_m> : Your code goes inside the flower brackets
<ishaan> : ok!
<vilas_m> : When you are coding on competitive programming platforms, one thing to realise is that - the inputs and outputs are dealt with in seperate files.
<vilas_m> : What I mean to say is, the input is read from the stdin file and the output is written stdout file by default.
<Ashwin> : Ok
<vilas_m> : This gives us a really good advantage. Can anyone guess what it is? 
<ishaan> : I don't know :/
<Anirudh_> : no idea
<Ashwin> : U can manipulate the files separately.? 
<vilas_m> : So basically you can print the output required immediately after it is calculated for a given test case. You need not wait to read all input to print the output. 
<vilas_m> : Have noticed a lot of people storing their outputs for all test cases in an array or something and then printing all of it at once. 
<vilas_m> : Don't do this ^.
<vilas_m> : Just do:
<vilas_m> : cin>>T;
<vilas_m> : while(T--)
<vilas_m> : { -Take the input for the test case
<vilas_m> :   -Do the manipulations
<vilas_m> :   -Print the output
<vilas_m> : }
<ishaan> : ohh.. okay
<Anirudh_> : okay
<Ashwin> : What's wrong if we store the outputs in an array.? 
<vilas_m> : Don't wait for the while loop to end for printing. As soon as you get the answer, print it. 
<ishaan> : time consuming?
<vilas_m> : @Ashwin, It's redundant. Why store the output in an array and then print it all at once. 
<vilas_m> : Yes ishaan.
<Ashwin> : Ok
<vilas_m> : Next
<ishaan> : ok!
<vilas_m> : I have seen many of my batchmates do this and get errors :P
<vilas_m> : Do not print redundant text such as "Enter the number of test cases", "Enter the input", "The output is:" and so on. It'll cause errors.
<ishaan> : ohh!!
<vilas_m> : I know that teachers in school/college frown seeing codes without these^ :P But please do not do this in online contests
<vilas_m> : There is no person sitting on the other end of the line who'll get impressed seeing how neat your output looks xD
<Ashwin> : Oh!! 
<vilas_m> : Your output file will be compared with the correct answer output file character by character. 
<vilas_m> : The question will specift the pattern of output required, so make sure you follow that pattern strictly
<ishaan> : Okay. Will keep that in mind
<vilas_m> : specify* 
<vilas_m> : The running time of your codes is also really important.
<vilas_m> : Typically, you will get TLE - Time limit exceeded if your code run time is over a few seconds (the limit varies according to the website/problem/language used. Generally a few seconds is set as the limit)
<ishaan> : okay
<vilas_m> : So you have to be careful and make sure the algorithms you use are efficient. 
<Ashwin> : What does run time depend on? 
<vilas_m> : The run time and time limit for each question depends on the language as well.
<vilas_m> : I am coming to that soon Ashwin :) 
<vilas_m> : For example, as Python, Java codes are much slower than C.
<vilas_m> : Time limit for Python is set five times higher than C/C++, and for Java, it is twice as that of C/C++.
<vilas_m> : Even though this relaxation is provided, it usually isn't enough to compensate for the slower languages. So it's better to use C/C++. 
<ishaan> : cool
<vilas_m> : Any doubts so far?
<ishaan> : no
<Ashwin> : Why is the run time for python,  java higher than c/c++? 
<vilas_m> : Python is a bit more abstract. Like - in c++ you specify the type of data like int, float etc right? 
<Ashwin> : Yes 
<vilas_m> : In python - You don't specify the type. You can directly use the variables
<vilas_m> : And there are many other things similar to this that makes Python, Java slower.  
<vilas_m> : Basically python is more user-friendly i can say :P 
<vilas_m> : If you guys are working on C++ (which should be preferred over C), you might have heard about how cin/cout statements are much slower than printf/scanf statements.
<vilas_m> : So, you might often see problems statements or websites saying "Use printf/scanf statements instead of cin/cout to make your codes run faster"
<ishaan> : Yes. I've heard
<vilas_m> : However, cin/cout statements are actually faster than printf/scanf
<Ashwin> : What does declaring/not declaring variable have to do with speed.? 
<Ashwin> : What makes cin cout  faster than printf and scanf.? 
<vilas_m> : The compiler has to find out which type the variable is and make sure there is appropriate memory allocated for that. For example - When you say int A[8]; it says by default to the C++ compiler that 8 elements of integer type is going to be used further on, so allocate space for it. 
<vilas_m> : But, this is skipped in Python. Additional time is required for that. 
<vilas_m> : Yea i am coming to that
<Ashwin> : Oh! Okay 
<vilas_m> : C++ IO statements are synced with the underlying C library IO statements. 
<Anirudh_> : how is cin and cout more faster han printf and scanf
<vilas_m> : This allows you to use cin/cout interchangeably with printf/scanf statements in your code and as a result, makes cin/cout run slower than printf/scanf normally
<vilas_m> : Yea, slow down Anirudh, coming to it xD 
<vilas_m> : However, you can turn this sync off and use only C++ IO statements. 
<vilas_m> : ios::sync_with_stdio(false);
<vilas_m> : Include this as the first statement inside your main function. 
<vilas_m> : As to why cin/cout statements are slower than printf/scanf - See in printf and scanf, you define %d %f etc in the format string right? 
<vilas_m> : *are faster
<Ashwin> : Yes 
<ishaan> : yes
<vilas_m> : In online contests, your run time is used as the judging parameter. Your compile time is not considered. 
<Ashwin> : Oh! Ok
<vilas_m> : In C++, all the type matching is done during compile time. When you write cout<<a; where a is an integer, the compiler knows that a is an integer to be displayed during compile time.
<vilas_m> : However in C, it is done during run time. The format string is evaluated during the run time, so this adds up for the additional time taken by printf/scanf .. 
<vilas_m> : That's why cin/cout is faster. 
<vilas_m> : Next, data types
<vilas_m> : It's always better to declare integers as long long int, floating point numbers as long double etc in case the range of input ( typically, the range of input will be available in the question ) is quite large
<vilas_m> : The range of int is around 10^9 while the range of long long int is around 10^18
<vilas_m> : Changing int to long or long long int will not affect the run time of your code much, so there is no harm in doing so if you are unsure whether you need long long int or not. 
<vilas_m> : Are you guys aware of what is a macro?
<ishaan> : no
<Ashwin> : No
<vilas_m> : #define ? :P 
<ishaan> : yes
<Ashwin> : Oh. 
<vilas_m> : Yea so macro is basically defining your own short forms for code. Say you are too lazy to type that extra "long long" for long long int
<vilas_m> : Just add
<vilas_m> : #define ll long long int
<vilas_m> : ^ this statement right after your header file declaration
<ishaan> : ok
<vilas_m> : And then use ll throughout the code :) 
<ishaan> : cool
<vilas_m> : Or even, say you are too lazy to write for(int i=0; i<N; i++)
<vilas_m> : Just add a line
<vilas_m> : #define rep(i,j,n) for(int i=j;i<n;++i)
<vilas_m> : And use rep(i, 0, N) wherever you need for(int i=0; i<N; i++)
<vilas_m> : You can write a bunch of such macros and save it in a file, and whenever there is an online contest, you could just copy paste these macros onto your code :P
<Ashwin> : Awesome 
<vilas_m> : Although, macros are generally considered dangerous if not used properly. So be careful. 
<Ashwin> : Dangerous as in.? 
<vilas_m> : Say you write rep(i++, 0, N) instead of rep(i, 0, N) 
<vilas_m> : By mistake
<vilas_m> : Basically you might get confused while using them. Just keep note of that
<ishaan> : okay!
<vilas_m> : Any other doubts so far?
<ishaan> : nope
<vilas_m> : Whenever you declare arrays of large size, say around 10^5 or so, make it a point to declare them globally. 
<Ashwin> : Is it possible to replace whole blocks of code using macros? 
<vilas_m> : Yes Ashwin. But be careful. Test them out before contests to make sure they work.
<ishaan> : will the runtime be affected if we use macros?
<vilas_m> : One of my favorite questions :P #define x 5+2 ... and y= x*x*x . What do you think will be the output?
<vilas_m> : No ishaan
<ishaan> : ok
<ishaan> : 125?
<vilas_m> : No. 
<Ashwin> : 27.?
<vilas_m> : Yes Ashwin! :) Excelelnt 
<vilas_m> : Not so excellent as my spelling though :P 
<Ashwin> : No problem :) 
<vilas_m> : Can you explain why?
<Ashwin> :  Precedence.  Right? 
<vilas_m> : Yup. Normally you might expect x =7, so y = 7*7*7 = 343. 
<Ashwin> : * has higher Precedence than +
<vilas_m> : But it's not. Because #define simply replaces x by 5+2 .. So it's 5 + 2*5 + 2*5 + 2
<vilas_m> : That's why i said #define is sometimes dangerous :P 
<ishaan> : ohh! I understood
<vilas_m> : So coming to arrays
<vilas_m> : The variables declared in the main() functions are stored in what's called a program stack. 
<vilas_m> : It's a limited memory which is allocated to the program. 
<vilas_m> : So arrays of size more than say 10^5, need to be declared outside main() as global variabls
<vilas_m> : variables*
<ishaan> : ok
<vilas_m> : As all global variables are stored in what's known as a heap. A heap can accomodate much more data than a stack because the size of the heap can keep on increasing until it occupies the entire RAM
<vilas_m> : Even while declaring them globally, make sure the size does not exceed 10^7 though
<Ashwin> : Where do we need arrays of such large sizes? 
<vilas_m> : Generally in contests, if you see the problems, they ll give the input range for number of elements to be really huge
<vilas_m> : That's why
<Ashwin> : Oh! 
<vilas_m> : I spent half an hour in a contest this year figuring out why i was getting a segmentation fault due to this :P 
<ishaan> : ohh!
<vilas_m> : So be careful
<vilas_m> : Next
<Ashwin> : What's a segmention fault.? 
<vilas_m> : It's a type of error you get while compiling codes when you mess with the memory. 
<vilas_m> : Say somewhere you want A[-1] or A[100000000000] 
<vilas_m> : Or some random errors while working with pointers
<vilas_m> : Segmentation fault
<Ashwin> : How can u declare arrays with negative sizez? What 
<vilas_m> : Exactly. That's an error right? 
<vilas_m> : It's called a segmentation fault
<Ashwin> : Oh!  Ok
<vilas_m> : Prefer writing \n instead of using endl while working on online judges
<vilas_m> : Now, when you are writing output to a certain file (stdout in our case), instead of writing data into the output file whenever a cout/printf statement is encountered, what the program does is to store output to be written in what's called a temporary buffer. 
<vilas_m> : When the buffer is full/some function which flushes the buffer is called, it flushes the entire output buffer into the output file. 
<vilas_m> : endl works by first adding a new line to the output buffer followed by flushing the buffer. 
<vilas_m> : '\n' is just a character and simply adds a new line character to the output buffer. 
<Ashwin> : What does endl do.? 
<vilas_m> : So, writing \n instead of endl can save a lot of time especially when large number of lines is to be printed for the question
<vilas_m> : Sorry, i dint get your question? :/
<Ashwin> : I mean what is endl? 
<vilas_m> : It's a predefined feature in C++
<vilas_m> : It just adds a new line
<vilas_m> : cout<<"Hello World!"<<endl; 
<Ashwin> : Ok
<vilas_m> : Never used it in +2? :/ 
<Ashwin> : Never used it
<vilas_m> : Anyway, so, writing \n instead of endl can save a lot of time especially when large number of lines is to be printed for the question
<vilas_m> : Next. 
<vilas_m> : Due to the limited time available during contests, it is a pain to identify and type all header files required in your program.
<vilas_m> : Instead of doing that, include a single header file called bits/stdc++.h in your programs (for C++ only). 
<vilas_m> : This header file includes every other header file in the C++ standard library and thus, there is no need to include any more header files.
<vilas_m> : The compile time of the program will be affected a bit due to this, but run time will not be affected. 
<vilas_m> : So there's no harm in using bits/stdc++.h at all
<vilas_m> : Although, let me warn you - Do not use it in college in any programming labs :P 
<Ashwin> : What about c.? 
<vilas_m> : There is no equivalent header file in C 
<Ashwin> : Oh
<vilas_m> : Especially in the comps dept :P Don't use this. IT Dept allows it I heard, but not sure.
<vilas_m> : mukta ?
<vilas_m> : Ok, so there's a little bit about time complexity remaining. Shall we continue or stop here?
<mukta> : IT dept doesn't really bother
<vilas_m> : Oh lol
<vilas_m> : Guys? Shall we continue with time complexity? 
<Ashwin> : So why  does comp dept get bothered with it.? 
<vilas_m> : I have no clue man xD They feel it's some sort of cheating
<ishaan> : yeah. continue
<Ashwin> : Yeah 
<Anirudh_> : yeah
<vilas_m> : Alright. So typically in C/C++, approximately 4 * (10 ^ 8 ) operations can run in 1 sec. 
<vilas_m> : The time limit and the input size of the problem will give you an idea of the complexity of the algorithm required (I'll explain what is complexity in a second, wait)
<vilas_m> : For example, if the input size range is <= 10^4 for a time limit of 1 sec, it probably means an O(n^2) solution is required. 
<vilas_m> : So, what is this O( ) something i wrote? Big-oh notation as we call it, gives an idea of the run time of an algorithm in terms of the input size
<vilas_m> : So, O(n) implies, the code will run in about n step
<vilas_m> : steps*
<vilas_m> : for example, say you have a single for loop from 1 to n (which isn't nested basically). This runs in O(n) time
<vilas_m> : Similarly, a nested for loop
<vilas_m> : for(i=0; i<n; i++) 
<vilas_m> : { for(j=0; j<n; j++) 
<vilas_m> :   { (code) } 
<vilas_m> : }
<vilas_m> : The above code runs in O(N^2) time. 
<vilas_m> : Because there are N^2 iterations in total over here 
<ishaan> : oh! Okay
<Ashwin> : Bit confusing 
<vilas_m> : @Ashwin, which part?
<Ashwin> : What is Big oh.? 
<vilas_m> : I wrote O(N) right? This is the big - oh notation. O(N) is read as Big - oh of N 
<vilas_m> : Just a name
<Ashwin> : What does it have to do with run time? 
<vilas_m> : Let's say a single iteration in the for(i=0; i<N; i++) runs in unit time. How much time will it take to finish all iterations? 
<vilas_m> : N right?
<Ashwin> : Yes of course 
<vilas_m> : Exactly. The unit time which i said over here depends on the system you are using. A super computer will obviously be faster than a normal computer. 
<vilas_m> : So to avoid telling the run time in seconds, microseconds, etc, we just tell it runs in O(N) time
<ishaan> : ok!
<vilas_m> : Ashwin? Is that clear? 
<vilas_m> : I'm defining the run time for only the for loop as O(N) and not for the entire program
<Ashwin> : Yes crystal clear:) 
<vilas_m> : Alright :D 
<vilas_m> : Consider this loop -
<vilas_m> : for(i=0; i<N; i+=2)
<vilas_m> : You might say this runs in O(N/2) time. But you can strike off the 2 there and simply say O(N) time. Big-oh notation is basically an approximation. 
<vilas_m> : That's how big oh is defined. 
<vilas_m> : So basically you can chuck any constants appearing in time complexity because it is kinda insignificant.
<ishaan> : okay! cool
<Ashwin> : Ok
<vilas_m> : O(2N) is O(N). O(N + 5) is also O(N).
<vilas_m> : But, O(N^2) is not O(N). It is O(N^2) itself. Why? Significant difference in O(N) and O(N^2). If N = 10^8, O(N) algorithms will take a few seconds to compute. 
<Ashwin> : So O(1000000N) is Also O(N).? 
<vilas_m> : But O(N^2) algorithms? 10^8 seconds. That's like a few months! 
<vilas_m> : Not exactly Ashwin :) That's one drawback of this notation. If the constants are huge, you cannot neglect the constants. 
<Ashwin> : Ok
<vilas_m> : for(i=1; i<=N; i*= 2)
<vilas_m> : Can anybody tell me what is the complexity for the above code? ;)
<vilas_m> : Take N=64 says. And count the numbers of iterations
<Ashwin> : O(N^2)?
<vilas_m> : No.. 
<vilas_m> : For N=64, can anybody trace the values of i in the iteration?
<vilas_m> : i = 1, 2, 4, 8, 16, 32, 64 and stops, right? 
<ishaan> : yes
<Ashwin> : Yes
<vilas_m> : That is 7 steps. So now can someone point out the complexity in terms of big-oh notation? :P 
<ishaan> : so O(sqrt(N)-1)?
<ishaan> : no. Sorry :P
<vilas_m> : Haha, good guess ishaan. But no :P 
<vilas_m> : What is 64? 2^6 right? 
<ishaan> : yeah
<Ashwin> : Yez
<vilas_m> : Does that give a clue? :P 
<vilas_m> : Ok, i ll give it away. It's O(log N)
<vilas_m> : I'll explain
<ishaan> : Ohh! 
<vilas_m> : The variable i will have values as 1,2,4,... 2^(n-1), where n is the number of iterations. Correct? 
<ishaan> : yes
<vilas_m> : Note that n is not equal to N. 
<vilas_m> : Should have used m or something. damn
<vilas_m> : So the for loop stops when 2^(n-1) <= N 
<vilas_m> : or i can 2^(n-1) is approximately N, yea? 
<ishaan> : yeah
<vilas_m> : 2^(n-1) = N, implies n-1 = log N (to the base 2) 
<vilas_m> : So n = log N + 1
<vilas_m> : Hence, no. of iterations = log N + 1 
<vilas_m> : So we can tell the for loop runs in O(log N) 
<vilas_m> : Got it?
<ishaan> : yes
<vilas_m> : Yup. That's it :) So that brings us to the end of today's session. 
<vilas_m> : Hope it was helpful guys.