shubhamgoyal__'s blog

By shubhamgoyal__, history, 6 years ago, In English

Hello Codeforces Community!!!

I invite you all to take part in HackerEarth's January Easy contest.The contest will be held on 1st January,2018 at 22:00 IST.

Problems have been set by me(shubhamgoyal__) and tested by MiteshAgrawal.We are grateful to HackerEarth admin prat33k for his help.

You will be given 5 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 towards beginners, we hope even experienced problem-solvers find one or two problems to be interesting. The contest is rated and prizes will be awarded to the top 3 beginners(i.e. Programmers with a rating of 1600 or less before the challenge starts).

Good luck and have fun.

UPDATE1: Close to 3 hours left in the contest.

UPDATE2: Contest has started.

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

| Write comment?
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Auto comment: topic has been updated by shubhamgoyal__ (previous revision, new revision, compare).

»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Auto comment: topic has been updated by shubhamgoyal__ (previous revision, new revision, compare).

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by shubhamgoyal__ (previous revision, new revision, compare).

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by shubhamgoyal__ (previous revision, new revision, compare).

»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Really excited for this one !

»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

January Easy' 18 Bro!

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by shubhamgoyal__ (previous revision, new revision, compare).

»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

hope some problems will also be "easy" for beginners !!!

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by shubhamgoyal__ (previous revision, new revision, compare).

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What was the expected solution for Shubham and Subarrays ?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hashing

    Solution

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

      Can you explain a bit more ? How are you making sure (x,y) and (y,x) are same ?

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Suppose hash function for value x returns basex for some base.Then hash value for (x,y) would be basex + basey and hash value for (y,x) would be basey + basex.So you can see both arrays map to the same hash value.

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Is there a particular reason you have chosen 127 and 129 as bases?

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Also, why have we used two bases? Why not hashing using just one, and storing it?

          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            You can choose any base of your choice as long as there are no collisions.The reason for choosing 2 bases is also to prevent collisions.

            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              How do we know whether the collisions will happen or not?

      • »
        »
        »
        »
        6 years ago, # ^ |
        Rev. 4   Vote: I like it 0 Vote: I do not like it

        I got 100 points even without using hash , tests are very weak. For the hash solution , just rolling hash this string (see code) for avoid mle =) if they are the same, they hash value will be the same.

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

In Shubham and tree — 1

How can answer for distinct costs can be zero for any node???

»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I have a question that how many people will get T-Shirt? Only 3 or 100 people. actually I am new on hackerearth and only did this contest and ranked 80. can I got T-Shirt?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Hi,

    We provide T-Shirts to the first 5 eligible participants. Better luck next time :)

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I guess I overkilled C with persistent trie.

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

    Can you explain how did you solve using persistent trie ?

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      Sure.

      For every index i, maintain a trie which has all the possible subarray sums in a[1..i]. Again iterate over i, and select j <= i. You have to find the value in the trie till j — 1 which gives maximum xor value with . Do it for all 1 < j <= i.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do C??

»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Really bad issue with test cases, hoping for rejudging. First time that I won a contest. : )

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We are looking into the matter.We will update everyone soon.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi,

    We have rejudged the required submissions. We apologise if you faced any issue. Congratulations for the first rank :)