Привет, Codeforces!
Codeforces Round #483 пройдёт во 15.05.2018 17:45 (Московское время). Раунд будет рейтинговым для обоих дивизионов.
Задачи подготовили FalseMirror, KAN и я.
Большое спасибо тестерам qoo2p5, manoprenko, AlexFetisov, winger, cyand1317 и ashmelev.
Отдельная благорность MikeMirzayanov за Codeforces и Polygon и ifsmirnov за jngen.
И несколько слов от MikeMirzayanov:
Спасибо фонду Botan Investments и лично Виктору Шабурову за поддержку и поздравления c 8-летием! Горжусь нашим знакомством и возможностью помочь фонду запускать интересные программы! Напомню, что Botan Investments ведет регулярную работу по поддержку спортивного программирования в РФ: грантовая программа для преподавателей и 50000 рублей гроссмейстерам из регионов РФ работают уже несколько лет. Здесь вы можете ознакомиться с отчётами фонда и найти ссылки на интересные посты droptable (и в ВК-группе https://vk.com/botaninvestments).
Upd. Разбалловка 500-1000-1500-2000-2500 для div2 и 500-1000-1500- 2250 -2500 для div1
Поздравляем победителей!
div1:
div2:
how many problems ?
5 for each division
Judging from the name, it seems like a round in honor of people who donated some satisfying amount. Why are such special rounds not held on weekends so that as many people as possible could participate? Also maybe include some more information about the sponsors in the announcements.
My rating is waving on the border of specialist and pupil these days.
And bless everybody and me to get more rating in this contest.
It is raining contests...!!!
Don't worry that your division can change after ratings update after Codeforces Round 482 (Div. 2). I'll fix all the registrations to match your actual division.
Both divisions ? Now we have three in Codeforces ! Thanks Codeforces
But rounds are still div1 + div2
I believe if it is a thanks round, then the blog post should include some information and thanking for the supporters in this round. Otherwise it'll be no different from a normal round.
Accidentally downvoted :(
Accidentally downvoted your comment :(
Intentionally downvoted :)
Contests everyday, thank you
what does jngen mean???
jngen
Contest of Div1 and ((div2 — div3) union div3) ) :P
These guys will beat tourist :
who is the tourist?
i am fish
deepsee
Hopefully, (Div. 2) Problems will be interesting like today's one.
I sure hope your wish won't turn out to be true. :/
Wow, there are real jngen users :) I haven't promoted it for several months, so I'm very happy to see that sort of self-promotion exists.
I would be glad if you could share the problems with me after the round. If I see how the community uses the library I can maybe improve the docs, give you some advice or see new development directions. My polygon login is the same as here.
Wow, nice short description. Hope the description of the problems will be as short as the blog. :)
My semester final exam start from today and I am waiting for Codeforces Round #483 (Div. 2) [Thanks, Botan Investments and Victor Shaburov!] :).
My rating is below 2100 but I cannot register at the home page.
Please fix the bug. MikeMirzayanov
If there is a div1 round, you only can participate in it. You are still a div1 contestant.
Candidate Masters are in Div 1 when both Div 1 and Div 2 round are scheduled at same time.
Hopefully.
Candidate master still participate in div 1 round.
She: "What would you do alone at home?"
Mobile chimes, " Codeforces Div ..."
He: "I am not alone, anymore."
"Гожусь нашим знакомством", "лично Виктор Шабурову"
you said the round rated for both divisions
is it rated for div3?
or div3 is n't a division
is it rated for DIV-3?
DIV-3 is a subdiv of div2, not an independent div.
As it is rated for div2, it is rated for div3
So why do we call it div3?
Q. Why did Scarlet witch fell in love with Vision?
A. He was Red. :P
Заиграет ли velheor в Na'Vi?
Good question it could be if it was in english. Accroding to google translator velhore I guess will overplay in Natus Vincere. Good luck in contest! Do not lose as Na'Vi always do.
10 min delay. why?
They did not give any reason in the past. So I do not think we can know the reason.
You are Adhami, however you code in C++.
C++ is faster.
Java is an island. An extremely verbose island.
Because I used to use Java one year ago
I think they wanted to wait for more participants. It's reaching 6k now. Apparently they've got ~100 more participants in the last 10 mins.
What a baseless accusation.
Problems difficulty is Unbalanced at all A and B**** are extremely easy compared to C and D
just searching the problem C and going to the top result leads to the answer
why you copy the question from somewhere else and then remove the comments??
No Hacks !!
I solved problem C without the condition of 4 guys in the elevator, and was thinking why I had got WA 4 during all contest.
What's the point in making such a tough TL in div1A? Nice problems btw.
After finding g = gcd(q,b), If you divide q by g only once, it may reduces TL.(In TC 13)
Furthermore, the next value of g will always be a divisor of the previous one. So you can initialise g = b and then do g = gcd(q, g).
Is Div1 E just finding greedily till lca from both nodes and summing it??
Also is Div1 B using SOS dp or something easy??
I did simple interval dp with precalculating function on all intervals.
Dint precalc use SOS dp. ??
F[i][len] = F[i][len — 1] ^ F[i + 1][len — 1]
dp[i][len] = max(f[i][len], dp[i][len — 1], dp[i + 1][len — 1])
Thanks!! I dont know how to react to this to miss such a simple observation but find a very nice pattern...
Easy.
dp[l][r] = max(dp[l][r-1], dp1[l, r]) where
dp1[l][r] = max(dp1[l+1][r], dp2[l, r]) where
dp2[l, r] = (dp2[l][r-1] ^ dp2[l+1][r])
calc dp2 for all [l, r], then dp1, then dp.
Almost. The way I see it, you should go greedily (precomputing jumps by 2^k buses up) and stop before reaching lca, then check if the two vertices you stopped at can be connected by 1 bus. That check seems harder to me, I solved it using offline+sweepline+segtree in
or 
, but I'm sure there's a simpler solution.
That check is equal to query "Is there any number from interval [tinx, toutx] in the subtree of vertex y?" so it can be done with simple merging of sets.
Ah, you mean numbering buses by one end vertex (with subtrees=intervals) and looking for them in subtrees by the other end vertex?
My solution represents each "do we need 1 bus?" query by a rectangle formed by the intervals corresponding to the subtrees of its end vertices and each bus by a 2d point formed by the coordinates of its end vertices (both sorted to avoid casework). I avoid using a 2d interval tree by sorting and sweeplining by one coordinate, using an interval tree with operations "add/remove labeled interval" and "check off all intervals containing some point". In the end, I made it have
amortised complexity per query, it's just more work and a clever structure.
Yes
I think you need to know whether you can "save one bus" because the stops from both subtrees are connected by the same bus.
Since I'm not too sure how to phrase that properly, maybe I'll just highlight the problem by asking a simpler problem: Given 2 nodes, how do you know if they are connected by a bus (i.e. answer = 1 for that query)?
Thanks. I get it .Will work on it!!
How to solve C?
How did you find prime factors with such time constraints?
You don't need to find prime factors, just divide by the gcd until they are relative prime.
Ok thanks got it
i exactly did that but i got TLE on test 13:(
set
b = gcd(q,b)before iterating, it decreases the complexity of finding the gcd, cuz you don't care about the other factors.You have to divide q by g(g = gcd(b,q)) till q % g == 0. This statement cost me 6-7 WA. RIP rating
I solved C as your described, but i do not know why I got TLE in test11.
I was getting it too, until i switched to fast IO.
mraron, can u please, explain in detail? I knew that prime factors of q must be subset of b during contest. But seeing, constraint I couldn't figure out how to code i.e, prime factor for number till 10^18, would be TLE? Update : Leave it, understood :)
What I was thinking was to convert q to base b and then check if the new q contains only powers of 2 or 5. Is this a correct approach?
mraron p/q is finite iff each prime factor of q and b are equal OR each prime factor of q divides b???
Check this out, for base 10, https://www.youtube.com/watch?v=rVhU8Vyhz7c
A rational number p / q has finite decimal representation in a base b iff there exists a positive integer n such that q|bn. From this we conclude that the set of divisors of q must be a subset of the divisors of b. I tried implementing this idea in PyPy but got TLE on pretest 9 (though asymptotically it should pass, guess the constant factor for PyPy is too large or my implementation was bad. :( )
Edit: Reading mraron's reply above, I think that my implementation was bad, kind of overkill.
Hack-Free contest !
I have seen someone had a successful hack. It was really unbelievable!
I realized that the TITLE of the Problem Div2D,Div1B was such a huge hint, but it was too late. no time to debug.
Problem Div.2 C
What is the answer for :
1 1000000000000000000 999999999999999999 10
the calculator shows : 1000000000000000000/999999999999999999 = 1.000000000000000001 which is finite
Infinite
why is that ?
For it to be finite you should be able to multiply denominator into a power of 10
I'm sure your calculator would also show finite fraction for 1/3
The answer is infinite if q / gcd(p, q) has prime divisors which b doesn't have and finite otherwise. The problem is I couldn't realise it.
i don't think calculator can show infinite number of digits
Yeah I got it now.
The answer for you case is "Infinite", you can learn some about precision of calculator.
You are right! Checker is wrong so contest needs to be unrated!!!
Thanks Botan Investments for my decreased rating...
For div2d, I thought of some kinda O(N^N) preprocessing but I had no clue how to calculate f() efficiently.. What is the idea behind this problem ?
Look at the title of that problem. There's a huge hint.
If len = ar - al then
f(al, ..., ar - 1) = f(al, ..., al + len - 2k - 1) xor f(ar, ..., ar + len - 2k - 1),
where 2k is the maximum power of two that less than len
Sorry, I can't understand why that works. How to prove that?
Write a program that simulates the function f.
First, Calculate the 2d dp:
A[j][i+j] = A[j][i+j-1]^A[j+1][i+j]
then calc max as:
M[l][r] = max(A[l][r], max(M[j][i+j-1], M[j+1][i+j]))
then the query will be O(1)
Может быть, авторы перестанут ставить ограничение по времени 1 секунду в задачах, где много ввода????
Там они по какой-то странной и неадекватной причине решили отсечь
.
Хм, у меня возведение в 64ю степень с бинарным умножением зашло на претестах за 982 мс
и упало
а потом я поменял cout на printf и зашло
how can we solve problem D , i know we need to find max xor pair in given range , but how to optimise it from o(n^2) ?
Using 2d segment-tree would be enough, I think.
((r-l)log (r-l) for each query ?
NVM. my approach was wrong. it was a simple pyramid-dp problem like answered below.
build a table :
d[n][n] where d[0] = a, d[i][j] = d[i-1][j] xor d[i-1][j+1]precompute
mx[n][n], where mx[0] = d[0], mx[i][j] = max(d[i][j], mx[i-1][j], mx[i-1][j+1])answer queries
mx[l-r][r]thanks
I think it should be:
precompute, mx[n][n], where mx[0] = d[0], mx[i][j] = max(d[i][j], mx[i-1][j], mx[i-1][j+1])
Correct me if I am wrong.
my mistake, sorry
To be honest, I must appreciate how setters choose cases for pretests in this one — really careful and cover nearly everything one can slip into. Cheers. ;)
too tight time limit on Div.2 C....
Anybody else wants to complain against time limit of div1 A?
me, i even made a comment in russian
It depends on what is an intended complexity. Firstly I did something like log times gcd per testcase (which is O(log^2)) and it turned out to exceed TL. Then I did some optimization which looks silly, but I think it may actually improve complexity and passed in TL/3. However this task is actually doable in O(log(log(b + q)) per testcase, because it suffices to check if q|b64 which can be done with 6 multiplications if we have big integers or __int128_t that Codeforces doesn't have (taking mod q after each step of course).
I tried bigint solution with python, and got TLE..
I have log times gcd and it got AC. On the other hand, the numbers I'm computing gcd from decrease very quickly — it's "while Q > 1 compute gcd(B, Q), divide Q by it as many times as possible".
That's what I did in the end as well. I mean you and I both finally have "while Q > 1 compute gcd(B, Q), divide Q by it as many times as possible", but in the beginning I had "while Q > 1 compute gcd(B, Q), divide Q by it" without "as many times as possible". I am not sure what is the worst case complexity of this solution, but after some thought I got an impression it is really useful and it is not as silly as it looks.
For having "while Q > 1 compute gcd(B, Q), divide Q by it as many times as possible", it may takes even longer time in worst case. An example is q = 260, b = 231 then gcd(q, b) = 231 but we can divide it only once. However to check whether dividing it one more time is possible, we have to compute a division to check its remainder. (That cause extra time)
Yes, in some cases it may be worse but thats not a worst case. In your example in next iteration we will have gcd=2^29 and divide everything, so there is only 2 computations of gcd(which also has divisions btw). If you divide by gcd once you have up to 60 iterations of gcd (which gives
per test comlexity. If you divide while you can, it's no more then sqrt(60) iterations of gcd, which gives you 
(and comment shows that complexity may be shown to be 
I'm pretty sure this is asymptotically faster. It's no more that O(sqrt(log()) iterations of gcd because you divide by numbers with different number of primes each time
(and may be it's even faster)
If you do that + making B = gcd(B, Q) after not being able to divide makes the complexity O(log) amortized. This works because for each 2 iterations of Euclid's algorithm, one number is at least half of before and you use that number for the next iterations so the maximum number of iterations is O(log). Other than that, the number will obviously be divided at most O(log) times. Did I miss something?
Edit: also, for your optimization my friend's reasoning applies. There will be 1 prime that will get below the exponent of B in one while iteration and it will disappear in the next one. So you get rid of at least one prime for each 2 iterations.
Thanks riadwaw for this comment, he is right, this solution works O(nlog1.5M). Optimization
is same as "divide as we can", but 
works faster because numbers are smaller. But I think that it doesn't make less complexity. Editoral will be updated.
It actually does make the complexity O(logM) per case. Maybe I wasn't clear on the comment above. If you call gcd(q, b) for each 2 iterations b will be at least half so the sum of iterations until b is 1 is O(logb) (amortized).
By iteration I mean iterations inside gcd
Sorry, it's not clear to me why the complexity is
O(log M)per case.If you have
log(N) + log(N/2) + log(N/4) + log(N/8)..., that's stilllog(N)^2time, no? Since it'slog(N) + (log(N)-1) + (log(N)-2)...complexity.Seems to me like the real complexity is still
. Since the worst case involves all the primes having different exponents, we can divide by more than half each time, we can divide by 2i for each iteration. So, our computation is
log(N) + log(N/2) + log(N/2^3) + log(N/2^7)..., orlog(N) + (log(N) -1) + (log(N) - 3) + (log(N) - 6) ....So, the number of
terms.
log(N)operations we have to do is based off of how fast1,3,6...reacheslog(N). As that's just simply the triangle numbers, there'sIf you had one gcd take x iterations then B will be <= B / 2^(x/2). So the complexity isn't log(N) + log(N/2) + log(N/4) + log(N/8)... and the sum of steps will be <= 2 * log(B).
So if a gcd computation takes indeed log(B) or a big number of steps, the number will be much lower than B and the maximum number of iterations for the rest will be lowered. This is amortized analysis, not every gcd will be worst case. Also as you get closer to worst case for gcd, worst case implies that gcd is 1 and you don't need to continue so more iterations == B is much lower.
If I'm not mistaken the following simpler code works in
:
Suppose that the loop has several iterations, and the value of variable b in the i-th iteration is bi. Time complexity of the i-th invocation of Euclid's algorithm is
. So the total complexity of the loop is 
, since 
for some Q.
solution for Div2. C (Div1. A):
https://math.stackexchange.com/questions/310402/proving-finite-vs-infinite-representation-of-p-q-in-base-b
(i think now there is no violation with codeforces stupid rules)
they didnt even change the p,q,b!!!
well if you know the solution. why you couldn't get accepted verdict? they have tighten the time limit so you must try different approach.
i tried 19 different approaches!
and now when i see others approaches some of them are same whit me and the only difference is that they print the answers immediately but i print all answers after calculating all of them
A very high chance that it's just a coincedence. Integer fraction is very often (almost always) presents as p/q and base is ussualy presents as 'b'.
An interesting game
problem C looks trivial. Does this dp works? dp[i][pos][x1][x2][x3][x4]=minimum cost if the first i people already entered in the elevator, currently we are at floor pos, and the elevator contains people that wants to go to floors x1,x2,x3,x4.
Yes, i think. but you should consider memory limit in that problem.
well, we only need the last two rows so i={0,1}
You can reduce the complexity and memory space only considering the ordered multisets of (x1, x2, x3, x4). There is only 715 such multisets. Also looked trivial for me, just a careful implementation was needed.
This is the first round when I solved div1 E. I solved div2 E for the first time when Livace was the problem setter too (Codeforces Round #442).
Link: http://codeforces.me/contest/877/standings
Perhaps you should plan to meet him in person?
I don't think it's just notorious coincidence ;)
in problem (B. Minesweeper) 1 1 * how test like this can be valid ????
It satisfied all constraints.
There is only one cell with a mine. No cells left un-mined, so no numbers could be found.
The one cell satisfies both criteria given in the problem statement:
:)
there is a bomb with no number point to it !! this is a violation for the game rule ??
During the contest I wanted to hack leon_ldy's solution(38273146).I had 2 unsuccessful submissions in this problem and after my second submission I noticed in pretests 8 , n=1.but why his submission passed pretest? this is his code:
but when n=1 so j=0. and in the "while (true)" we had TLE. because at first "j--" and after that j=-1. so always j!=k.
C+E = (Code*Code*Code+Code^2)^Code
What's wrong with C? Seems fine to me.
That it is obvious to come up with a solution and nontrivial how to properly code it. It is a programming task, not an algorithmic one. Some people would say that it is ok, but I think that it is also ok to say it is not an interesting problem.
OK, I see what you mean (but I still think that it's pretty easy to code)
It seems that whenever contest goes well for me I think tasks were fine and when it doesn't I always declare tasks as programming and noninteresting ones :P.
For C I check whether the divisors of q are a subset of the divisors of b with gcd but still get TLE on 13.
It is because of slow input
Any ideas for D?
Probably, it's wrong
Do you know any good tutorials for kd-tree?
Unfortunately, I haven't seen.
For D I followed this easy-to-implement solution(actually, it's not classical KD-tree, it's more likely as joined KD-tree and Segment tree, just intersecting rectangles instead of segments) Probably, the author forgot about inclusion/exclusion case with boundary points in some quadrant.
Author's solution is scanline + segment tree with sets in vertices.
even after writing exactly the same code as it is being discussed in the comment section, my solution failed. Time limit for python is too strict. i got tle in 11. Please verify if there is a mistake on my side or this happened because of the language selected. Thanks :)
my English is poor,emmmm,
~~~~~ while(q!=1 and r!=1): q=q/r while(q%r==0): q=q/r r=gcd(q,r)
it means while q not equal to 1 || r not equal to 1
i know , it is the first time for me to reply you can look the code i changed.
I even tried this in my submission but even that failed pretest 11
oh i know ,and you should know if p == 0 output Finite change like that ~~~~~ while(q!=1 and r!=1): q=q/r r=gcd(q,r) ~~~~~
ohh shoot I think I got my mistake i thought all were having constraints >=1 Thanks a lot mate
it dosent matter whether p==0 or not as when p==0 gcd(p,q)=q and q/q=1 and so ans would be finite it is definitely fault of strict time limit
The language selected is the mistake on your side.
I know. I think its time to switch to c++
It can be solved with python although. Not recommended. http://codeforces.me/contest/983/submission/38299853
but isn't this method just a fluke way which has no guarantee always. can't the original solution with any optimization pass in python
yes, it's better to use C++/Java for the contests. Some problems just can't be solved in python under given time limits.
Is the time limit for python and c++ same every time for every question???
Pretty sure it is. Python needs more love!
no I guess its 5x for python but at times even that is slow it makes the competition more fair if the setter/tester try it in python as even python is being used a lot as compared to c++ and java
Where did you hear of this? All I see is there is only a single time limit for each problem, e.g. it's 1 sec for Div2 C
python has a time of 5x likewise java has 2x. this time is allocated according to the processing time of the language. as python is a slower language than c++ it gets 5x time. But this dosent mean python has more advantage.
You aren't answering my question though, are you sure you are not just making this up?
no I am sure as on various platforms like codechef and hackerearth this rule follows
For Div2D , if (r-l+1) is power of 2 then we can take all elements from l to r.
If I am right then please someone say the answer of this input and how ?
24
1 2 128 256 512 1024 2048 4 8 16 32 64 1 2 128 256 512 1024 2048 4 8 16 32 64
1
5 20
The answer is 4035. For simplicity, that input is the same as
16
512 1024 2048 4 8 16 32 64 1 2 128 256 512 1024 2048 4
1
1 16
While you can take all elements from 1 to 16 (f(array), if array's size is a power of 2, is indeed the xor of all elements), the statement asks for the biggest value of f considering all continuous subsegments of the subarray v[l...r]. The xor of all elements in this input is 507, however you can take f(v[7...14], 0-indexed) which gives 4035.
OMG, I did bitwise OR rather than XOR ( typo ).
http://codeforces.me/contest/984/submission/38300540, http://codeforces.me/contest/984/submission/38290267
During the contest I had the following problem. In my template I have a few pragmas that should optimize operations and make Codeforces submissions faster (they’re pretty common to include nowadays).
However, for today’s problem E, something weird happened. The solution with these pragmas got RE verdict on pretest 1, while the solution without them got accepted.
http://codeforces.me/contest/983/submission/38296856 http://codeforces.me/contest/983/submission/38297301
I assure you the only difference between the two sources is in the pragma macros.
Have you ever experienced something like this? What pragma do you think is broken, in this sense?
Leaving my comment, cuz I am curious as well and I wanna be notified :D
I tested on custom invocation and put the bits/stdc++ line before the pragmas and oddly it worked. I have no idea why
Third pragma. The problem may appear in situation, when CF uses different machines with a different architecture to compile and run code. It's common problem on Yandex Contest system. I use following pragma for it:
So, is it only the tune=native setting I shpuld remove or all the rest of them?
Also, I can’t test myself right now, have you tried running it without tune=native and seen it work?
Also, I see no point in using these pragmas outside CF, as from my experience with using it, it was always worse times.
Ok, I tested. In your case it's "abm" setting.
Actually, It depends not on platform, but on problem and on your code. That is, if the bottleneck of your solution can be vectorized, then the pragma will help. Otherwise, the optimizer can apply vectorization where it is not needed, and your solution will slow down.
I agree with that. However, I’ve seen consistently better results overall on Codeforces, while I’ve never seen improvements on Yandex (Opencup for example). I think it depends on the architecture and the compiler as well. I’m not pretending to know anything here, but my guess is that the running on Windows the pragmas will have a bigger positive impact than on Linux.
Have you ever had noticeable changes using these pragmas on Yandex? (compared to not using them, obviously)
There were some problems from SNWS contests, PTZ and MIPT camps, that I solved with not optimal complexity, and I'm pretty sure that pragmas helped in that solutions.
abm changed the implementation of std::__lg, which is later called by std::sort. Here's a simple example of it being unstable, even on other platforms:
Output:
with abm
without abm
Lol, I added the Ofast pragma to my code for E and it slowed down by ~50%.
On the other hand, one secondary school student in our IOI selection used
to almost solve a problem with bruteforce.
The time limitation on Div2C is too tight.... just reassigning gcd value made it passed.. -_-
Systests for div1B are weak, i see some O(q*n) solutions accepted
Can anyone explain why first gives TLE and the other one AC 38300452 and 38300601
Because
cin/coutis much slower thanscanf/printf. So, don't usecin/coutto solve big I/O problems.you can just write first line from int main(): ios::sync_with_stdio(false); and this will give you a boost
When are we going to get the tutorial?
So, did noone notice this: 1 2?
ʕ ͡° ͜ʖ ͡°ʔ
As far as we know, the problem coincided with a problem from some Chinese online judge :(. So we think these submissions are fair.
https://blog.csdn.net/wmdcstdio/article/details/44596291
Actually is this problem from a Chinese National Training Team contest back in 2011.
can someone explain why the first query of the second test case of Div.2-D is 60 instead of 63? shouldn't it be 1 ^ 2 ^ 4 ^ 8 ^ 16 ^ 32?
You misunderstood how f function works. Acturally, the answer for f(1,2,4,8,16,32) = 51. You may implement it yourself. :)
Pretests for B were pretty weak. In my solution I put a "n" instead of "m" in the second loop when I wanted to traverse my matrix. Apparently that was enough to pass the pretests. I noticed that error only after the system tests.
Then I changed "n" for "m" and got AC. Sad day for me :( .
weak pretests are needed for hacking:)
Hacking is needed for weak pretest (not the opposite)
Q. When does one grow up? A. When one reads more comments on CF than FB.
In div2 problem C For values of p,q,b=(10,5,3) in TC#3 how the answer is finite
10 / 5 = 2 in base 10 which is 2 in base 3. This does not have a non terminating decimal part(rather does not have any digit after decimal point)
I guess you are confusing with the case (p,q,b) = (5, 10, 3). In which case it would be non terminating and hence infinite in problem's context.
So you only need to take into consideration the prime factors of denominator and base since for improper fraction a/b you can always write it as [a/b] (greatest integer function) + {a / b} (fractional part) where the former will always be translatable to different bases without recurring decimals . Refer editorial for more insights.
Well if we convert both numerator and denominator firsthand to base 3 i.e. 10 in base 3 would be 101 and 5 in base 3 would be 12, so 101/12 will be infinite. I am confused here.
Yes it is correct to say that but notice that since you convert numbers to base 3, conventional division(in base 10) does not work.
You can still observe that base3(12) * base3(2) = base3(101). Hence we don't have a recurring decimal. An easier way to do the this is the same as mentioned in samples in the question .
I was trying to solve Div1E with O(n * sqrt(n)) complexity, sqrt(n) jumps instead of binary lifting. When I debugging I changed my sqrt variable to 1. And it got accepted.
38320734
It simply tries to jump lca and stop when there's a route from this node to lca. And same thing for second node, also check for ans - 1, no different solution.
You can check my code and see that for every query I'm calculating the answer with increasing res one by one.
And sad part is I have no clue how good my O(n * sqrt(n)) solution is. It actually got slower time :(