jeal0uspengu1n's blog

By jeal0uspengu1n, 19 months ago,

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.

• +23

| Write comment?
 » 19 months ago, # | ← Rev. 2 →   +2 Looking forward to it
 » 19 months ago, # |   +8 Reminder: Contest starts in less than 12 hours!
 » 19 months ago, # | ← 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.
•  » » 19 months ago, # ^ |   +8 Thanks for the feedback, glad you liked the contest ^⁠_⁠^
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 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 order1 3 4 5 2And overlap are : Overlaps1,10 2,16 3,10 4,9 5,9 codeconst int MAXN = 1e5; int n; int a[MAXN]; vectoradj[MAXN]; int parent[MAXN]; bool visited[MAXN]; map order; vector 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> vals; for(int i=1;i<=n;i++){ cin >> a[i]; vals.pb(mp(a[i],i)); } parent[1]=-1; int edges=n-1; setfound; 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> overlap; for(int i=0;i
•  » » » 19 months ago, # ^ |   0 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
•  » » 19 months ago, # ^ | ← Rev. 3 →   +1 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.
•  » » » 19 months ago, # ^ |   +1 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.
•  » » » » 19 months ago, # ^ |   0 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.
•  » » » » » 19 months ago, # ^ |   0 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.
•  » » » » » » 19 months ago, # ^ |   +8 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 :(
•  » » » » » » » 19 months ago, # ^ | ← Rev. 2 →   +3 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 ?
•  » » » » » » » » 19 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » » » » » 19 months ago, # ^ |   +3 Will forward the same to the contest admin, thanks to bringing it to light!
•  » » » » » » » » » 18 months ago, # ^ |   0 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
 » 19 months ago, # |   0 Can anybody please guide how to perform the 3rd kind of operation for the Team Up problem.
 » 19 months ago, # | ← Rev. 2 →   0 a good contest of mixed topics
•  » » 19 months ago, # ^ |   +9 (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.
 » 19 months ago, # |   0 hints needed for problem Split Permutation
•  » » 19 months ago, # ^ | ← Rev. 2 →   +7 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. Example1 2 3 4 5 6 2 1 3 5 6 4start with 1(in A) then find position of 1 in B(which is 1th index) so go till that index in A(you will find at index 1,A[i]=2 then find the position of 2 in B (which is 0 less that the current destination(1)). So, we covered one segment so increase the answer.Now do the same for rest of the elements. Codevoid solve() { int n; cin >> n; vectorv1(n),v2(n); mapm1,m2; for(int i=0;i> v1[i]; m1[i]=v1[i]; } for(int i=0;i> v2[i]; m2[v2[i]]=i; } int tot=0; for(int i=0;i
•  » » 19 months ago, # ^ |   0 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.
 » 19 months ago, # |   0 When will the prizes be processed?
•  » » 19 months ago, # ^ |   0 ujjwald7 might be in better position to answer this!