ganesh_6's blog

By ganesh_6, history, 2 years ago, In English

Given a positive integer k and two non-negative integers n and m such that we need to take out a certain non-negative integer from n and certain non-negative integers from m such that the sum of these two is <=k.

Formally, n, m>=0, and k>0. Number of ways to take a and b from n and m such that

0<=a+b<=k

The number of such (a,b) pairs?

I can do it in a linear solution. Any O(1) combinatorics solution? Please let me know. I need this solve https://codeforces.me/problemset/problem/1744/F -> I got an idea where in i want to optimize from O(n*n) to O(n).

UPD: The below solution worked and i got AC: Submission Using this formula: https://codeforces.me/contest/1744/submission/179129170

Full text and comments »

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

By ganesh_6, history, 2 years ago, In English

Problem: Bots

The solution explanation/discussion is in the comments. I could not understand the editorial. Please help me! Thanks!

Full text and comments »

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

By ganesh_6, 2 years ago, In English

For the expression, do we have a formula like we have for $$$\binom{n}{0} + \binom{n}{1} + \binom{n}{2}+\binom{n}{3}+\binom{n}{4}+... = 2^n$$$

$$$\binom{n}{0} * 0! + \binom{n}{1} * 1!+ \binom{n}{2}*2!+\binom{n}{3}*3!+\binom{n}{4}*4!+...$$$ ?

This gives an intuition like taking 0 or 1 0r 2 0r 3... items from n items and permute them in a given place.

Full text and comments »

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

By ganesh_6, history, 2 years 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

Full text and comments »

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

By ganesh_6, history, 2 years 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!

Full text and comments »

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

By ganesh_6, history, 2 years ago, In English

I am solving https://codeforces.me/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.

Full text and comments »

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

By ganesh_6, history, 3 years ago, In English

I am solving the problem https://codeforces.me/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.me/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!

Full text and comments »

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

By ganesh_6, history, 3 years 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?

Full text and comments »

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

By ganesh_6, history, 3 years ago, In English

I was solving the question http://codeforces.me/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++

Full text and comments »

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

By ganesh_6, history, 3 years 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";
    }
}

Full text and comments »

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

By ganesh_6, history, 3 years ago, In English

I am solving the problem https://codeforces.me/problemset/problem/1033/C. I could not get the editorial and found the comment https://codeforces.me/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.

Full text and comments »

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