Invitation to SpyBits, Udyam'21 - IIT (BHU) Varanasi (Rated for Div. 2 & Div. 3)

announcement
1

Greetings Coders,
We would like to invite all of you to the SpyBits CP Round 2021, under the banner of Udyam’21, IIT (BHU) Varanasi.

Udyam is the annual technical fest of the Department of Electronics Engineering, Indian Institute of Technology (BHU), Varanasi organized from Apr 15-18, 2021.

The CP round of SpyBits is a hugely anticipated annual affair now, entering it’s 11th edition under different names and forms. It will take place on April 15th from 9:00 PM - 11:30 PM IST.

We would like to thank our Title Sponsors, CoinSwitch Kuber, and the Event Sponsors, Silence Laboratories.

Click here to go to the contest page.

The Problem Set has been prepared by Ashish Vishal, Daksh Garg and me, Aditya Kumar Singh

We would like to thank Jatin Yadav, Istvan Nagy, Daanish Mahajan , Shikhar Sharma, Achintya Kulshrestha and Ronit Raj for their support in testing and preparation of this contest.

spybits1
spybits11753×2480 666 KB

Participants will have 2.5 hours to solve 7 problems. The scoring will be ICPC style. The contest will be rated for Div. 2 and Div. 3 participants, but even so, has some hugely exciting problems for everyone!

Prizes!
Merit Certificates shall be awarded for the Global Top 15 as well as Top 5 Indian participants

Good Luck everyone! Hope to see you on the leaderboard.

UPDATE
Click below to open EDITORIALS:
SAVE WATER
Valentine Couple
MISSION GOTHAM
PILGRIMS DESTINATION
MINIMUM OPERATION
STONE LAND
MAXPOOL
SOLVE IT

26 Likes
2
3

Update: There will be 8 problems in the contest.
Reminder: The contest is about to begin in an hour.

1 Like
4

Will the problems be sorted by difficulty?

2 Likes
5

great problems

2 Likes
6

Any idea why is this code giving a RTE ?
PS: I’ve used sparse table for finding range max.

7

Great contest! I spent over an hour solving the 5th problem (about piles) and solving the harder version where i does not have to be less than j for j to be seen. I literally had a heart attack after 5 WA, in the end I ended up just subtracting the “harder” thing and submitting my code in the last 2 minutes. Thanks for the problems, but I had to die to hit top 20 Div2 in the last 2 minutes…

Jokes aside, a great problemset for sure! :slight_smile: Kudos to the authors!

2 Likes
8

Great Contest. For the Prilgrims problem, I created the graph first by the weights be k*D as given. Then I applied dijkstra and recorded all distances to special cities and then calculated max special cities which can be filled. Is this the correct approach ? I dont know if my code has bug, it didn’t passed. Can someone correct me ?

Code Link

9

My last submission is not included in ranklist. @adikr_singh , please look into this.

1 Like
10

The ranklist is not updated. I managed to solve 6 problems but it is not reflected in the ranklist.( shows 5 problems solved)
@adikr_singh please look into it.

Btw ,GREAT problemset.
Enjoyed solving them.

11

Can Stone Land question be done using offline queries??

Link to my Code:

https://www.codechef.com/viewsolution/45072214

Please see solve function…

12

Did you consider corner case

1
2 4
190 20 10 50
1 2 10

Correct answer = 1
Sadly, I missed this one :frowning:

2 Likes
13

@admin @adikr_singh Please make problems available for practice :slight_smile:

1 Like
14

You don’t need dijkstra for this

15

Even i solved the harder version at first :cry: and got one WA…
Then saw the condition j > i and fixed it… :sweat_smile:

16

sad missed this. :slight_smile:

17

any other approaches ?

18

If this code looks familiar, then I can feel your pain:

CODE 
#include <bits/stdc++.h>
using namespace std;

int t, n, m;
int ar[100005];
int tree[400005];
int suff[100005];
int pref[100005];
int next_t[100005];
int prev_t[100005];
int next_e[100005];
int prev_e[100005];
stack<int> st;

void build(int v, int tl, int tr) {
	if (tl == tr) {
		tree[v] = tl;
		return;
	}
	int tm = (tl + tr) / 2;
	build(2 * v, tl, tm);
	build(2 * v + 1, tm + 1, tr);
	if (ar[tree[2 * v]] > ar[tree[2 * v + 1]]) tree[v] = tree[2 * v];
	else tree[v] = tree[2 * v + 1];
}

int query(int v, int tl, int tr, int l, int r) {
	if (l <= tl && tr <= r) return tree[v];
	if (r < tl || l > tr) return -1;
	int tm = (tl + tr) / 2;
	int a = query(2 * v, tl, tm, l, r);
	int b = query(2 * v + 1, tm + 1, tr, l, r);
	if (b == -1 || ar[a] > ar[b]) return a;
	else return b;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> t;
	while (t--) {
		cin >> n >> m;
		for (int i = 0; i < n; i++) {
			cin >> ar[i];
			next_t[i] = -1;
			prev_t[i] = -1;
			next_e[i] = -1;
			prev_e[i] = -1;
			suff[i] = 0;
			pref[i] = 0;
		}
		build(1, 0, n - 1);
		for (int i = 0; i < n; i++) {
			while (!st.empty() && ar[st.top()] < ar[i]) {
				next_t[st.top()] = i;
				st.pop();
			}
			st.push(i);
		}
		while (!st.empty()) st.pop();
		for (int i = n - 1; i >= 0; i--) {
			while (!st.empty() && ar[st.top()] < ar[i]) {
				prev_t[st.top()] = i;
				st.pop();
			}
			st.push(i);
		}
		while (!st.empty()) st.pop();
		for (int i = 0; i < n; i++) {
			while (!st.empty() && ar[st.top()] <= ar[i]) {
				next_e[st.top()] = i;
				st.pop();
			}
			st.push(i);
		}
		while (!st.empty()) st.pop();
		for (int i = n - 1; i >= 0; i--) {
			while (!st.empty() && ar[st.top()] <= ar[i]) {
				prev_e[st.top()] = i;
				st.pop();
			}
			st.push(i);
		}
		while (!st.empty()) st.pop();
		for (int i = 0; i < n; i++) {
			if (prev_t[i] == -1) pref[i] += 0;
			else pref[i] += 1 + pref[prev_t[i]];
		}
		for (int i = n - 1; i >= 0; i--) {
			if (next_t[i] == -1) suff[i] += 0;
			else suff[i] += 1 + suff[next_t[i]];
		}
		while (m--) {
			int l, r; cin >> l >> r;
			int res = 0;
			int ind = query(1, 0, n - 1, min(l - 1, r - 1), max(l - 1, r - 1));
			cout << suff[ind] << '\n';
		}
	}
}

:slightly_smiling_face:

BTW this is the fixed version, I had no time to erase the unnecessary details of finding the left side, etc… But the important part is fixed. :smiley:

1 Like
19

Thanks for reporting. It is updated now. Can you please confirm?
Apologies for the issue.

20

You can use the property that trees don’t have cycles to your advantage.
This should give a fair idea.

CODE 
int n,m ,a[mxN],d[mxN];
vt<ar<int,2>>adj[mxN] ;
vt<int>sp,e ;
void dfs(int v,int p){
	EACH(y,adj[v]){
		int x = y[1] ;
		if(x==p)
			continue  ;
		d[x]=d[v]+1 ;
		a[x]=a[v]+d[x]*y[0] ;
		if(sz(adj[x])==1)
			sp.pb(x)  ;
		dfs(x,v) ;
	}
}
void solve(){
	read(n,m) ;
	FOR(m){
		int x ;read(x) ;
		e.pb(x) ;
	}
	FOR(n-1){
		int x,y,z;read(x,y,z)  ;
		adj[x].pb({z,y}) ;
		adj[y].pb({z,x}) ;
	}
	dfs(1,0) ;
	sort(all(sp),[&](const int &i,const int &j){
		return a[i]<a[j] ;
	}) ;
	multiset<int>b(all(e)) ;
	int ans =0 ;
	EACH(x,sp){
		auto it = b.lower_bound(a[x]) ;
		if(it==b.end())
			break ;
		ans++ ;
		b.erase(it) ;
	}
	print(ans) ;
	mems(d,0) ;
	mems(a,0) ;
	sp.clear() ;
	e.clear() ;
	FOR(i,n+2)
		adj[i].clear() ;
}