It's not about hope, You'll be gray if you participate.

Indian round ,Cool,,, Hopefully I won't be green this round :)

because IIT indore means The Indian Institutes of Technology Indore

Maybe time for getting a Shipping address in India too, and also ID proof.

PS.: Currently, shipping t-shirts would be tough in India too, shipping worldwide is almost impossible.

A blue can't set alone but he can do with orange or red. Orange/Red can only set contest.

As an advisor; Try rewriting; as a contributor, in the beginning, that will surely stonk your contribution.

I have noticed you comment in almost each blog Maybe you should try to control your urge as it seems too irritating for others.

Naah, just population I believe xD

Anything else?

k

Yes in inventing viruses

Hello Do Lund Trump

I think it is just free points.

Funny thing is IMO can be read as International Math Olympiad:)

Why?

yes

what is it in cricket that you like?

LMAO

you can watch match recordings as well as participate virtually

You are initializing an array of size 2,00,001 in each testcase. Maybe that's the reason?

tujhe_kyon_janna_hai

Yes, someone please tell me what is the Pretest 3 in D.

• I got WA on Pretest 3.
• Then, I figured out I used to wrong iterator. After correcting it also, WA on pretest 3.
• Then I thought, maybe it is because of overflow. So, I used long long. Then also WA on Pretest 3.

I precomputed number of digits for 0 to 9 until 2e + 50 and then solved eatch testcase in log10(n) by simply adding values from the array.

its a series. https://oeis.org/A103377

I have just debugged my code :( But I think it will be AC. EDIT: It got AC: 112711140

We can calculate answer independently for every digit, so we can use precalculation.

Precalculate all the answers (200000) for 9. It will take about of 2*10^6 operations

Then, in every test case count how many times every digit is present in n. I have used cnt array for that.

Substract every number from 1..9 from 9 and check if it's less than m. If it is, just add calc[m — (10 — i)] * cnt[i] to the answer. Else, simply add cnt[i] to the answer.

Time Complexity: amortized O(1) per every test case.

Code:

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define all(x) (x).begin(), (x).end()
#define len(s) (int)((s).size())
#define str(ch) string(1, ch)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using graph = vector<vector<int>>;

long long calc[200001];
void solve() {
    int n, m;
    cin >> n >> m;
    long long ans = 0;
    int cnt[10];
    memset(cnt, 0, sizeof(cnt));
    while(n) cnt[n % 10]++, n /= 10;
    for(int i = 0; i < 10; i++) {
        if((9 - i) < m)
            ans += calc[m - (10 - i)] * cnt[i], ans %= (int)1e9 + 7;
        else
            ans += cnt[i];
    }
    cout << ans << endl;
}   

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    long long cnt[10];
    for(int i = 0; i < 10; i++)
        cnt[i] = 0;
    for(int i = 0; i <= 200000; i++)
        calc[i] = 0;
    cnt[9] = 1;
    for(int i = 0; i <= 200000; i++) {
        long long ncnt[10];
        memset(ncnt, 0, sizeof(ncnt));
        for(int j = 0; j < 10; j++) {
            if(j == 9) {
                ncnt[0] += cnt[9];
                ncnt[0] %= (int)1e9 + 7;
                ncnt[1] += cnt[9];
                ncnt[1] %= (int)1e9 + 7;
                continue;
            }
            ncnt[j + 1] += cnt[j];
            ncnt[j + 1] %= (int)1e9 + 7;
        }
        for(int j = 0; j < 10; j++) {
            cnt[j] = ncnt[j];
            calc[i] += cnt[j];
            calc[i] %= (int)1e9 + 7;
        }
    }
    int tt;
    cin >> tt;
    while(tt--) solve();
    return 0;
}

https://mirror.codeforces.com/contest/1513/submission/112705430

I am getting TLE On Pretest 3? What is wrong with my submission?

your code has "index out of bound" on line 51

I agree.

It's harder than usual but not because of the math knowledge imo.

I agree that it needed more math knowledge than usual, but mostly math that occurs pretty commonly in competitive coding, not anything completely out of the blue.

• A — Adhoc, maybe a bit mathy

• B — Required some basic combinatrics, so fair enough its pretty heavy math for a B.

• C — Pretty standard dp, no math involved

• D — First observation is somewhat math intensive for a D (gcd = min means all elements are multiple of the min), but the rest of the problem requires no other math, just intuition of why Kruskal's algo constructs an optimal MST.

• E — Pure math, all non-combinatorial observations can be made using just the samples. Then its just standard combinatorial ideas that most 18-1900+ rated participants should have likely come across.

• F — didn't solve, no comments.

The condition in the problem is equivalent to finding the number of permutations of Indices of the array's elements so that ap1 and apn are bitwise and operation of all of the elements in array a. So let cnt be the number of occurrences of (a1 & a2 .. & an) in array a, if cnt is less than 2 then there is no such permutation and the answer is 0, otherwise the answer is cnt * (cnt — 1) * (n — 2)!.

For intuition, consider n = 2. This has a valid permutation when both elements are identical.

Now consider n > 2. What if the first and last elements in the permutation are different? Then, this is not a valid permutation since you can always make a 1-element group which has just the larger endpoint, and a (n-1) element group with all the other elements. The AND of the group with the smaller endpoint is strictly smaller so there's no solution.

Now we know the end points have to be the same. What about the middle elements? Assume there's an element in the middle that has a 0 in a bit where the endpoint has a 1. Then, we can always make a (n-1) element group that will have an AND smaller than the other endpoint. So, every element a_i in the middle must equal the endpoint when ANDed with the endpoint, i.e. satisfy (a_i AND a_0) = a_0. This also implies the endpoints must be the smallest values in the array.

So the answer is (count_of_smallest_element nCr 2) * ((n — 2)!), assuming there's at least 2 of the smallest element and all values in the array equal the smallest value when ANDed with it.

matrix expo is not needed

I have the same code... also very curious :) submissions

Try this -
1
12
12
2 4 10 16 2 6 3 21 30 17 20 16
Answer — 55

Let's say you have a testcase like this:

1
3 1000
2 6 3

Your algorithm connects 2 to 6, then doesn't connect 6 to 3. This can be fixed simply by using DSU instead of your vis[] array.

I made the same mistake and realized it after contest. Think of the following p=10 2 4 6 3

here 2 will connect 4 and 6 and 3 will be connected to(2,4,6) by p=10 in your case but the better way will be to connect 3 to (2,4,6) by the edge of weight 3.

Yeah, there's a catch out there! Notice that every time you're trying to connect your current index to some node on the left or right, you're checking if the left or right has already been considered or not! Now, consider the case like array [2,6,3]. Your algorithm will start from the first node and mark both 2 and 6 as connected So when you try to connect 3 to 6 (as 3 is the gcd of [3,6]), your algorithm denies saying that 6 is already visited! Now you can observe that the accepted codes have incorporated a slight change that allowed every node to be considered by potential values both on the left and right. An easy way out is always the DSU method, and when you wanna avoid that, you need to be careful about the components! So yeah one possible input is:
1
3 100
2 6 3

try adding fast io

tie(nullptr)
sync_with_stdio(false);

I got same tle, then i change cin and cout to scanf and printf and it passed

also you use endl, which flushes the output on each iteration, use "\n" instead

Btw, had to rewrite it from python to c++ because the most natural implementation didn't fit into time limit

Unnecessary tight time limit for D2C

Slow I/O operations, i.e., cin/cout.

Just added this to your code:

ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

Btw, it got WA due to integer overflow: 112713355

every time you count dp again

Its O(10*m*t)

You are given t <= 200000

The time complexity of your solution is O(t*10*m) which can be around 10^11 in worst case. So, it is giving TLE.

Just precalculate the dp once instead of calculating it every time.

For E, we want to reach $$$\frac{sum}{n}$$$ as the value of all elements. Lets call this the $$$\textbf{good}$$$ value of the array, all elements smaller than it as $$$\textbf{low}$$$ elements and all elements larger than it $$$\textbf{high}$$$ elements.

Clearly a high element can never be made less than good, as it can never be used later as a sink (due to step 4), meaning we can never make it good. Same for low elements and greater than x. For the same reason, good elements can never be used in an operation.

Now lets notice that if there exists any subsequence of the form $$$\textbf{low high low high}$$$ or $$$\textbf{low high high low}$$$ or $$$\textbf{high low low high}$$$, we can get different end costs by mapping the lows to different highs. So if there is more than 1 low and more than 1 high, we need them to all be separate, that is all lows before highs or vice versa.

So we just want to arbitrarily choose where to place the $$$\textbf{good}$$$ elements in the array, multiply that by the number of ways of individually permuting $$$\textbf{low}$$$ and $$$\textbf{high}$$$ respectively. (and that by 2 if the array actually has $$$\textbf{low}$$$ and $$$\textbf{high}$$$ elements for the other direction)

Ways of choosing places of good elements is clearly just $$$n \choose cnt_{good}$$$. Ways of placing low and high can be found is just multinomial theorem.

In E array is balanced if sum is divisible by n and there is no subarray [x, y, x, y] where x is less than sum / n and y is greater than sum / n. You can calculate number of combinations with multinomial coefficient.

Wow now that I realized I misread the problem statements. I thought i can't be source anymore :<. Wonder how many people like me and can't solve E :<?

because t <= 2 * 10 ^ 5 and you code for passing system test needed for ios_base or scanf & printf

The constraints were too tight:)

You can do nothing. That's the rule.