Блог пользователя jeal0uspengu1n

Автор jeal0uspengu1n, 15 месяцев назад, По-английски

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
  • Проголосовать: не нравится

»
15 месяцев назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

Looking forward to it

»
15 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Reminder: Contest starts in less than 12 hours!

»
15 месяцев назад, # |
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.

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    15 месяцев назад, # ^ |
    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 order

    And overlap are :

    Overlaps
    code

    It gave me runtime error :( pls help

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится 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

      Code for reference.

  • »
    »
    15 месяцев назад, # ^ |
    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.

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      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 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        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 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          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 месяцев назад, # ^ |
              Проголосовать: нравится +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 :(

            • »
              »
              »
              »
              »
              »
              »
              15 месяцев назад, # ^ |
              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 ?

              • »
                »
                »
                »
                »
                »
                »
                »
                15 месяцев назад, # ^ |
                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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  15 месяцев назад, # ^ |
                    Проголосовать: нравится +3 Проголосовать: не нравится

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  14 месяцев назад, # ^ |
                    Проголосовать: нравится 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

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
15 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

a good contest of mixed topics

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +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.

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

hints needed for problem Split Permutation

  • »
    »
    15 месяцев назад, # ^ |
    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.

    Example
    Code
  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 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.

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When will the prizes be processed?