Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

dunjen_master's blog

By dunjen_master, history, 3 weeks ago, In English,

Can somebody explain their solutions to problems-

1) Promotion Game 2) Count Diameters

 
 
 
 
  • Vote: I like it
  • -8
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

2)Count Diameters

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

    Oh shit !!

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

    Did you submit and get the testcases right?

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

    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 ?

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

      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
      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

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

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

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

    And is $$$summation(1/i)$$$ for all i from 1 to n . Can anyone prove????

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

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

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

How did you solve the string question?

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

    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².

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

      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));
                  }
              }
          }
      
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Someone please tell the approach for string problem.

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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]

»
3 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

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

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

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

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

if i would have more time, i would have solved all. promotion game u can find series on OEIS. counting diameters is BF by checking all graphs( i didnt solve my friend did). stirng problem was LPS dp.

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

The content was great.

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

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

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

    Nope it wasn't this time.

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

      I remember there was a check box before starting the test on HackerRank that said only language reference and IDE with auto-completion are allowed?