satyaki3794's blog

Google APAC Kickstart 2018 Round A
By satyaki3794, history, 7 years ago, In English

Throughout the year, Google Code Jam hosts online Kickstart rounds to give students the opportunity to develop their coding skills, get acquainted with Code Jam’s competition arena, and get a glimpse into the programming skills needed for a technical career at Google.

Inviting you to solve some fun and interesting problems this Sunday, March 18, 2018 05:00 UTC – 08:00 UTC.

Link to contest dashboard
Problem analysis will be published soon after the contest.

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

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

A gentle reminder, the contest is about to start in 1:30 hrs!!! GoodLuck to all those who are participating :)

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

Seems like APAC is still using the old way of judging solutions: downloading/uploading i/o files. I am saying "old" cause I heard CodeJam will be shifting to the traditional method of submitting source code and running it on their server for judging.

Anyways, since we have to download input and run the solution on our OWN pc, I think this blog post will be helpful: Increase Stack Size in C++ IDE Codeblocks.

This will help you avoid getting Run Time Error while running your solution against large dataset :)

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

    aka "What to do when your solution runs in O(n^3) and there's no time to optimize it to O(n^2)".

    Wish I knew this when I first competed in kickstart. :/

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

    I heard that CodeJam will be shifting to new interface while APAC/Kickstart will continue with the same interface this year.

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

Fingers crossed, I might have submitted the small output for problem B, hopefully I stay at the third place at the end. :/

Edit: Screw it, I won't have 100% score after system test, I ACTUALLY SUBMITTED THE SMALL OUTPUT FOR LARGE OUTPUT

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

I was in top 30 previous year, but nobody has contacted me. Which score is good enough for interview invitation?

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

    Which round did you participated? Some offices only recruit on certain rounds.

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

    Last year, I got a call for internship at Google India from Kickstart Round C or D I suppose. I scored 75 rank I guess.

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

please dont say that B was ruined by allowing O(n*k) solutions to pass.

Also is there a determinsitic approach for C without using hashes

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

    Yes. My solution was O(n*k) and it passed. I know, its weird.

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

    what do you mean by "allowing O(n*k) solution to pass"? AFAIK google doesnt run your solution on their servers, only the output is matched with the correct output.

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

    Expected complexity is O(k*logn) right?

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

    Two main motivations to allow O(N*K) to pass were a. optimize for smaller input files and b. binary search not being the main crux of the problem.

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

      Lol. I overkilled the question using convexhulls.I did not notice the easier greedy part. That was the reason I was sad about O(n*k) solutions .Otherwise there is not much in adding binary search.

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

      There is no need of binary search though. You can just keep shifting the x pointer to the right, as Ek is increasing, and so is xk. Can be done O(n logn + k).

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

How to solve B and C ?

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

So, who else got into the following dilemma: should I solve A using greedy method or digit dp? :p

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

for C-large, isn't there sth missing in the editorial? How do I find which dict entries match for a certain length and frequency array (in O(1)), hashing with factor 26?

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

    When you move one position to right, frequency of one character increases and that of another decreases. You just account for this change and update the hash. This takes overall O(N) for a particular length.

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

      The value of N is too strict, even my solution which follows same complexity didn't passed because its update involved a few more multiplications and additions.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 3   Vote: I like it +15 Vote: I do not like it

        I don't think so. For large dataset, my code runs in 11s, and we have 8 minutes. Link to code

        EDIT : A possible reason for TLE is that when you access map using operator [], you also insert the element and it might increase the size of your map to , which is a little too much. For example, if I remove the 61st line from my code, it would give TLE

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

          Thanks, you are correct. This is the reason why unordered_map was giving TLE in my code.

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

How can we solve problem B without dp .

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

Problem A can be solved without implementing both decrease and increase case. I'm surprised that this is not mentioned in the editorial. This trick is really important to reduce complex implementation.

When you implemented decrease case as solve(n), you can calculate increase case by solve(8888888888888888 — n).

→ Reply