Help in solving CSES - DIGIT QUERIES

help
1

Problem Link
Here’s my approach from the mathematical Idea being used here to reach the required number from which to pick the particular digit from 9999…

Here’s my code which is leading me to WA for k > 9*13121110987654321

#include <bits/stdc++.h>
#define ll unsigned long long
#define vll vector<ll>
using namespace std;
 
void setIO() {
  cin.tie(0)->ios_base::sync_with_stdio(0);
}
 
void solve() {
  vll store = {0,9*1,9*21,9*321,9*4321,9*54321,9*654321,9*7654321,(ll)9*87654321,(ll)9*987654321,(ll)9*10987654321,(ll)9*1110987654321,(ll)9*121110987654321,(ll)9*13121110987654321,(ll)(12718089998888888889)};
  vll tens = {1,10,100,1000,(ll)1e4,(ll)1e5,(ll)1e6,(ll)1e7,(ll)1e8,(ll)1e9,(ll)1e10,(ll)1e11,(ll)1e12,(ll)1e13,(ll)1e14};
  ll k,i;
  cin >> k;
  for(i = 1;i <= 14;++i) {
    if(store[i] >= k) break;
  }
  cout << to_string(tens[i]-1-(store[i]-k)/i)[i-1-(store[i]-k)%i] << '\n';
}
 
int main() {
  ll q;
  cin >> q;
  while(q--) solve();
  return 0;
}

& here’s my submission

Please help me know what’s exactly wrong with this code and how can I fix it ?

2

store[14]-k can cause an overflow, if k>store[14].
tens[14]-store[14] would cause an overflow as well.

Will that happen in your code? Maybe, it depends on the input values. Which I don’t know since you did not link the problem.

1 Like
3

Thanks for the response sir but i ve linked the problem now and one more thing store[14] isn’t leading to overflow it’s just giving warning but causing no problem and more importantly store[14] isn’t even needed upto store[13] it works fine as k <= 1e18 <= store[13]

But the problem for WA is something else please help me fix my code

4

your store array is wrong. Its not only wrong, but also annoying. Magic-numbers (numbers whose origin is not clear) should only be used, if you have a clear reason. You neither have time pressure nor would it take any meaningful time or work to calculate them. So do it!

The way I would calculate “store” is in 4 steps:
-1st calculate how many numbers exist with n digits (numbers amount)
-2nd calculate how many digits these numbers have in total respectively (digit amount)
-3rd calculate how many digitis these numbers have commutatively (commutative digit amount)
-4th (optional) divide each of the last arrays numbers by 9 so you can see where you went wrong.

The solutions are below. None is fully complete so you cannot use magic numbers^^
Calculate them!

numbers amount

[0, 9, 90, 900, 9000, 90000, 900000, 9000000, 90000000, 900000000, 9000000000, 90000000000, 900000000000, 9000000000000, 90000000000000, ?, ?, ?]

digit amount

[0, 9, 180, 2700, 36000, 450000, 5400000, 63000000, 720000000, 8100000000, 90000000000, 990000000000, 10800000000000, 117000000000000, 1260000000000000, ?, ?, ?]

commutative digit amount

[0, 9, 189, 2889, 38889, 488889, 5888889, 68888889, 788888889, 8888888889, 98888888889, 1088888888889, 11888888888889, 128888888888889, 1388888888888889, ?, ?, ?]

commutative digit amount divided by 9

[0, 1, 21, 321, 4321, 54321, 654321, 7654321, 87654321, 987654321, 10987654321, 120987654321, 1320987654321, 14320987654321, 154320987654321, ?, ?, ?]

5

Why it’s not fully complete ?
And what’s exactly wrong with calculation of total number of digits from 1 to max i-digit number at ith position in store ?

6

not fully complete so you cannot copy-paste.

You are not really calculating them, you have an array that is supposed to have the solutions. But store is not correct.
store[0], store[1],…store[10] are correct. Everything after is wrong though. Also Note that I did not mean to tell you to change your approach. What you call “store” is what I called “commutative digit amount” above.

1 Like
7

Yeah I just wanna know what’s exactly being wrong after store[10] . Everyone says it’s wrong after that but what’s being wrong after that where’s the error same formula which was used to calculate till store[10] is being used afterwards too so what’s actually wrong ?

8

you can compare your store-array with “commutative digit amount divided by 9”. Just click the arrow to open it up.

Also, feel free to show how you calculated store. To me it looked like you were adding numbers in reverse and multiplying by 9 (20191817…7654321 * 9). This is a symmetry that works initially (until you reach 11-digit numbers), because there are no carry-over digits in the parent formula. The symmetry changes when these are introduced though.

9

btw, I do not know how you are learning and feel free to do whatever keeps you motivated. But if you are free to choose your learning platform, you may want to use problems that have viewable solutions and editorials.

I believe a beginner gets the most out of something like: https://a2oj.herokuapp.com/
(this is a mashup list of codeforces problem. The list ranks Problem by how much they help you improve. Top problems in that list are extremely educational and often have an editorial.)

1 Like