[OFFICIAL] Live DSA Learning Session 1 - Contest 1 - Part 1

Hi everyone,

So in this DSA Learning series, we plan to conduct some live sessions.

A session would generally be conducted by 1-2 volunteers and would be a live discussion (via text + video). The main purpose of these sessions would be to discuss the theory topics and then move on how to go about solving the problems of the contest.

For this week, the 1st session is as follows:

  • Topic:
    Complexity Analysis discussion + Problem discussion of MULTHREE + Problem discussion of ZCO14003

  • Brief Description:
    In complexity analysis we will first define the idea of complexity, then show some basic examples followed by some advanced examples (i.e cases where people sometimes ends up analysing the algorithmic complexity incorrectly).
    After this, we will do problem discussion of MULTHREE + ZCO14003.
    In case we have time leftover we can do a brief generic discussion about IDE setups and some implementation tricks.

  • Pre-requisite:
    None. Recommended going through the reading material of complexity analysis provided here. Also expect you guys to have read the two problems (MULTHREE + ZCO14003) beforehand.

  • Session volunteer:
    Sidhant Bansal

  • Date-Time:
    11 AM IST, 4th April 2020 (Saturday)

  • Duration:
    2-2.5 hours

  • Platform for video conferencing:
    Zoom Meetings

  • To register:
    If you are interested just register by clicking on the Going button below the topic title at the top and Add it to your Calendar for a reminder so that you don’t miss it :slight_smile:

  • Note from CodeChef:
    — These sessions are hosted by our volunteers. Kindly respect their efforts and time.
    — In case of any doubts, please post in the comments.

[Update1] We will be sending Zoom meeting details via message on your Discuss profile (Messages can be accessed in the top right corner profile dropdown) to all those who have signed up as going in the event.

[Update2] There is a limit of 100 participants in the Zoom meeting. In case you are unable to join then you can catch us live on our official channel on YouTube here: https://www.youtube.com/watch?v=c_wUBeeJV9U

[Update3] We have stopped registrations as the session has started. Please join the YouTube stream using the link above.

[Update4] Rate the session and share your experience and feedback in the comments below.

  • 1 Very Bad
  • 2 Bad
  • 3 Average
  • 4 Good
  • 5 Very Good

0 voters

[Update5] Find the live streaming of the session here: https://youtu.be/c_wUBeeJV9U. Apologies for missing to record the initial few minutes of the session.

[Update 6]
The questions discussed from the text file were as follows:
Q5, Q7, Q11, Q12, Q13(hard), Q17(hard), Q20 (from here)

Q1.
Given complexity N + N/2 + N/3 + N/4 + N/5 + ... + N/N = ?

for(int i = 1; i <= n; i++) {
	for(int j = i; j <= n; j += i) { 
		cout<<"HAHA"<<endl;
	}
}

Q2.

bool is_composite[N];
vector<int> primes;

int main() { // sieve of eratosthenes: to list all primes <= n
	memset(is_composite, 0, sizeof(is_composite)); // what if remove this, does this code still work?

	for(int i = 2; i <= n; i++) {
		if(is_composite[i])	continue;
			primes.push_back(i);
			for(int j = i; j <= n; j += i) {
				is_composite[j] = 1;
			}
	}
	// how slow ??
}

Q3.

const int N = 100, LOGN = 8;
int total = 0;

bool is_bit_on(int x, int pos) {
  return ((x & (1 << pos)) != 0);
}

void flip_bit(int &x, int pos) {
  x ^= (1 << pos);
}

void increment(int &x) {
  for(int i = 0; i < LOGN; i++) {
  	total++;
    if(is_bit_on(x, i) == 1) {
      flip_bit(x, i);
    } else {
      flip_bit(x, i);
      break;
    }
  }
}

int main() {
  int counter = 0;
  for(int i = 1; i < N; i++) {
    increment(counter);
  }
  // how slow?
}

Q4. \{\lfloor\frac{N}{1}\rfloor, \lfloor\frac{N}{2}\rfloor, \lfloor\frac{N}{3}\rfloor, ..., \lfloor\frac{N}{N}\rfloor\}, how many distinct values does this set have?

a) \log{N}
b) \sqrt{N}
c) N
d) log{N} * log{N}
e) None of the above

Q5. Given \sum_{i = 1}^{N}K_i <= 10^5, find the maximum number of times K_i > \sqrt{10^5} ?
[Not discussed, Homework]

Q6. f(N) = \sqrt{N} and f^x(n) = f(f(f(... \text{x times }(n))))
[Used in analysis of square root tree, see here]
[Not discussed, Homework]
Then find x, such that f^x(N) = 2

a) \log{N}
b) \log{\log{N}}
c) \sqrt{N}
d) none of the above

18 Likes

Really appreciate what you guys are doing. Just wanted to ask if we will be covering implementation and greedy in this webinar or is that going to be covered afterwards?

1 Like

How we get the link of zoom live session ?

Hi,

So we will be covering the implementation of the problems mentioned.

I don’t think any of the problems mentioned for this session involve greedy algorithms and as such the topic of greedy algorithms will be covered in the latter weeks, so you should consider that greedy algorithms wont be covered in this session.

2 Likes

We will be sending it via message on discuss (Can be accessed in the top right corner profile dropdown) to all those who have signed up as going in the event.

Hey, I have just opted by Going can I get the Zoom link too?

marked As going still no message recieved.

Can we attempt any questions in any week. Or it will be closed after 1 week i.e the first round?

1 Like

You can attempt the questions later also. It will be open after one week.

Great.Thank you.
Will they be shown in the ranklist too?

Yes. Though it is only a practice contest. No prizes involved here.

Yes, yes no issues.

Great effort and very well done, thank you for answering all our questions, and explaining the topics using your prepared questions, and opening up topics for us to study, God bless you and all the CodeChef team. This series and the way you are doing it, with a forum, hints, editorials, and live streams is seriously igniting the fire for CP again for me ( i am a “returning” programmer), it is a dream come true to me.

Deeply grateful…:slight_smile:

2 Likes

Thanks a lot sidhant007 for the great explanation and walkthrough of the problems.

3 Likes

Very nice initiative and lec was very good

The lecture was really good. I had recently studied more about sums.
If one wants to study how harmonic series converges to log n, check out these


From around 45 minutes, he starts with integration bounds where he explains how to integrate such expressions so as to find an approx sum.
2 Likes

@sidhant007 you talked about some better editors and compilers to work with. Could you mention them?

Just for the sake of completeness and helping my fellow buddies. Answer to Q-5 and Q6 are:

a

b

let me know if i am wrong somewhere.:blush::blush:

4 Likes

Umm, sure. So the ones I recommended are Vim, Gedit, Nano, Emacs. Out of these if you look up on the net most productive ones are generally said to be Vim/Emacs. Along with this one would need to get comfortable in terminal and use g++/gcc from terminal along with basic file redirection and piping.

1 Like