madlogic's blog

By madlogic, 10 days ago, In English

Hi Codeforces!

I would like to invite you to participate in HackerEarth's August Easy '22. It will be held on Saturday, Aug 6 at 9:30AM IST.

The problems were written and tested by Me (Chibuoyim madlogic Ogbonna), Wesam Wesam Naseer, Yatin nit_ay03 Kwatra, Rohit rohit_768_ Pradhan, Andreas Rasvanis, Pawankumar Nandagiri, and Divyam Agarwal. 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 (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
  • +13
  • Vote: I do not like it

»
9 days ago, # |
  Vote: I like it -6 Vote: I do not like it

how can I contribute in hackerearth?

»
8 days ago, # |
  Vote: I like it -6 Vote: I do not like it

Totally Love the contest, all problems are really good and intuitive.(got 16 rank lol)

One Room to another was little bit confusing for me.

can you correct me on this? (all nodes should be in cycle and return smallest cycle length)?

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes! the question was to find such a value K so that for each node after K steps it returns back to that node. And the answer would be -1 only if any values repeat otherwise it is just the lcm of all the cycle lengths.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      still doesn't get that? how the LCM comes in it?

      my code
      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        LCM will give you the smallest K such that from all nodes after exactly K steps you come back to that node. For example — [2,3,1,5,6,7,4] In this case, there are two cycles 1. 2->3->1->2 (cycle length — 3) 2. 5->6->7->4->5 (cycle length — 4) now the LCM(3,4) = 12 which means that from each node if you perform 12 steps you will return back to that node. LCM is because we need to find the smallest common multiple of each cycle length.

        • »
          »
          »
          »
          »
          8 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          dumb ass me :( i did almost correct just didn't took the LCM because i thought they asking for smallest cycle length

»
8 days ago, # |
  Vote: I like it +21 Vote: I do not like it

Could you please rectify the test cases for one room to another. People have taken lcm by taking mod at each step and then taking lcm which is incorrect. The correct approach was to calculate the lcm and then its mod.

Winner sol: https://www.hackerearth.com/challenges/competitive/august-easy-22/algorithm/smallest-trip-length-c5309d9f/submission/73879142/

My sol: https://www.hackerearth.com/challenges/competitive/august-easy-22/algorithm/smallest-trip-length-c5309d9f/submission/73880121/

For reference: lets say there are 3 cycles of length 3,4 and 4 and suppose modulo is taken with 5 we get lcm(3,4,4)=12 which modulo 5 gives 2 whereas when taking modulo on the fly lcm(3,4) = 12 which modulo 5 gives 2 then lcm(2,4) = 4 which modulo 5 gives 4, which is incorrect.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    loss of some dollars :(

  • »
    »
    8 days ago, # ^ |
    Rev. 3   Vote: I like it +11 Vote: I do not like it

    Yes, exactly I was doing the same thing. I was storing the max count of all prime factors from the divisors of cycle lengths and then calculating the LCM which is now just the multiplication of all the prime factors (max count times).

    For example-> cycle lengths are [12,14,18] I calculated all prime factors of each element 12 -> ({2,2},{3,1}), 14 -> ({2,1},{7,1}), 18 -> ({2,1},{3,2})

    now the lcm would be (2 ^ (max({2,1,1}) * 3 ^ (max({1,2})) * 7 ^ (max({1}))) % (1000000007) but this was giving WA just because answers were calculated in a wrong way.

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Apologies for the inconvenience caused. Will get this fixed and the solutions rejudged.

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

Bracket tree is exactly this codechef problem. Wish I had searched it online during the contest.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    otherwise u'll be 3rd

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How are they the exact same thing? In the problem you linked the brackets are on the nodes, while in bracket tree the brackets are on the edges and the tree is rooted at node 1.

    Yes, they are similar but they are not exactly the same.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there gonna be a September Easy also? I don't use HackerEarth very much, hence unaware of the competitions that happen there.

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

    Yes,there will a September Easy. We usually have 3 contests in month i.e. Easy, DSA and Circuits. Easy and DSA take place on the first and second Saturday of every month. Circuits is a long contest starting on the 3rd Friday of every month.