I’m making this thread in the same spirit as the ones made for previous month’s long challenges by @vijju123 and @aryanc403.
I would request you all to NOT ask other people to review your code as an answer in this thread but in the end it’s your choice.
Anyway, here’s my 2 cents on the problems I found interesting.
MAXEP
The most efficient solution is to do a binary search where, at each step you query for a point that divides the current range in a ratio 1:r\ such that r satisfies r^{c+1} = (r+1)^c.
WKPLAN
I was able to show that given sum can be written as \displaystyle \sum_{n=1}^N \Big(f*h(n)\Big)\Big(n^p\Big)
Where * represents Dirichlet Convolution and h(n) counts the number of ways to chose m numbers such that their gcd is 1 and their lcm is n.
h can be written in terms of other common functions related to Dirichlet Convolution as h = \mu * \mu * d^m. Their meaning can be found in the wiki I linked.
And the whole sum written in terms of common functions is \displaystyle \sum_{n=1}^N (f*\mu *\mu *d^m)\cdot(Id_p)(n)\ where \cdot represents pointwise multiplication.
My guess is that we can somehow calculate prefix sums of h\cdot Id_p efficiently and using them we can calcalate the required sum in O(n^{\frac{3}{4}}) using the method shown here.
3 Likes
I actually thought of making one, but thought its too late now for that. Next time I’d make a thread, whether editorials or no editorials.
I did MAXEP in a different way. I used linear search itself to solve the problem. In my case, the panel will not break more than once.
I queried in the following manner:
Query for 850: If it breaks, start from 1 and you have enough coins (850) for linear search now.
If it doesn’t break:
Query for 850+849: If it breaks, we have enough coins (849) for a linear search between 851 to 850+849.
Observe that I just used the fact that 1+2+3+…+850 > 1,50,000 which is the largest N possible.
Here is the link : https://www.codechef.com/viewsolution/21769768
3 Likes
Thank you. Can you explain your idea of binary search?
Think of ‘regular’ binary search. Let’s assume you know that l\leq x\leq r for some l, r. You can start with l=1, r=n. Then if you query for a point m that lies in that range and it breaks the panel, then you can say that l\leq x\leq m and if it doesn’t break then m+1\leq x\leq r. What I’ve said is that the best m that you can choose is such that it divides the range [l,r] in a ratio 1:R i.e. \frac{r-m}{m+1-l} \cong R and that R^{c+1} = (R+1)^c but I haven’t provided a proof for that and I probably wont. Notice that if c = 0 then this reduces to a ‘regular’ binary search.
MAXEP using the idea of Egg dropping puzzle
-
100-floor building and 2 eggs.
-
Calculate the highest floor from which eggs won’t break on dropping.
-
If an egg breaks during the drop, we can’t use again. If it doesn’t break then we can reuse it.
Here we fix the worst case drops. Let’s assume its x. We first drop it on the x th floor and if it breaks we check 1 to (x-1) linearly. If it doesn’t then we have used one drop and we are remaining with (x-1) drops so we drop at $(x+(x-1))th floor. If it breaks then we have to check (x-2)$ floors linearly.
Similary,
- x
- x+(x-1)
- x+(x-1)+(x-2)
- …
The last floor we break is n. So, x(x+1)/2 = n.
For n = 100, x comes out to be 14.
Relating to MAXEP,
-
n is 150000
-
x turns out around 548.
-
Egg breaks 2 times in worst case, so similarly in MAXEP, the cost is 300 (150*2).
-
Adding total cost 848 which is less than 1000.
2 Likes
I did MAXEP by linear search. I searched basically in chunks of 300 . So max to max we will have to go through 150000/300=500 chunks . So max cost=500+150=650 .Lets call the multiple of 300 at which breakdown occurred to be x . then i checked from x-299 to x . This will take at max 950 coins .
Illustratively lets say the answer to a case is 1249 . so what i will do is ask the checker answers for 300,600,900,1200,1500 . as soon as breakdown occurs at 1500 i will start checking from 1201 to 1500 and as soon as first time breakdown occurs i print that answer.
Here is My Solution
https://www.codechef.com/viewsolution/21854111
I see. Looks good. I’ll see if I can prove that.
I did by this by the help of jump search concept.
Here is my Solution
https://www.codechef.com/viewsolution/21874631
I did this question with jump search.
here original Constraints are
1≤N≤150,000
1≤c≤150
in this we can take a interval of sqrt(n) and check in this interval if panel does not break then we will check the next one. when we found the desired interval we do Linear search in this.
we can see if n=150000 then sqrt(n)=387.-- so we can do this thing in less then 1000 coins.
here is my solution
https://www.codechef.com/viewsolution/21874631
I solved MAXEP by Square Root Decomposition.
For those who don’t know about it, just search online. Its a well known approach.
I had to apply it twice that is decompose the required block further then applying linear search
Just look at my solution. You will get what am saying
https://www.codechef.com/viewsolution/21840529
Can someone please post the solution to BICONT? The one thing I’ve been able to figure out after looking at the accepted solutions and asking on codeforces is that we need to do a DFS and compute the dp for children first and then use the dp for the parent. The dp is of the form dp[node][number of components or equivalently the number of bridges][size of the component for the current node]. However I’m not clear how and why this works.