syedaaliyanx's blog

By syedaaliyanx, history, 4 weeks ago, In English

Problem: https://atcoder.jp/contests/abc220/tasks/abc220_c

A good problem for beginners who want to improve their logic building and learn basic optimization.

The Idea: A straightforward approach is to keep adding elements until the sum exceeds X. But when X is very large, this can be too slow.

Instead, calculate the sum of one complete array. Use integer division to skip as many complete repetitions as possible, then process the remaining elements one by one.

C++ Solution

#include <bits/stdc++.h> 
using namespace std; 


int main() 
{ 
    long long n; 
    cin >> n; 

    vector<long long> a(n); 
    long long total = 0; 

    for (int i = 0; i < n; i++) 
    { 
        cin >> a[i]; 
        total += a[i]; 
    } 

    long long x; 
    cin >> x; 

    long long cycles = x / total; 
    long long sum = cycles * total; 
    long long count = cycles * n; 

    for (int i = 0; i < n; i++) 
    { 
        sum += a[i]; 
        count++; 

        if (sum > x) 
        { 
            cout << count << '\n'; 
            return 0; 
        } 
    } 

    return 0;
}

What Can You Learn? - Why a brute-force approach can be too slow. - How to use maths to skip repeated operations. - How to turn a straightforward solution into an efficient one.

NOTE:

I'm a beginner myself, and I really enjoyed solving this problem, so I thought I'd share it. If you spot any mistakes, feel free to point them out!

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

»
4 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by syedaaliyanx (previous revision, new revision, compare).

»
4 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by syedaaliyanx (previous revision, new revision, compare).

»
4 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by syedaaliyanx (previous revision, new revision, compare).

»
4 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

i solved this a few days ago took me a while to figure out the optimization lol...

»
4 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

good blog!

»
4 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

2009F - Firefly's Queries uses a similar idea

»
4 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

https://atcoder.jp/contests/abc480/tasks/abc480_d also but the size of each group is not the same

Spoiler
»
4 weeks ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

You can optimize the code a bit more. Since you're adding to your total sum of the array 1 item from left to right at a time, you can use your total at each loop to make a prefix sum array (let's call that s). That way, instead of processing the remaining sum one by one, you can use lower_bound() to find the very left position that has a number not smaller than x-sum (with lower_bound() returning an iterator, which you have to minus it by s to get the index). Add the number you just got to the number of cycles and you get the final answer. The similarity between my solution and yours is the cycles counting part, with the time complexity being O(n). The difference lies in the process of counting the exceed elements, mine has a time complexity of O(log(n)), better than your O(n), despite requiring O(n) time complexity to prepare the prefix sum array.

P.S. Maybe it's worse than your process because this solution requires you to do at least n loops to generate the prefix sum array before using the lower_bound() function, while yours require at most n loops to count the exceed elements.