Блог пользователя dunjen_master

Автор dunjen_master, история, 4 года назад, По-английски

Can somebody explain their solutions to problems-

1) Promotion Game 2) Count Diameters

  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

2)Count Diameters

Spoiler
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Oh shit !!

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Did you submit and get the testcases right?

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Suppose the graph looks like this

    5 3 1 3 5 5 4 5 2

    • $$$k=1$$$ There are $$$4$$$ diameters
    • $$$k=2$$$ There are $$$4$$$ diameters
    • $$$k=3$$$ There are $$$2$$$ diameters
    • $$$k=4$$$ There are $$$0$$$ diameters

    Can someone please explain why this is wrong ?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится

      I also had a stupid bug. After fixing my code gives these graphs

      • k=1 There are 4 diameters (1,3), (3,5), (4,5), (2,5)
      • k=2 There are 5 diameters (1,3,5), (3,5,4), (3,5,4,1), (3,5,2), (2,5,4)
      • k=3 There are 3 diameters (1,2,3,4,5), (1,3,5,4), (1,3,5,2)
      • k=4 There are 0 diameters
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Oh thanks ! I understand my mistake. I was counting diameters but we should be counting subgraphs !

»
4 года назад, # |
Rev. 3   Проголосовать: нравится +4 Проголосовать: не нравится

Promotion Game — Stirling numbers of the first kind (https://oeis.org/A000254). This gives p. q is n!

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

How did you get to know about the test through some website or anything..?

»
4 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

How did you solve the string question?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Dp with states (i,j,k) representing answer for substring from l to r with k being the last taken alphabet, as there are 26n² states and each state can be computed in constant time, the overall run time was 26n².

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      what is wrong in it?

      static int f(int left,int right,int last,char a[]){
              if(dp[left][right][last]!=null)return dp[left][right][last];
              if(left>=right)return dp[left][right][last]=0;
              if(a[left]!=a[right]){
                  return dp[left][right][last]=Math.max(f(left+1,right,last,a),f(left,right-1,last,a));
              }
              else{
                  if(last!=a[left]-'a'){
                      int temp=2+f(left+1,right-1,a[left]-'a',a);
                      temp=Math.max(temp,Math.max(f(left+1,right,last,a),f(left,right-1,last,a)));
                      return dp[left][right][last]=temp;
                  }
                  else{
                      return dp[left][right][last]=Math.max(f(left+1,right,last,a),f(left,right-1,last,a));
                  }
              }
          }
      
»
4 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Had you written a brute force and searched oeis, the solution of promotion game was <10 Lines of code

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

For string question- Take two pointers let's say i and j representing the points in the string where i<=j Now if s[i] is equal to s[j] we can take them only if the last character we took is not equal to s[i], this is because of the condition that Xi =/= Xi+1. Thus along with i and j we need to remember the last character we took. Thus in this case ans= 2+ f(i+1,j-1,s[i]) If s[i] =/= s[j] we need to take maximum by increasing i or decreasing j that is, ans=max( f(i+1,j,last_ch) , f(i,j-1,last_ch) )

ans=f(0,n-1,26) , ['a'-'z']=[0-25]

»
4 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Any idea when they call for further rounds and what will the cutoff in this test?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How many questions did you solved? I was able to solve 1st, promotion game and partial for count diameters.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The content was great.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hey, how come some of the comments mention "googling" the problems? Isn't it forbidden to use Internet resources in this?

»
4 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Can You please Provide the question statements for the same...

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

did anyone give today's hiring test?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yes, did war one. What about you?

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      I did the cubes one, and I passed 12 test cases/15 in the metrices problem. What was your approach for War?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I was only shown 1 sample test and 4 hidden tests which my solution passed for B. How were you able to see the 12/15 thing? Btw I used binary search to find the answer in B and used prefix array in the check function. What should be the cutoff according to you?