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.

Looking forward to it

Reminder: Contest starts in less than 12 hours!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.Thanks for the feedback, glad you liked the contest ^_^

Can we solve

Tree of candlesby 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 2

And overlap are :

Overlaps1,10

2,16

3,10

4,9

5,9

codeIt 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,

My order is: 1 4 5 2 3

Code for reference.

Team Upis actually much easier to do with merging small to large :)Split permutationalso 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.

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 ?

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

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!

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

Can anybody please guide how to perform the 3rd kind of operation for the

Team Upproblem.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.

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.

Example1 2 3 4 5 6

2 1 3 5 6 4

start 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.

Codei found this confusing rather this we can also do that by finding the maximum and minimum till a particular index if they are equal then we have found one answer

ok

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.

ok thanks

When will the prizes be processed?

ujjwald7 might be in better position to answer this!