Hack Lockdown 1.0 Editorials

editorial
,
6

Problem 2: Small Volume
I am getting wrong answer but I am using the same approach.
Instead of writing nnn, I am using pow(n,3). Please Help me.
Here is my code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        ll v=n*n*n;
        ll sv;
        if(n<=2)
        {
            sv=0;
        }
        else
        {
            sv=pow(n-2,3);
        }
        cout<<v-sv<<"\n";
    }
}
7

Since N can be 10^9 , your answer is overflowing. Use binary exponentiation to calculate a^n

1 Like
8

I know binary exponentiation but I don’t understand
why will it prevent overflow?
could you please elaborate the reason.

9

In binary exponentiation we can calculate a^n in log(N) time instead of the naive O(n) method, which is why it will not overflow. Basically, it breaks the number, when the number is even and calculates the product.

10

Sorry buddy!

This is my first post on discussion forum. I’ll format it by tomorrow.

11

I don’t know much about cpp but do pow() fiction returns floating number or integer?

12

Very weak test cases of Ordered Indexed array.
for ex . test case 1
3
2 4 11
3
Correct answer is NO
but many solutions are giving wrong answer (i.e YES ) including mine

1 Like
13

NO, you check yourself. The correct answer is 8 for n=2. I have checked it. But please explain me when I am replacing pow(n-2,3) with (n-2)(n-2)(n-2) then My solution is getting accepted.

14

Was this contest rated?

15

no

1 Like
16

i think thats because pow function return floating point value by default. If you will explicitly do the type conversion, I think your solution will get accepted.
And yes, correct ans for n=2 is 8

17

Nope.

18

I don’t know much about cpp pow() function.

19

Copied problems, yet poor statements. That’s laughable.

3 Likes
20

I think the problem statements in the contest were a bit confusing.
Also, in the minimum trans. question, someone asked that is it necessary that ui != vi and you said its not necessary, but when i opened the hackearth link provided above, it was clearly mentioned that ui and vi are guaranteed to be distinct.

Its just a suggestion that you please try to explain the statement properly.
Take it positively. :slightly_smiling_face:

1 Like
21

can u explain how to solve it

22

Bro I uses different test cases.
Yes, will try my test in the next contest.
Thanks for the suggestion buddy.

1 Like
23

Its a simple dynamic programming problem
Step1:- Precompute all prime factors of number at ith index in an adjacentcy list
Step2:- Apply Top down Dp approach same as you apply for finding paths reaching nth step using recursion +dp
Step3 go for every prime factor in both the directions and update the dp[i][j],
where dp[i][j]=true if and only if you reached i in exactly j steps.

MY Simple solution can describe more.
Solution

1 Like
24

Thanks for explanation but I see many solution using matrix exponentiation.
Any idea?

25

My solution was of pure recursion … It was giving TLE, but after setting max. recursive calls, it ran in almost 0.97 sec with AC…

I avoided visited places…
I caught the point that if we have cycles then we can actually waste some moves to sum up to M(if we reach last position before M moves)

You could find solution here