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

Problem: Bots

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

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.

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

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!

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.

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.

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!

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?

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?

#include<iostream>

using namespace std;

long long xa,xb,ya,yb,xc,yc,t;

long long cp(long long x1,long long x2,long long y1,long long y2)
{
    return x1*y2-x2*y1;
}
int main()
{
    cin>>xa>>ya>>xb>>yb>>xc>>yc;
    t=cp(xc-xa,xb-xa,yc-ya,yb-ya);
    if (t==0)
    {
        cout<<"TOWARDS"<<endl;
    }
    if (t<0)
    {
        cout<<"LEFT"<<endl;
    }
    if (t>0)
    {
        cout<<"RIGHT"<<endl;
    }
    return 0;
}

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";
    }
}

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

import java.util.*;
    import java.io.*;
    import java.math.*;

    public class Coder {

      static StringBuffer str=new StringBuffer();
      static int n;
      static int a[];

      static void solve(){
        int dp[]=new int[n];
        for(int i=0;i<n;i++) dp[i]=-1;
        for(int i=0;i<n;i++){
          int cur=a[i];
          boolean isAll=true;
          for(int j=i+cur;j<n;j+=cur){
            if(a[j]>cur && dp[j]==0){
              isAll=false;
              break;
            }
          }
          for(int j=i-cur;j>=0;j-=cur){
            if(a[j]>cur && dp[j]==0){
              isAll=false;
              break;
            }
          }
          if(isAll){
            dp[i]=0;
          }else{
            dp[i]=1;
          }
        }
      }

      public static void main(String[] args) throws java.lang.Exception {
        BufferedReader bf;
        PrintWriter pw;
        boolean lenv=true;
        if(lenv){
          bf = new BufferedReader(
                              new FileReader("input.txt"));
          pw=new PrintWriter(new
                BufferedWriter(new FileWriter("output.txt")));
        }else{
          bf = new BufferedReader(new InputStreamReader(System.in));
          pw = new PrintWriter(new OutputStreamWriter(System.out));
        }

        // int t = Integer.parseInt(bf.readLine().trim());
        // while (t-- > 0) {
          String []st=bf.readLine().trim().split("\\s+");
          n=Integer.parseInt(st[0]);
          a=new int[n];
          st=bf.readLine().trim().split("\\s+");
          for(int i=0;i<n;i++) a[i]=Integer.parseInt(st[i]);
          solve();
        // }
        pw.print(str);
        pw.flush();
        // System.outin.print(str);
      }
    }

/**
     *    author:  tourist
     *    created: 07.10.2018 20:09:43       
    **/
    #include <bits/stdc++.h>

    using namespace std;

    int main() {
      ios::sync_with_stdio(false);
      cin.tie(0);
      int n;
      cin >> n;
      vector<int> a(n), pos(n);
      for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
        pos[a[i]] = i;
      }
      string win(n, '?');
      for (int x = n - 1; x >= 0; x--) {
        int i = pos[x];
        win[i] = 'B';
        int j = i;
        while (true) {
          j -= (x + 1);
          if (j < 0) {
            break;
          }
          if (win[j] == 'B') {
            win[i] = 'A';
            break;
          }
        }
        j = i;
        while (true) {
          j += (x + 1);
          if (j >= n) {
            break;
          }
          if (win[j] == 'B') {
            win[i] = 'A';
            break;
          }
        }
      }
      cout << win << '\n';
      return 0;
    }

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.