Problem Link
Hey everyone,
First of all, thank you everyone for taking part in this contest. Second, I apologise for ruining this contest.
When setting the question, I directly jumped to proving mathematically that this problem can be solved in n+p-3 steps. My solution was motivated by the logic that, when you get 2 numbers which are equal to the final LCM, you need additional n-2 steps to make rest of the n-2 elements equal to the final LCM. But it turns out that it is possible to do it more optimally.
Some CC Discuss threads point out that this can be done n+p-4.
It would be really great if someone can provide a proof for this.
We can use this thread to discuss correct solution for the problem.
1 Like
sometimes it can be done in n+p-3 i.e for n=4 or n=5 but sometimes n+p-4 is the ans like for n=7
Will the contest be unrated ?
If there is a rejudge ,then what about those who coded the solution and got AC and then moved on to solve question 3.(you know,because in a contest ,time matters a lot).
Had the test cases been right, people(who got AC by coding the wrong solution) would have spent more time figuring out the correct solution.
So ,if the contest were to be rated ,should this question be even considered?
The contest is unrated.
2 Likes
I only thought of n+p-3. Some people got n+p-4. But is a lesser value possible?
it’s very tough for problem setter when contest become unrated but i really enjoyed this contest.
3 Likes
for some cases it might be possible to do it in n+p-4. one thing i can point out is the answer will also depend on the number of multiples of the largest power of that prime fitting inside n. Like for example for n=23 , the highest power of 5 inside 23 is 5, but the presence of numbers 10,15,20 which are a multiple of highest power of 5 affects the answer.
n=23 can be done in 27 steps
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
first consider only these 8 numbers
7,9,11,13,16,17,19,23
LCM(7,9)
LCM(11,13)
LCM(16,17)
LCM(19,23)
63 63 143 143 272 272 437 437
LCM( 63,143)
LCM(272,437)
63 9072 9072 143 272 11864 11864 437
LCM(9072,11864)
LCM(9072,11864)
out of the 8 now 4 numbers are 1078334208 in total 8 operations;
combine these 4 numbers each with 5,10,15,20
LCM(1078334208,5)
LCM(1078334208,10)
LCM(1078334208,15)
LCM(1078334208,20)
all four will give same answer which is the final LCM all four numbers should reach
so now in total 8 numbers(4 of 1078334208 and 5,10,15,20) are converted to final form in 12 steps, this leaves us with remaining 23-8=15 numbers which can be done in 15 steps combining each with any of 8 already in final form
so it requires 15+12=27 operations
I dont know to include this to form a complete solution though
yes, 27 is possible for n=23
Then there is no formula. Which means that bruteforce is the only way.
Also, LCM(1, \ 2, \ 3, \ \dots, \ 10000) (yes, 1e4 not 1e6) will not fit in long long. So this problem should be unsolvable under the given constraints.
@dj_r_1 bro n+p-3 atleast tell how yiu get this. n-2 steps is okay. why to add p-1 also for ans ? @therealnishuz
1 Like
If you write down all numbers from 1 to n, you will notice that only the highest multiple of primes contribute to the LCM.
this part alone pls explain a bit
Why do you even want to know about it? It is wrong.
First do this and think for a while. You will notice that only primes matter. Then try to correlate this with the multiples of their highest powers.
See, you have p primes < N. Now, we need highest power of all these primes in our final LCM. So, we need to combine p primes, this will take p-1 steps.
This contest was based on judging mathematical skills rather than programming and algorithms ,we are preparing for writing good programme not for solving mathematical equations.
Try the questions Min Max String and Special Power string. They are based on algorithms and Data Structures(DP, tries and LCA).
Question Beautiful Circle can be solved purely using implementation(By finding the intersection points and then the required centre and radius). You can easily find the code for finding intersection points on cp-algorithms.