harsh_bamane17's blog

By harsh_bamane17, history, 3 weeks ago, In English

WCPC 2024 Invitation

Greetings, fellow Codeforces enthusiasts!

We are thrilled to invite you to WCPC 2024 (Walchand Collegiate Programming Contest), hosted on the Codedrills platform! This competition is inspired by the spirit of ICPC and is an excellent opportunity to sharpen your skills ahead of the ICPC Regionals.

Tracks:

Novice Track: For first-year students (FY) Expert Track: For second, third, and final-year students (SY, TY, and Final Year)

Prize Pool: 15k INR

Registration Links :

To those gearing up for the ICPC Regionals on 11th November, we wish you all the best! We hope this contest serves as an excellent warm-up for your journey to the regionals.

Special Thanks:

A big shoutout to our amazing problem setters : one_autum_leaf , pajju04 , Pankaj777 , patiljyotiraditya123 , adarshsahu460 , wildwarrior_44.yadavvaishnavi95 ...etc . And mentors ravikjha7 , puriabhijit000 , ganekasar , omkarugale27 and many more who have worked tirelessly to bring this event to life. Your efforts and dedication are what make contests like WCPC 2024 possible.

We can't wait to see your brilliance in action! Best of luck, and may the best coder win!
Regards,
Harshavardhan Bamane
President,
CodeChef WCE Chapter


Full text and comments »

  • Vote: I like it
  • +12
  • Vote: I do not like it

By harsh_bamane17, history, 2 months ago, In English

Codeforces Round 970 (Div. 3)

Problem C.Longest Good Array

  • When I realized that the solution is related to (n)*(n+1)/2, I tried to find the value of n where the absolute diff between the range is d. Where d<=(n)*(n+1)/2 for some n.
  • I decided to precompute all the values of (n)*(n+1)/2 from n=1,2,.....(till where?), I didn't know where I should stop, I thought as it is going to be n^2+n = 2x, then we should consider n till SQRT(1e9) but it gave WA on 1, then I tried 1e2, 1e4 it gave the wrong answer on 1 279159310
  • after increasing and decreasing the limit for n, I started getting my answer getting closer and at n = 44730 279164491 it got accepted!
vl pree;
vl precomp(){
    ll r = 44730;
    vl pre;
    for(int i=1;i<=r;i++){
        pre.pb((i*(i+1))/2);
    }
    return pre;
}
int32_t main()
{
    fastio()
    
    auto solve = [&] () {
        ll n;
        cin>>n;
        ll m ;
        cin >> m;
        ll diff = m-n+1;
        
        auto it = lower_bound(pree.begin(),pree.end(),diff);
        ll ans = it - pree.begin();
        cout << ans+1<< endl;
        
        
    };
 
    int t;
    t=1;
    pree=precomp ();
    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

Can anyone help me with the detailed analysis of the code? Why my n = 44730 worked? and what should be the ideal limit? And also why other people's brute force solution didn't give TLE?

Thank you in advance

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it