№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 161 |
2 | awoo | 160 |
2 | maomao90 | 160 |
4 | atcoder_official | 157 |
5 | -is-this-fft- | 155 |
5 | nor | 155 |
7 | adamant | 153 |
8 | maroonrk | 152 |
8 | Um_nik | 152 |
10 | djm03178 | 146 |
Название |
---|
E was quite good tbh.
can someone please explain me the solution of problem E in detail ...i am too dumb to understand this
I struggled quite a lot with problem E. Hope this explanation helps you.
Let’s first look at the constraints of the problem, here the value of (n = 100) and the value of (a <= 10^4) and (1 <= b <= 10000). We have to find the value of the expression (n * a — b). So, what can be the max value of this expression? If n = 100 and a = 10^4 and assuming b = 1 (because the minimum value of b can be 1) we get that the max value of the expression becomes (n * a — b = 10^2 * 10^4 — 1) = 999999. From this deduction what can we say? There will be 6 digits maximum in the final solution we want to find. If there are more than 6 digits we can simply ignore those answers because we found out the max value to be of 6 digits. So, the problem has been reduced to a minimized version and can be solved with brute force on the value of 'a' only.
If we run a loop for a from 1 to 10^4, and inside that loop we firstly find digits(n) * 'a', which is basically the number of digits in the number (n * a) for each value of 'a'. Now as we know this value (digits(n) * a) must not be greater than 6. Because as we discussed earlier those values will not contribute to our answer. So, we run a loop of digits(d) from 1 to 6 and can find from that b = (digits(n) * a — d). In case you didn't get this point what was the original equation supposed to be? (digits(n) * a — b = d).
From this, you got the value of both a and b. Now you can calculate the original value of n * a — b and the value digits(n) * a — b and compare if both of them are equal. If both of them are equal then these (a, b) pairs will contribute to your answer. And as we are running a loop for the value of a only from 1 to 10^4 and n = 100(max) and for the digits 1 to 6.
The total time complexity reduces to 100 * 10000 * 7 ~ 10^7(roughly). Which is fast enough to pass the test cases.
thanks... understood it very well
amazing explanation I was not able to understand the editorial but your explanation was to the point and simple to understand.
Your explanations are very beginner friendly ,keep going brother <3
I'm glad to hear that.
Shayan sir, a small suggestion from my side, if you are doing official video editorial then why don't you just give testing to the round and prepare your videos in advance?? (I know there will be no live discussion happens if this works, but I think you will get more time analyse the harder problems and come up with a good problem discussion) just a personal opinion.
You are right. I will test this idea.
Thank you for explaining question F very well