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

Автор shubhamgoyal__, история, 7 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +59
  • Проголосовать: не нравится

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

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

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

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

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

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

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

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

»
7 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Really excited for this one !

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

January Easy' 18 Bro!

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

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

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

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

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

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

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

What was the expected solution for Shubham and Subarrays ?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Hashing

    Solution

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

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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.

      • »
        »
        »
        »
        7 лет назад, # ^ |
        Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

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

In Shubham and tree — 1

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

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

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?

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

I guess I overkilled C with persistent trie.

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

    Can you explain how did you solve using persistent trie ?

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

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

How to do C??

»
7 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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