shashank21j's blog

[HackerRank] CounterCode on 1st August / Awesome Prizes
By shashank21j, history, 9 years ago, In English

Hello CodeForces Community!

I am glad to share that HackerRank's CounterCode (CodeSprint on Algorithmic Programming Challenges) is scheduled on 1st-August-2015 at 16:00 UTC.

Go ahead and register now at www.hackerrank.com/countercode to show off your coding chops, and win amazing prizes like Apple iPhone 6, Sony PS4, Bose Headphones, Fitbit Charge, WD 1 TB HardDisk and HackerRank t-shirts!.

All participants who completely solve one challenge (that’s just 1 out of 8 questions!) will get $100 of AWS credits.

Also, you'll get an opportunity to connect for a career opportunity with CounterCode contest sponsors — Asana, Blippar, LaunchCode, Marketo and Verizon.

Contest will be rated, scoring is 20 — 30 — 50 — 70 — 100 — 120 — 140 — 150. Tiebreaker is person to reach the score.

Editorials will be live soon after the contest ends, I invite everyone from experts to beginners to participate and solve challenges. This is going to be a really awesome contest :)

GL&HF

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

Comments Comments (64)
| Write comment?
»
9 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Start of CounterCode conflicts with SRM 664. 2 hours shift would be great.

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

    Two hours sooner will be fine, but two hours later will be a problem for me because of timezone.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Date and time are decided by marketing team 1 month in advance, and specially when sponsors are involved this happens with their consent.

    We follow the calendar https://www.hackerrank.com/calendar and when we listed SRM didn't so the time of contest will not change.

    Anyways it's a 24h contest, you can possibly join later.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I phone6 *_*

→ Reply
»
9 years ago, # |
  Vote: I like it +11 Vote: I do not like it

August Easy, SRM 664 and CounterCode all begin on the same time! If you could shift this contest for about 2 hours or more, it'll be highly appreciated. We are humans after all:P

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Tiebreaker is person to reach the score

What does it mean? Google Code Jam-style: penalty is the time of last submission that changed score, is it correct? There is no penalty for incorrect submissions, is it true?

Will there be instant feedback, like in old challenges practice?

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

    Yes codejam style, Time of last submission that increased score is taken into account.
    No penalty for incorrect submission Full feedback for every submission (no hidden testcase and no rejudging later on hidden tests)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -11 Vote: I do not like it

      This rule-set makes the contest even more interesting :)

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +27 Vote: I do not like it

        I'd say this ruleset makes duration of 24h pointless.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          ← Rev. 2   Vote: I like it +8 Vote: I do not like it

          Not necessarily. HR doesn't have subtasks / batch tests — each input file is scored independently, so if there's a challenge-type problem (non-binary scoring of each test or just solvable using heuristics etc), then it could be a decent tiebreaker. It depends on the setters/testers.

          Time should not be a tiebreaker in 24h contests, anyway.

          UPD: It was done the exact opposite way, the last 2 problems had no partial scoring...

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

            Unfortunately, "tiebreaker is first person to reach score"

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
                Vote: I like it +8 Vote: I do not like it

              I understood it as tiebreaker in case of getting equal points. Obviously, the main tiebreaker must be the scored points.

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

      Last submission time or last submission time — open time, like weekly challenges?

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

May I have a list of problem setters in advance :)

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What about time and memory limits? I've looked through old contests and found out that there are no information about them at all. There is 'environment' page with TLs specified, which are bullshit: I've tried one problem and my C++ submission got terminated in 1 second, not 2 seconds. I've asked support week ago and their answer was:

However, looks like a lot of people have solved this challenge successfully. Please refer to the editorial section of the challenge for the suggestions / solutions.

Old ACM-ICPC style? Your program should terminate in a reasonable amount of time and you can expect reasonable amount of test cases in a single input?

→ Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Looking at the scoreboard now, 24 hours definitely were too much for the top competitors. There are already several highscores and with small (20 minutes between the top 2 places) time differences.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    The contest isn't just about the prizes, there's also the other 99% of the scoreboard. Also, everyone is asleep now, it looks like you might need to solve the 140 or 150 for a t-shirt, and people will solve it in the morning, so 24h makes sense. Now stop complaining and continue coding, you still have a chance to grab the HD before tourist wakes up.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Hard Disk claimed by yeputons :D congrats!

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

      The contest isn't just about the prizes

      Lol I didn't say anything about prizes :D. It's that I tend to connect 24h contests with (me) actually needing those 24 hours (or 24- hours) of effort, but only the last problem needed non-negligible thinking time.

      Oh well. Here's my solution of that last problem:

      • introductory tree classic: 2^k-th and K-th (for some K) ancestor of each vertex, depths, sums from the root (vertex 1) everywhere; we're able to find LCAs

      • in order to avoid doubles, we want to check if the sum from A to X — T*(the distance of A and X) > 0 somewhere

      • the limits allow solutions comfortably and an additional log-factor with possible optimisation; we can split the path into O(N / K) pieces from A up to the L = LCA(A, B) and O(N / K) from B up to L and process each piece somehow, then bruteforce a small (O(K) vertices) path containing L

      • so we always have some vertex, take the paths up from it with length 0..K - 1 edges (if it's the part from A to L; if it's from B, we find its K-th ancestor and take paths down from that ancestor to that vertex of length 1..K) and want to know the maximum of (path sum)-T*(path length) for each T — more precisely, if we keep incrementing T, then we want the pair (sum,length) that gives the maximum for each T where this pair changes, which can be done by the "convex hull trick" in

      • when we know those numbers, for given T, we just find the last smaller T where that pair changed and take the max. given by that pair for our given T, so we always move K edges up with cost

      • time complexity now: ; that's too slow, so we only do the convex hull trick thingy for vertices with depth divisible by K and always bruteforce O(K) vertices above A and B until the first vertex with this depth divisible by K; the part with has a small constant now, so we can take K = 300 and add clever breaks and it works :D

      I wasted some time thinking if it's possible to solve it faster, got some good ideas, but they only worked for simpler variations of the problem. In the end, Method Lumberjack (cut till it falls) worked well... I wonder if there's a fast solution. And I used another sqrt-decomposition in Subset, too.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it +1 Vote: I do not like it

        My solution is O(N * log2(N)). I used heavy-light and convex hull trick on segment tree.

        Edit : Editorial uses the same idea.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it -7 Vote: I do not like it

          Oh... of course. I didn't try to improve the idea with convex hull trick...

          But my approach seems simpler! :D (one less HLD)

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it +22 Vote: I do not like it

            As I remember you said, "HLD is just a dfs" but SQRT-Decomposition is SQRT-Decomposition :D

            http://codeforces.net/blog/entry/17401?#comment-222355

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
                Vote: I like it -8 Vote: I do not like it

              Yes, HLD is pretty simple as well and there isn't far from moving up sqrt-paths to moving up HLD-paths, but this sqrt-decomposition was really just "bruteforce, then a small loop where you pick the right subpath from a map, bruteforce again" — still a bit simpler. Convex hull trick is the whole bulk of the idea (about 90% of my effort went to it... why when I wrote it correctly easily a week+ ago?).

              Don't dwell on my lulzpost that obviously exaggerates details :D

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

        ...but only the last problem needed non-negligible thinking time.

        I can't somehow relate to that :D

        → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        I splitted tree in centroids and processed each subtree twice for up and down queries (like in convex hull). My solution is O(NlogN + QlogN). On each query I did binary search by value of T.

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

          Can you give more details or post your code?

          I tried to find a solution using Centroid Decomposition but couldn't.

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            I found that actually my solution is O(Nlog^2N + Qlog N). Actually it do the same as other solutions, but splittes the path from A to B in other way.

            → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can I report cheating requests somewhere, e.g. "send me the code/tests"? I've marked them as spam for now.

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve Subset?

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

    I solved it using two tries. code

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

      Your idea is correct , but you didn't really needed to use trie , arrays are enough

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

      Can you explain little bit about your approach ? I actually used just one tries and got accepted but i feel in worst case i might have to traverse whole tries how did you optimize that using 2 tries ?

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

    I solved it with sqrt-decomposition.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I solve it the using brute force algorithm with some optimization.

    However the correct one used similar technique like http://codeforces.net/contest/348/problem/C.

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

    If number of bits in S less or equals to 8, then add/del takes O(16) time at max, cnt takes O(28) time at max
    If number of bits in S more than 8, then add/del takes O(28) time at max, cnt takes maybe O(214) time at max, maybe I made a mistake in time complexity for this case
    Source

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

    I used a trie: http://pasted.co/175145aa

    The main idea is that you only need to store / remove values < 2^16, this can be easy mantaining a trie with depth of 16.

    For query you need only the last 16 bits of the value, then traverse the trie and if in some level, all the remainding bits of the value to query are 1, you can only return a precalculated value in that node (sum of all nodes down). See the code for more detaills, I guess my implementation was straightforward.

    I really liked solving this one.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      But isn't then the worst case complexity of each query= 2^16?

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

        Yes, it is.

        add/remove works in O(N) where N is the number of bits (16).

        Query has worts case complexity when the value has every bit turned on but the most significant bit off, this only if there are all 2^16 possible values, in average is much faster, there are some tricks to optimize the worst case but this got accepted.

        → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I split the problem for first and second byte of s.
    code

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice problem sets.

However, it is really hard to get a T-shirt.

→ Reply
»
9 years ago, # |
  Vote: I like it +17 Vote: I do not like it

BTW, editorial of "Long Narrow City" is really awesome.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    Thanks, I'm glad you enjoy it ;)

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

      Indeed. One of the best written editorials I've read. Nice problem for a long contest. Keep up the good work :). I figured out the solution but was too lazy to code it ;-)

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Shouldn't the editorial be unlocked even if you solve the problem after the contest?

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

    Nope, you don't need to buy it if you've solved it.

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

The question "Poisonous Plants" is the same as : http://codeforces.net/problemset/problem/319/B

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where is the editorial?

Or can someone explain the solution for problem 5 (Best Photo)? I think is dp but couldn't solve it.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    For all i, make an edge i to a[i]. You need to find circles, components, etc. Than you have to do some math on it.

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

      I tried some like that while the contest was running but the math was not obvious for me, can you give more details?

      Thanks.

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

        You can start by calculating the maximum number of groups you can be from these graphs.

        → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

LOL, we can solve Subset with O(215 * Q) time complexity, http://ideone.com/E1itZd

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

    Could you tell what is meaning of osob array? And how it helps to avoid TLE? Thanks.

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

    O(215 * Q) = 215 * 200000 > 109 How is it not TLE?

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Subset. Could someone explain this moment 'then count the numbers X that have at least one common 1-bit with S by inclusion — exclusion principle'. I don't quite understand how to use inclusion-exclusion principle there. Thanks.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There is a mistake in the last letter: w4yneb0t (3rd place) has 680 points, not 550

→ Reply