ganesh_6's blog

By ganesh_6, history, 3 hours ago, In English

What is the alternative to mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); in c++ for Java? Tagging users who use Java for Problem Solving

taran_1407 SecondThread

Read more »

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

By ganesh_6, history, 2 days ago, In English

Can anyone provide a proper explanation of the A2 problem of Round 2 Facebook Hackercup editorial provided here: https://www.facebook.com/codingcompetitions/hacker-cup/2022/round-2/problems/A2/solution

I could not understand the Video editorial as well.

If you have other solution, kindly explain it. I want to learn and upsolve it. It is indeed a good question. Providing code/implementation the explanation is highly appreciated. Thanks!

Read more »

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

By ganesh_6, history, 3 months ago, In English

I am solving https://codeforces.com/contest/1556/problem/C. I got an idea to use Stacks and Prefix Sums to find the answer, However, it is failing on test case 13.

Submission

My Approach: 1. Iterate from left to right and calculate prefix sum of length upto index i.

  1. Iterate from left to right and insert extra open brackets in stack with it's location i.

  2. When we get extra closing, pop the stack and match closing with opening.

  3. In every iteration insert matching subarray in a list, because we can use this to calculate number of ways to group matching subarrays.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By ganesh_6, history, 5 months ago, In English

I am solving the problem https://codeforces.com/contest/1579/problem/F . Although I got the idea to solve it, I could not get the mathematical formula or intuition that the number of cyclic sequences formed can be gcd(a, b).

From the editorial https://codeforces.com/blog/entry/95447, I came to know that "Note that by shifts of d the array splits into gcd(n, d) cyclic sequences of this kind, each of length n/gcd(n, d)".

Can anyone explain the mathematical intuition or provide some explanation for this formula? Thanks in advance!

Read more »

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

By ganesh_6, history, 5 months ago, In English

I am solving a problem: How many words are less than four letters long and contain only the letters A, B, C, D, and E? Here, 'word' refers to any string of letters.

My Solution 1 uses Generating functions gives the wrong answer

(1+x+x^2+x^3) * (1+x+x^2+x^3) * (1+x+x^2+x^3) * (1+x+x^2+x^3) * (1+x+x^2+x^3)

where (1+x+x^2+x^3) is Generating function for each letter. This approach gave a wrong answer (35+15+5+1) which is the sum of coffecients of (x^3, x^2, x, 1) in x^15 + 5 x^14 + 15 x^13 + 35 x^12 + 65 x^11 + 101 x^10 + 135 x^9 + 155 x^8 + 155 x^7 + 135 x^6 + 101 x^5 + 65 x^4 + 35 x^3 + 15 x^2 + 5 x + 1

Correct Approach using Case Work gives the correct answer

Case 1: The word is one letter long. Clearly, there are $$$5$$$ of these words.

Case 2: The word is two letters long. Constructing the set of these words, there are $$$5$$$ options for the first letter and $$$5$$$ options for the second letter, so there are $$$5^2 = 25$$$ of these words.

Case 3: The word is three letters long. By similar logic as above, we have $$$5$$$ options for the first letter, $$$5$$$ options for the second, and $$$5$$$ options for the third. Then there are $$$5^3 = 125$$$ of these letters.

Adding all our cases up, there are $$$5 + 25 + 125 = 155$$$ words that are less than four letters long and contain only the letters A, B, C, D, and E.

Could Someone help me in explaining why the Generating function approach failed here?

Read more »

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

By ganesh_6, history, 6 months ago, In English

I was solving the question http://codeforces.ru/contest/227/problem/A. If the cross product is zero then obviously they are collinear since sin(x)=0 if x=2*n*PI. However, how do they decide if it is Left or Right based on the value of cross-product i.e; x1*y2-x2*y1. Please demystify this for me. Am I missing any fundamentals?

C++

Read more »

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

By ganesh_6, history, 9 months ago, In English

I know Nim Game, Nim Sum (xor sum) and the theorem, lemmas behind that. Also, I solved the https://cses.fi/problemset/task/1730 After solving that, I moved to https://cses.fi/problemset/task/1098 I could not figure out the solution. So, I found one solution online and could not figure out the nuances behind the working of the algorithm. I can see that he has used a[i]%4 which is used for one pile game to find out the winner. However, in this case he combined Nim Game 1 algorithm and 1 pile game algorithm to derive the solution. Please explain the reason behind working of this?

#include<bits/stdc++.h>
using namespace std;

string solve(int n, vector<int> heaps){
    for(int i=0;i<n;i++)
    {
        heaps[i]%=4;
    }
    int xr=0;
    for(int i=0;i<n;i++)
    {
        xr^=heaps[i];
    }
    if(xr)
    {
        return "first";
    }
    else{
        return "second";
    }
}

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By ganesh_6, history, 10 months ago, In English

I am solving the problem https://codeforces.com/problemset/problem/1033/C. I could not get the editorial and found the comment https://codeforces.com/blog/entry/62287?#comment-462858 useful. I have implemented the solution as per the comment, but it is giving WA

WA
AC

My doubt is that why can't we do like WA and why should we loop using elements instead of indexes?

Please explain why the earlier approach is giving WA and not later.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it