darkshadows's blog

Google Code Jam Kickstart 2018 Round B
By darkshadows, 7 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 Saturday, April 21, 2018 23:00 UTC.

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

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

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

Notif: It's on!

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

How to solve B large?

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

    Calculate dp: f[pos][mask] is a number of ways to construct a correct binary starting from position pos and ending at the end of the string, where first bits will be mask, and all constraints are satisfied.

    Number of bits in mask should be equal maximal difference between Bi and Ai, so 16 should be ok.

    Transitions: select which bit 0 or 1 you want to add to the position pos - 1, and check that all constraints starting at the position pos - 1 are satisfied.

    You can use long double, but I code it in python.

    Given this dp, you can easily construct needed string.

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

How to solve C?

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

    C: We will count the triples where there are no squares passing through all of them.

    It isn't hard to show that (x1, y1), (x2, y2), (x3, y3) is such a pair if and only if (x1 < x2 < x3 and y1 < y2 < y3) or (x1 < x2 < x3 and y1 > y2 > y3) under some permutation.

    Therefore, it reduces to calculating the number of points in each quadrant if we regard each of the N points as the origin. This can be done by a simple segment tree. (by going from left to right)

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

Problem analysis is uploaded.

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

I have a small problem : My name appears on the ranklist (rank 58) for me and all people who have added me as friend(it appears in both friends list and in the position of rank 58 in general ranklist) but it does not appear when I am not signed in or for people who have not added me as friend.

I observed this immediately after the contest ended but I thought it would rectify with time but it didn't.

My handle is the same (sdssudhu) for kickstart.

Can anybody help me with this ??

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

    Fixed now. Please check. Scoreboard generator task died somehow. Sorry for the inconvenience.

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

      Thanks. I can see my name in the scoreboard now.

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

Can someone explain the 3D digit-dp solution for problem A?

→ Reply