jeal0uspengu1n's blog

By jeal0uspengu1n, 15 months ago, In English

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.

  • Vote: I like it
  • +23
  • Vote: I do not like it

| Write comment?
»
15 months ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

Looking forward to it

»
15 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Reminder: Contest starts in less than 12 hours!

»
15 months ago, # |
Rev. 4   Vote: I like it +23 Vote: I do not like it

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.

  • »
    »
    15 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    15 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    It gave me runtime error :( pls help

    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    15 months ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    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.

    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      1. I think DSU uses small-to-large merging approach in the background.

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

      • »
        »
        »
        »
        15 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        1. I mean if you're using small to large — you don't need any additional tricks and problem become very straightforward.
        2. Are you sure it can be done with prefix sums? Because I had another approach in mind.
        • »
          »
          »
          »
          »
          15 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          1. Ah cool, during the contest I thought that would tle.

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

          • »
            »
            »
            »
            »
            »
            15 months ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            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 :(

            • »
              »
              »
              »
              »
              »
              »
              15 months ago, # ^ |
              Rev. 2   Vote: I like it +3 Vote: I do not like it

              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 ?

              • »
                »
                »
                »
                »
                »
                »
                »
                15 months ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it

                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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  15 months ago, # ^ |
                    Vote: I like it +3 Vote: I do not like it

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  14 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
15 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

a good contest of mixed topics

  • »
    »
    15 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

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

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hints needed for problem Split Permutation

  • »
    »
    15 months ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    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
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

When will the prizes be processed?