Hi everyone,
This is a continuation of the Live DSA learning sessions being conducted as part of the DSA Learning series.
A session would generally be conducted by CodeChef 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 Contest 2, the 2nd session is as follows:
-
Topic: Theory discussion + Live problem solving of 1 - 2 problems of the contest 2 + QnA
-
Brief Description:
Which theory topics would you prefer (Pick at most 3 out of the 4 options)
(Update - The voting will close by 16th April afternoon)
- Dequeue theory + How to solve the following question: Given an array A, print the maximum element of all subarrays of length K ,i.e max(A[1] A[2], …, A[K]), max(A[2], A[3], … , A[K + 1]), max(A[3], A[4], …, A[K + 2]) in O(N)
- Stacks are useful when recursion causes stack limit exceeded, rare use case in Facebook Hacker Cup, etc
- Stacks in ZCO Rectangles (Classic use case of stacks)
- Bracketing questions use stacks
0 voters
From problem solving aspect which problems would you want to be discussed (Pick at most 3):
(Update - The voting will close by 16th April afternoon)
- STFOOD
- PSHOT
- STUPMACH
- COMPILER
- ZCO12001
- INPSTFX
- NOTALLFL
- ZCO12002
- CHFQUEUE
- ZCO15004
0 voters
-
Pre-requisite:
Recommended having gone through the reading material of this week here -
Session volunteer:
Sidhant Bansal -
Date-Time:
11:30 AM IST, 16th April 2020 (Thursday) -
Duration:
1.5 - 2 hours -
Platform for video conferencing:
Zoom Meetings limited 100 seats. Entry to the session on Zoom will be on a first come first serve basis.
Rest of the participants can join live on CodeChef’s YouTube channel . -
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
-
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 admit the participants at 11:30 am IST in the Zoom meeting. Details as follows:
-
Join Zoom Meeting: https://zoom.us/j/92470746261?pwd=bDNieVlGaG1MSU54dWI5QlVjclJFQT09
-
Meeting ID: 924 7074 6261
-
Password: 415179
[Update2] Catch the live stream on YouTube here: Live DSA Learning Session 4 - Contest 2 - Part 2 - YouTube
[Update3] Kindly share your feedback on the session here: https://bit.ly/3bjLcG8
[Update 4]
The Deque theory links: here and here
Deque Sliding Window Code: here
Homework 1 - Try to solve Sliding Window Range Min Query problem in O(NlogN) using sets/maps/priority_queue
Homework 2 - Another approach using Min/Max prefixes and partitioning the array into N/K blocks each of size K exists. Try to understand it from here
Written explanation of ZCO Rectangles (aka SPOJ Histogram / Largest Area Rectangle on x-axis) is here also
[Update 5] I refactored our pseudocode written to slightly simpler idea and below is the code attached which ACs for ZCO15004:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
vector<pair<int, int> > A;
int L[3*N], R[3*N];
int main() {
memset(R, -1, sizeof(R));
memset(L, -1, sizeof(L));
int n, x, y;
cin>>n;
A.push_back({0, 0});
A.push_back({N, 0});
for(int i = 1; i < N; i++) {
A.push_back({i, 500});
}
for(int i = 1; i <= n; i++) {
cin>>x>>y;
A.push_back({x, y});
}
sort(A.begin(), A.end());
stack<int> S;
for(int id = 0; id < A.size(); id++) {
int x = A[id].first, y = A[id].second;
while(!S.empty()) {
if(A[S.top()].second > y) {
R[S.top()] = x;
S.pop();
} else {
break;
}
}
S.push(id);
}
for(int id = A.size() - 1; id >= 0; id--) {
int x = A[id].first, y = A[id].second;
while(!S.empty()) {
if(A[S.top()].second > y) {
L[S.top()] = x;
S.pop();
} else {
break;
}
}
S.push(id);
}
int ans = 0;
for(int id = 0; id < A.size(); id++) {
int x = A[id].first, y = A[id].second;
if(L[id] == -1 or R[id] == -1 or L[id] == x or R[id] == x) continue;
ans = max(ans, (R[id] - L[id]) * y);
}
cout<<ans<<endl;
}