Invitation to HackerEarth's January Easy '23

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

Hello Codeforces!

A very happy new year to everyone ＼(＾▽＾)／

I would like to invite you to take part in HackerEarth's January Easy '23! It will be held on Saturday, January 7, 2023 at 9:30 AM IST.

The problems were written and tested by me (Sutej jeal0uspengu1n Sharma), Priyanshu Bit_Megumi Verma, Rohit rohit_768_ Pradhan, Ramgopal grayhathacker Pandey, Nitil ARPlT Mohanty and Rajan rajan2k Keshari.

Also many thanks to Ujjwal ujjwald7 Dwivedi for coordinating the contest.

You will be given 6 algorithmic problems to solve in 3 hours. Partial scoring will be used (i.e. you get points for passing each test case).

Although the contest is targeted toward beginners, we hope that everyone finds the tasks interesting. The contest is rated for all and the prizes will be awarded to the top 3 beginners (i.e. participants with a rating less than 1600 before the challenge starts):

First place: $75 Amazon gift card.
Second place: $50 Amazon gift card.
Third place: $25 Amazon gift card.

Good luck everyone, and feel free to discuss the problems here when the contest ends.

Comments (23)

Show archived | Write comment?

C_plusplus

2 years ago, # |

← Rev. 2 →

Looking forward to it

→ Reply

jeal0uspengu1n

Reminder: Contest starts in less than 12 hours!

vrintle

← Rev. 4 →

+23

It was an amazing round, I enjoyed it and got to learn few things, thanks to the authors. Here is my feedback on the problems:

Fruit Slicing: Easy problem, use of sets.

Replace X: Easy greedy problem, just find a number x and calculate y based on it.

Team Up: Amazing disjoint-sets problem. I used a trick in which I used N extra heads in dsu and initialized the pointers as i to (i + N). So, now we don't have to care for those nodes which points to node a in type-3 query.

Split permutation: Nice dsu problem again (bit annoying too?). It can be easily solved with dsu and 2 pointers. But, I didn't noticed that numbers can be negative, which gave me 7 penalties :(

Tree of candles: Nice dijkstra problem. I used a greedy idea to remove those nodes which will burn for longer time, and suddenly I realized that it is dijkstra.

Optimal moves: Nice dp problem. The first operation is easy to handle, but not the second one, if we think of the second operation in reverse way, like for every j what possibilities of i's we have, then we see that it's basically a segment of the array, so we can use RMQ here.

2 years ago, # ^ |

Thanks for the feedback, glad you liked the contest ^⁠_⁠^

inceptionabhi

Can we solve Tree of candles by first sorting the values on the basis of their candle time (by decreasing order) and then manually check if we try to assign this ( before that we also need to check whether all the ancestors are already assigned or not, it not we do dfs to first assign them and then assign the resultant value to the current node). From my code we will visit nodes in this way :

Nodes Visit order

And overlap are :

Overlaps

code

const int MAXN = 1e5;
int n;
int a[MAXN];
vector<int>adj[MAXN];
int parent[MAXN];
bool visited[MAXN];
map<int,int> order;
vector<int> curr;
void dfs(int node){
	if(visited[node]){
		return;
	}
	if(parent[node]==-1){
		visited[node]=true;
		curr.pb(node);
		return;
	}
	visited[node]=true;
	curr.pb(node);
	dfs(parent[node]);
}
void solved(){
	cin >> n;
	vector<pair<int,int>> vals;
	for(int i=1;i<=n;i++){
		cin >> a[i];
		vals.pb(mp(a[i],i));
	}
	parent[1]=-1;
	int edges=n-1;
	set<int>found;
	while(edges--){
		int u,v;
		cin >> u >> v;
		if(u==1 || v==1){
			if(u==1){
				parent[v]=u;
			}else{
				parent[u]=v;
			}
			found.insert(u);
			found.insert(v);
		}else{
			if(found.count(u)){
				parent[v]=u;
			}else{
				parent[u]=v;
			}
			found.insert(u);
			found.insert(v);
		}
		adj[u].pb(v);
		adj[v].pb(u);
	}
	// for(int i=1;i<=n;i++){
	// 	cout << i << ' ' << parent[i] << endl;
	// }
	sort(all(vals));
	reverse(all(vals));
	//deb(vals);
	int currorder=1;
	vector<pair<int,int>> overlap;
	for(int i=0;i<vals.size();i++){
		if(!visited[vals[i].ss]){
			dfs(vals[i].ss);
			reverse(all(curr));
			//deb(curr);
			for(int j=0;j<curr.size();j++){
				overlap.pb(mp(currorder,currorder+a[curr[j]]-1));
				currorder++;
			}
			curr.clear();
		}
	}
	// deb(order);
	// deb(overlap);
 
	int ans=0;
	for(int i=overlap[overlap.size()-1].ff;i<=overlap[overlap.size()-1].ss;i++){
		ans ++;
	}
	cout << ans << endl;
 
}

It gave me runtime error :( pls help

I used a similar greedy idea but instead of dfs, I did bfs-like traversal but using a priority-queue so that I always take out the maximum burning time candle. From my understanding of your code, I think that it could fail on a testcase like,

1
5
1 4 15 6 10
1 2
1 4
2 3
4 5

My order is: 1 4 5 2 3

Code for reference.

gultai4ukr

← Rev. 3 →

Team Up is actually much easier to do with merging small to large :)

Split permutation also can be done without DSU :)

Tree of candles: I would not call it dijkstra, it's just greedy on available vertices.

I think DSU uses small-to-large merging approach in the background.
Yeah, I just complicated by bringing in DSU, it can be done with prefix sums, where we will increase answer only when prefix sums are equal for a and b.

I mean if you're using small to large — you don't need any additional tricks and problem become very straightforward.
Are you sure it can be done with prefix sums? Because I had another approach in mind.

Ah cool, during the contest I thought that would tle.
Yes, because for any permutation the sum would be equal, and since the numbers are unique, we can do this. Practice submission, ignore the dsu template.

2. Numbers are unique, but the sums aren't!

Consider example:
1 4 2 3
2 3 1 4
Your solution will return 2 (0-1, 2-3) when it's 1 in fact.

I guess the tests were very weak if this solution passed :(

Lmao, that's actually crazy, I shouldn't believe on HE acceptance ig. But, it's sad to say that this is usual thing on HE. Anyways, what was your approach ?

23 months ago, # ^ |

But, it's sad to say that this is usual thing on HE

Unfortunately, you're right. I am already quite used to huge partial scores for wrong solutions on HE, but full score is really nuts.
FYI jeal0uspengu1n ujjwald7

Anyways, what was your approach ?

Our goal is to find biggest partition of B into segments such that every segment is permutation of corresponding segment of A. Let's call every segment in target partition a good one. I mapped numbers from A to their indices (to have them sorted) and packed into set. Then iterated through B and removed appropriate indices (using the same mapping). On each step $$$i$$$ I checked if the smallest number in set is $$$i+1$$$ (which basically means that we just cleared another good segment ending at $$$i$$$) and if so — added 1 to the answer. In-contest submission.

Will forward the same to the contest admin, thanks to bringing it to light!

ujjwald7

Apologies for the late response. This might have been a miss on my part. Although my solutionn (Tester's solution) uses the same approach you've mentioned here. Will keep this in mind moving forward

Abhishek_Srivastava

Can anybody please guide how to perform the 3rd kind of operation for the Team Up problem.

callback

a good contest of mixed topics

(Toxic answer) Because you haven't sponsored bigger ones.

(MHO) Because such contests are running every month and all expenses are fully covered by HE which doesn't make anything of it except PR and maybe a bit of advertisement. So, say thanks that at least they are.

Shivam14

hints needed for problem Split Permutation

In split permutation, we start with the first element in array A, then we need to find the position of that element in array B (say destination) now, keep traversing till that point and in between you will find the various A elements just keep updating the value of destination as (destination = max(destination, m2[B[i]]) here m2 stores the position of value in array B) while traversing. In this way, we end up covering a segment that contains permutations same in both A and B.

Example

Code

void solve() {
	int n;
	cin >> n;
	vector<int>v1(n),v2(n);
	map<int,int>m1,m2;
	for(int i=0;i<n;i++){
		cin >> v1[i];
		m1[i]=v1[i];
	}
	for(int i=0;i<n;i++){
		cin >> v2[i];
		m2[v2[i]]=i;
	}
	int tot=0;
	
	for(int i=0;i<n;){
		// deb(i);
		// deb(v1[i]);
		int destinations=m2[v1[i]];
		// deb(destinations);
		int j=i;
		for(j=i;j<=destinations;j++){
			//deb(j);
			destinations=max(destinations,m2[v1[j]]);
		}
		// deb(destinations);
		// deb(j);
		i=j;
		tot++;
	}
	cout << tot << endl;
}

llc5pg

Use DSU to assign each element to a root. For the elements in the same root, get the minimum and the maximum element. Treat each root as a 'meeting', the minimum element as the 'start meeting time' and maximum element as the 'end meeting time'. If multiple 'meeting's overlap, then they can be considered as merge as one 'meeting'. Count how many 'meeting's end. That's the answer.

wargang

23 months ago, # |

When will the prizes be processed?

ujjwald7 might be in better position to answer this!

jeal0uspengu1n's blog