md.ashif313's blog

By md.ashif313, 2 months ago, In English,

Google's hiring contest, APAC Kickstart 2017 Round E is going to held on Sunday, August 27, 2017 05:00 UTC – 08:00 UTC

Google

Ready to get started solving fun, challenging problems? Throughout the year, 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 potentially get noticed by Google recruiters, too. Participate in one—or join them all!

For more visit here.

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

»
2 months ago, # |
Rev. 2   Vote: I like it -26 Vote: I do not like it
  • Is it rated?
  • Is dit gegradeer?
  • هل يتم تقييمه؟
  • Qiymətləndirilmişmi?
  • рэйтынг Ці з'яўляецца гэта?
  • Оценява ли се?
  • এটা রেট কি?
  • Je hodnoceno?
  • Αξιολογείται;
  • Értékelt?
  • Գնահատված է:
  • È valutato?
  • האם היא מדורגת?
  • それは評価されていますか?
  • Бағаланған ба?
  • វាត្រូវបានវាយតម្លៃ?
  • 등급이 매겨 졌습니까?
  • Is it rated?
  • ມັນຖືກຈັດອັນດັບ?
  • Ar jis vertinamas?
  • ഇത് റേറ്റുചെയ്തിട്ടുണ്ടോ?
  • Үүнийг үнэлдэг үү?
  • Adakah ia dinilai?
  • အဆင့်သတ်မှတ်ခဲ့ပါသလဲ?
  • Er det vurdert?
  • Czy jest oceniany?
  • Это оценено?
  • A është vlerësuar?
  • Да ли је оцијењен?
  • Na e baloa?
  • Je, ni lilipimwa?
  • ఇది రేట్ చేయబడిందా?
  • Na-rate ba ito?
  • Beğenilen mi?
  • Чи оцінюється?
  • Nó được đánh giá?
  • Ṣe o ṣe ayọkẹlẹ?
  • 是否评分?
»
7 weeks ago, # |
  Vote: I like it +40 Vote: I do not like it

Did anyone got call due to his/her performance in KickStart Round D ???

»
7 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Where can we upload our resume on the kicktstart site? I have already registered

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

All solutions and explanations will update here soon after the contest ends. https://github.com/ckcz123/codejam

Good Luck!

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Solutions of A, B and C-small have been updated!

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

Round link anyone?

»
7 weeks ago, # |
  Vote: I like it +54 Vote: I do not like it

Sadly no one get 100 scores, people who passed C large are all failed in A large.

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

Can any one tell me how did they did B large?

  • »
    »
    7 weeks ago, # ^ |
    Rev. 3   Vote: I like it +17 Vote: I do not like it

    Let's say the sides of trapezoid are a, b, c, c; such that b > a; Now due to the fact that height of trapezoid should be  > 0, we get the condition between a, b, c as b > a and b < (2 * c + a). Now you can simply iterate a, c and count the number of b's that satisfy given condition. The answer is number of ways we can pick (a, c) * number of such b's.

    The counting of b's can be done in O(logn) using binary search. That gives the solution complexity of O(n2logn).

»
7 weeks ago, # |
Rev. 3   Vote: I like it +5 Vote: I do not like it

Can someone explain their solution for A-large?

I tried a dp solution but failed. Can somebody please point out the error? Let s be the string. State is dp[i] which is the minimum steps required to construct the string s[0..i]. Initialise dp[0] = 1 and dp[1] = 2. For every i in [2, length(s)-1], first do dp[i] = dp[i-1] + 1 which corresponds to the first operation. Or select some j < i and consider the string t = s[j..i]. Check if the string t can be formed by repeatedly concatenating some substring of itself and check whether that substring exists in s[0..j-1]. If it does, then dp[i] = min(dp[i], dp[j-1] + 1 + length(t)/l) where l is the length of repeating string we considered.

My code: Ideone

Thanks!

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

    DP[i][a][b] — minimal number of steps for sufix i...n if in clipboard we have substring a..b

  • »
    »
    7 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Got my mistake.

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

      Can you please share what the mistake was?

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

        A substring can reamin persistant on the clipboard with character intsertions in between. For example, condider bacackac.

        Here, b-> ba -> bac -> bacac -> bacack -> bacackac.

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

          Ah yes, totally missed that. Thanks!

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

          What would be recursion for this problem ? I came up with these cases ->

          1. Simply append next char.
          2. Simply append next char but start copying from here in clipboard.
          3. Append the clipboard string to current string.
          4. Simply append next char and this will be new start of clipboard string(that is, previous clipboard text discarded).
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What with this test?

    gabbbbbbbbbcwabbbbbbbbbc

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Mine gives 12. But I cant give assurance since mine is a hashing solution

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

        could you share the idea of hashing solution?

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

      I am getting 12 with my code, I compared this with an AC code which also outputs 12.

  • »
    »
    7 weeks ago, # ^ |
    Rev. 4   Vote: I like it +9 Vote: I do not like it

    Simply use recursion with memoization

    f(cur, str) -> if till cur we have made the string till "cur" and "str" is on clipboard, our answer is f(-1, "") and halt recursion when cur = n — 1; where n is string's length.

    Transitions:

    1) add one char -> 1 + f(cur + 1, str)

    2) if string on clipboard fits -> 1 + f(new_length_done, str)

    3) one by one check for all x if substring (s[cur + 1....x]) is already present in made up string -> 2 + solve(x, s[cur + 1....x]);

    Memoize using map< pair<int, string> , int> dp Code: https://ideone.com/pixvWn

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      Wow, that's an awesome solution!

    • »
      »
      »
      7 weeks ago, # ^ |
      Rev. 3   Vote: I like it +3 Vote: I do not like it

      Can you please explain the third transition in a bit detail ????

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

        Basically I try to copy a new string to clipboard and obviously paste it to end of our already made up string (otherwise we won't even paste it on clipboard). So 1 move for pasting on clipboard and then 1 move for pasting it at the end.

        For e.g. s = "mautkakuan" and cur = 5, clip = "a";

        I try to put strings 1) "k", "ku", "kua", "kuan" one by one to clipboard and then to string and move forward to f(new_len_done, clip).

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          shubhiks1032

           while(j <= cur)
              {
                  if(is1(i, j, s1))
                      return true;
                  i++, j++;
              }
          

          why are we considering only the first occurrence of substring?

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I dont think this will pass large data set, even with memoization.

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

      nice solution, and how to analyze the time complexity?

»
7 weeks ago, # |
  Vote: I like it +31 Vote: I do not like it

What is the approach to solve C Large ???

»
7 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Here are some unofficial results after running plagiarism check on all the codes(includes both accepted and unaccepted submissions).
https://drive.google.com/drive/folders/0ByNcq665KLJhMWh6U1MwWEY0djQ

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

My rank is below 350 and in india below 100.I am in third year can i get chance of intership or not.

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Hello everyone, here is the official analysis:

https://code.google.com/codejam/contest/12234486/dashboard#s=a&a=3

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How to check if three circles have a common intersection?