satyaki3794's blog

Google Code Jam Kickstart 2018 Round E
By satyaki3794, history, 6 years ago, In English

Throughout the year, Google Code Jam hosts online Kickstart rounds to give participants 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.

Each Kickstart round gives participants 3 hours to solve challenging, algorithmic problems developed by Google engineers. Participating is a fun way to grow your coding skills—and potentially explore opportunities at Google.

Inviting you to solve some fun and interesting problems on Sunday, August 26, 2018 05:00 UTC.

Dashboard can be accessed here during the contest. Problem analysis will be published soon after the contest.

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

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

Starts in 15 mins

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

WTF did just happen? I saw the first problem. Coded it. Went to submit it. And now it says the contest begins in 7 minutes?

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

    Sad part is should have started from C

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

    How did you see it? It showed contest begins in 15 mins just when it was going to start.

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

      For me, problem A was automatically loaded when the contest was going to start.

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

The contest has been delayed by 15 mins due to some technical issues.

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

    Why did you hide the problem statements? It is unfair that some lucky contestant can read problems during 5:00-5:15.

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

Participants who read all of the problems just after the contest start win.

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

Is there a reason all problems have the same scoring? I don't think they are the same level of difficulty.

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

How to solve 2nd subtask of problem B?

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

    Do greedy and find minimum configuration. If it is not prohibited take it. Else try changing all possible bits(change bit x and then recurse and change some-other bit and so on). If u get a non-prohibited solution u can stop else u can keep on changing the bits. Since m<=100 u won't exceed memory

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

      But how will I make sure that cnt is minimum?

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

        Since we arer initially doing greedy solution when we terminate at a solution it is optimal because changing any other bits will lead to a sub optimal solution. In all possible changes for 1st change of bits are seen only a few will be prohibited. For those we change a second bit and then third bit if necessary and so on

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

    Always take the maximum frequency for each bit. There are two cases:

    1. If p is small, then simply run a bitmask solution for each bit and sort all the obtained costs storing the obtained strings alongside. Start from the smallest cost obtained until you find a permitted string.

    2. If p is big, note that since m is small, the final string will differ in at most 2 bits from the minimum cost string. Just iterate over p^2 possible different strings, mainaining the costs of the string. Again start from the smallest cost obtained until you find a permitted string.

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

      Maybe this is wrong because if the absolute difference between no. 0's and no. of 1's at position i forms array

      1 1 1 n n n n n n n n n n n n. (n is maximum diff we know). then this maynot work.

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

        Oh missed that. That would have failed my solution. Seems like the testcases were weak.

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

          I'm crying like hell, even I thought of too many greedy solutions, but I realised that all were wrong. and didn't even try........ I didn't expect such weak test cases :(

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

    Do DP with (index , forbidden string indexes that match the prefix built yet) as state. https://www.ideone.com/HfxR4M

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

How to solve a problem B with large input ?

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

    I tried using Greedy + Dijkstra.

    Starting with simple assumption M=0 (no forbidden tea)

    Now, using greedy find to target binary string( T0 ) which have minimal cost. ( Binary indexes are independent in this case)

    However M can be more than 0, but it has to be less-eq than 100.

    Considering a graph whose states(nodes) is represented by a binary string.

    We can start exploring states using Dijkstra with start state as T0. And from each state, we can jump to adjacent states which are at Hamming distance 1 from current state binary string with the proper edge cost.

    Terminate the search when the first binary string which is not present in forbidden tea is found. ( Our solution )

    And, the max number of states explored should be bounded by M * P

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

When will the results be out? Today ranklist wasn't working properly during the contest either :(

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

Was B (large) DP with bitmask Problem ?

→ Reply
»
6 years ago, # |
← Rev. 5   Vote: I like it +8 Vote: I do not like it

My solution to B large: https://pastebin.com/v1yEZSVz

DpWays[X] counts the ways we can get X complains. If we are at the ith position and we use want to use 0 then we look at position i-1 and we will add how many complains we will get in ith position if we use 0(so we will add the number of ones of all strings in that position). So if at ith position using 0 we get A complains then at ith position if we will use 0 and we want to count the ways we can get X complains(until position i) we will calculate it as dpWays[X][i] += dp[X — A][i — 1]. Similar with the 1.

After that we just delete the complains we will get if we use strings from the forbidden set.

Answer will be the smallest X that has at least one way to happen.

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

How to solve C ?

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

    I had a solution with 2-D sparse BIT (Binary Indexed Tree). Basically first calculate number of permutations such that Bahu at least 2 values greater than the corresponding values for Bala. It can be done simply by using a BIT. Then subtract 2 times the number of permutations where all three values of Bahu are greater than Bala. This can be done using 2-D sparse bit. Any solution easier than this?

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

      Could you link your code?

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

      Is it possible to perform such a query (finding the number of elements smaller than a given element) using a BIT?

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

    Let Ai (Bi) be the sum of Bahu's (Bala's) cards in the i-th battlefield. If we fix A1 & B1, the rest part can be calculated by two pointers. Complexity is comb(3n,n)^2 comb(2n,n) and this is a bit larger, so I had to implement carefully(e.g. It is ok to assume a1 is always in the 1st battlefield. It is trivial when A1<=B1 && A2+A3<B2+b3+2 or A1>B1 && A2+A3>B2+B3.)

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

Is there some problem with the scoreboard?

All Scores shows different rank whereas friends shows different rank.

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

Upto which rank does google call for internships in kickstart?

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

    Some answers on quora says as much as 350, given that you've a good resume.

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

Today morning around 10 mins before contest start I had this feeling that Kickstart is happening very properly compared to last year wrt glitches in website, leaderboard, reminder emails and all.

Then today's contest happened.

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

    Yeah, true.

    Analysis isn't out yet, so probably they're fixing up the things for now. The scoreboard and dashboard shows different statistics as well.

    Do you have any clue why all questions carried equal scoring? And round was only for 60 pts instead of 100. So, other than technical glitches they were some other issues too?

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

I solved B large by first constructing the best solution by looking at each ingredient.Then flipped bits corresponding to each subset in ascending order of cost of flipping, where cost of flipping is change in the cost before and after flipping. Since the number of disallowed configurations is almost M, this is feasible.Ranking the subsets wrt cost can be done by maintaining a min heap and updating with next largest element.

→ Reply
»
6 years ago, # |
← Rev. 5   Vote: I like it +15 Vote: I do not like it

Serious scoreboard glitch- When I access the scoreboard from my account, then it shows that I have attained 22nd position when the one right below me has less penalty, and moreover, there are two people in 22 position from my account!

What's more surprising is, when the scoreboard is accessed from incognito mode or some other account, my username/rank doesn't show up at all, like I haven't even participated in the contest! And not just me, I've definitely found some other accounts with the same problem.

Even all scores and closest competitors show different results from my side.

I think this issue is serious, and must be fixed. I definitely do want a job at Google, and hope this does not hamper it in any way :(

EDIT-Resolved :D

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

    I met the same issue. Could anyone take a look at this issue?

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

    It seems something is broken very badly there. Notice 30th place penalty is 1:22:36, and 31th place penalty is 2:29:42 — there is a huge gap, which seems very weird because results of other contestants are very close. The same pattern is observed for other pages too, for example results of 90th and 91th places — huge gap again. Looks like lots if people are missed from the common scoreboard.

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

      Exactly-I think a whole page is missing between 30th and 31st place, and I am in that page maybe.

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

From what I am seeing, half of the participants are missing from the standings-that is, contestants who have obtained which would have been in even pages had the standings been complete. Another way of wording is it-pages 2, 4, 6, etc are missing from standings.

When will this issue be resolved?

Edit-Resolved :)

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

Scoreboard is fixed now. Really apologize for all the inconvenience. Hope you enjoyed the problems atleast (amidst all the frustration). I assure all of you folks that such kind of experience will not repeat in the future.

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

My rank is 250. Any chance to land an interview ?

→ Reply