HackerEarth April Circuits ‘21 Solutions

general
,
1

Hello Codechef Community, Here are the editorials for the recently held HackerEarth April Circuits’ 21. Each and every problem along with their solutions are explained in detail.

Below are the links to the solution:-

  1. Minimum Operations
  2. Divide Arrays
  3. Smallest Subarrays
  4. A Special Sequence
  5. A Sign of Place
    update

Rest of the problems will be updated soon.

Please do watch videos, like, comment, and subscribe to this channel. Likewise, Videos will be uploaded for most of the contest’s editorial. Any suggestions are welcome, do comment in this blog post.

Thank You!!

Google Kickstart Round B Editorial
HackerEarth March Circuits '21 Solutions

4 Likes
2

Thank you for editorial buddy !
Can you point out what is problem with my code for proble A special Sequence?
I am getting TLE . Here is my code :- l0Ydlq - Online C++0x Compiler & Debugging Tool - Ideone.com

Edit:- I got it* lower_bound on set have time complexity O(n) :slight_smile:

1 Like
3

Why use a map and set if you can define a vector of fixed size because 1e13 will come under some constant index. It makes our work simpler. Refer to the solution for the explanation.

2 Likes
4
My Solution with Preprocess Hashing and Lower bound 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define Ceil(a, b) (((a % b) == 0) ? (a / b) : ((a / b) + 1))
#define FASTIO                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define tsolve(t) \
    ll t;         \
    cin >> t;     \
    while (t--)   \
    {             \
        solve();  \
    }
ll hash_L[1000005];
ll hash_R[1000005];
void preprocess()
{
    ll L = 1, R, X;
    for (ll i = 1, j = 2; i <= 1000000; i++)
    {
        X = (i * ((ll)sqrtl(i))) + Ceil(i, j);
        R = L + X - 1;
        hash_L[i] = L;
        hash_R[i] = R;
        L = R + 1LL;
    }
    // for (int i = 1; i <= 20; i++)
    //     cout << i << " " << hash_L[i] << " " << hash_R[i] << endl;
}
// ==================== Solve =====================
void solve()
{
    ll L, R;
    cin >> L >> R;
    ll x = lower_bound(hash_R, hash_R + 1000000, L) - hash_R;
    ll y = lower_bound(hash_R, hash_R + 1000000, R) - hash_R;
    cout << (y - x + 1) << '\n';
}
// ================================================
signed main()
{
    FASTIO
    preprocess();
    tsolve(t) return 0;
    // solve();
}
1 Like
5

Got it . Here’s AC implementation with vector and Binary search :- JoWWgb - Online C++0x Compiler & Debugging Tool - Ideone.com

1 Like
6

Problem: A Sign of Place, Updated
Do check it out.

3 Likes