pashka's blog

By pashka, history, 6 weeks ago, In English

1921A - Square

Idea: goncharovmike, prepared: pashka

Tutorial
Solution

1921B - Arranging Cats

Idea: pashka, prepared: ikrpprppp

Tutorial
Solution

1921C - Sending Messages

Idea: step_by_step, prepared: step_by_step, Vladosiya

Tutorial
Solution

1921D - Very Different Array

Idea: Vitaly503, prepared: pashka

Tutorial
Solution

1921E - Eat the Chip

Idea: ikrpprppp, prepared: ikrpprppp

Tutorial
Solution

1921F - Sum of Progression

Idea: Vitaly503, prepared: Vitaly503

Tutorial
Solution

1921G - Mischievous Shooter

Idea: Vitaly503, prepared: goncharovmike

Tutorial
Solution
  • Vote: I like it
  • +111
  • Vote: I do not like it

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

nice E and F

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    в задаче Е в последней строчке написано Элис хотя должно быть Алиса

»
6 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

The problems were nice. I solved A-E in-contest and F about 10 hours later.

For some reason I feel like E was easier to figure out than D.

Also my F submission is in-queue even though it got accepted earlier (?)

»
6 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

prefixsum forces

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

Beautiful problems specially a to f Couldnt figure out g in time I misread a,b both which was abs terrible since the penalty I got from both was almost as twice as usual For A I thought that the squares aren't parallel to the Axis so I wrote a function to validate the squares, the i assumed every possible square and find the max Before I code the last part just reread the ! Question and...

»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why D can use prefix sum without considering absolute value symbols?

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

I reached 1000 and I am so happy. Hope to reach pupil soon!

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

Finally crossed 1500. Had no idea how to solve F.

»
6 weeks ago, # |
Rev. 8   Vote: I like it +17 Vote: I do not like it

I wonder what the intention for the strict limits for F was. The model solution 241944593 runs in approximately 1s, which is around half of the limit, and it consumes almost full memory allowed (1010600 KB).

The very same solution reaches very close at the limit just by swapping the array dimensions that leads to a worse cache hit rate: 241946807, which is what my own solution 241780298 exactly did and barely passed.

It's quite unfriendly with other slower languages, and with only a few trivially inefficient elements it's easy to exceed the time limit as well as the memory limit. It would've made more sense to set a bit more lenient TL and ML as done in problem G.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    It's always a tradeoff. The problem here is that the optimized naive solution, written in good C++ works about 2.5 s, so we cannot extend the TL any further.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That's a lot faster than I imagined. Guess you couldn't really do much about the ML as well as Polygon only allows up to 1024 MB ML.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh, i checked again and I was wrong, we added more tests with many long sequences, and not it works more than 4s, but still pretty close.

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

          indeed the time limit is too tight.
          same code after converting to c++ by gpt works in 900ms whereas it gives tle on test 3 in java

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            Yes, maps and lists are much slower in Java

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            But there are a lot of accepted submissions in Java, actually. Here is one for example https://codeforces.com/contest/1921/submission/243773379

            It's sad that you cannot use standard java containers in problems with such strict time limits, but I don't think we can do anything about it.

            I solved a lot of contests in Java, and at some point I learned how to implement anything using only simple arrays, but it's painful, I agree. That's why I moved to C++ for contests at some point.

            • »
              »
              »
              »
              »
              »
              »
              3 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Thanks for the reply
              Instead of map and arraylists, I used 2d array and the case which was giving TLE now passes in 450ms

»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Solution for G without prefix sums: 241838352.

The idea is very similar to the author's solution with prefix sums over $$$O(nm)$$$, but in this solution the recalculation is done over $$$O(\text{min}(n, m))$$$. In this solution, I go through all the red squares (from the parsing) and subtract them, and I also go through and add all the green squares.

The total time complexity of this solution is $$$O(nm\ \text{min}(n, m))$$$.

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

E was doable

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Fr but never thought E would be just if elses lol

»
6 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

i also had same intution for D as editorial ,but so much less confidence in contest .can anyone please justify why the greedy approach(same as editorial) will work.

@authors

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Always, the difference between minimum and maximum is the max possible to get... Wym

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      it is maximum diff now ,but by taking out maximum such element,we might be reducing maximum difference for second smallest element. you are saying local optimum decision will lead to global optimum(that is exactly greedy),i am asking why it will always result in optimum answer

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Usually proving that swapping any two elements doesn't improve the answer is enough.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    See my submission first before reading the proof.

    The greedy approach can be neatly summarized as choosing the pair that gives the largest absolute difference and then we can pop the two corresponding elements and then we can continue doing the greedy.

    We need to prove two things:

    (1) That the largest distance is either abs(a.front() - b.back()) or abs(a.back() - b.front()).

    Proof. Note that any selected pair a[i] and b[j] have an associated direction from a[i] to b[j] in the number line (either right or left). If the direction is right, we can make the difference larger if we change a[i] to a.front() and b[j] to b.back(). The case is similar to if the direction is left.

    (2) Choosing the largest difference is optimal.

    Proof. Without loss of generality, assume that abs(a.front() - b.back()) gives the largest difference. Assume that the two pairs are (a.front(), b[j]) and (a[i], b.back()) (other cases like when a.front() or b.back() is not paired is trivial). Then by swapping, it's easy to visualize that (a.front(), b.back()) and (a[i], b[j]) is not worse.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can u pls elaborate (2) choosing largest difference is optimal "Assume that the two pairs are (a.front(), b[j]) and (a[i], b.back())" what are we assuming

      Then by swapping, it's easy to visualize that (a.front(), b.back()) and (a[i], b[j]) is not worse. After swapping what is not worse than what?

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

The Solution Code of D may meet some display problem?

On my view, there are some — in the brackets of abs(), they look like:

c[i] = b[m — n + i];
s += abs(c[i] — a[i]);

I don't know if it's an issue with my browser.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    actually the &mdash is the minus sign -

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what does that line mean c[i] = b[m — n + i]; is it b[m-n+i] or what is it

      • »
        »
        »
        »
        6 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yup

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Me too! It's confusing!!!

»
6 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Can someone explain why are we taking d=sqrt(q) ?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    We want to minimize $$$nd + qn/d$$$, When we increase $$$d$$$, the first part will increase, and the second part will decrease, and the minimal point will be when they become equal: $$$nd = qn/d$$$, from that we can get $$$d=\sqrt{q}$$$.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      We can also sort queries by $$$ (d,s \mod d) $$$, and for all queries with same $$$ (d,s \mod d) $$$, we preare the prefix sum using items : $$$ a_{s \mod d}, a_{d+s \mod d},a_{2 \cdot d+s \mod d}, \cdots $$$, which are $$$ \frac{n}{d} $$$ items in total. For some fixed $$$d$$$, $$$d$$$ queries would be needed to make prefix sum calculation cover the whole $$$n$$$ array. Worst case is when $$$ 1+2+3+ \cdots + x=q$$$, get $$$x \approx \sqrt q $$$ , so the total time complexity of prefix sum preparing is $$$n \sqrt q $$$.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I get really stuck when it comes to understanding the problems so deeply with respect to constraints.

»
6 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Can Problem D be solved with dynamic programming approach? dp[i][j] = maximum diff when a[i] is paired with b[j].

transition: dp[i][j] = abs(a[i]-b[j])+max value from dp[i-1] (other than dp[i-1][j] as jth element is paired with current element.)

return max value from dp[n-1];

is this approach correct?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also thought about dp but finding max value from dp[i-1] takes O(m) or I can not come up with better way to do it, overall it will be slow.
    Personally I solved it by sorting both arrays and using two pointers on each of them and taking values by greedy approach.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I thought something like this .We will need to keep 2 largest values from the dp[i-1] array . As mostly we will use largest value and if the currently chosen index is equal to index with greatest in dp[i-1] then we will use the second largest value. We can maintain this values in such array maxValue[n][2] and update it while processing dp states.

»
6 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

почему моё решение 241780647 использует multiset но в тегах не было добавлено структуры данных?

»
6 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Editorial is not attached as "Tutorial" in problem statement page yet. May it would be fixed.. UPD: Fixed Now..

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

F Video editorial + Live Coding (English): https://youtu.be/mJVq_nW8iQk

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

Can someone help my find out why my submission to E gives WA?: expected: 'DRAW', found: 'BOB'

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    why you are doing wins==true in if(w — ya — 1 <= dh /2) and in else aslo ? in else there will be draw

»
6 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

who setted this problem G and why

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +19 Vote: I do not like it

    Sirs teaching Englishs. 😂

    So spreading the awareness xD
»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

After 18 contests, I've finally reached specialist, and so far, the only active specialist in Seattle! :)

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

I have an alt. sol for F that uses memoization.

Suppose we split the array into $$$d$$$ subsequences of increment $$$d$$$ for every $$$d$$$ from $$$1$$$ to $$$n$$$.

Ex: Original array is $$$[1,2,3,4,5]$$$

$$$d = 1: [1,2,3,4,5]$$$

$$$d = 2: [1,3,5],[2,4]$$$

$$$d = 3: [1,4], [2,5], [3]$$$ (You get the idea)

If we can generate both the prefix sums and the partial sums of the values multiplied by their index (eg $$$[1,3,5]$$$ becomes $$$[1\cdot1, 1\cdot1 + 3\cdot2,1\cdot1 + 3\cdot2 + 5\cdot3] = [1,7,22]$$$.

We can use these two precomputed arrays to evaluate the queries efficiently. However, precomputing all of these will be too slow, instead, we can create them and store them as we process queries since we don't need to precompute every subsequence.

To store them, we would just need something like a map, the key would be a pair $$$(d,s\%d)$$$ where $$$d$$$ is the increment and $$$s\%d$$$ represents the first element's index of the subsequence.

The worst case is that for every query, we have to create both types of prefix sum arrays for the largest, not-yet-computed sequence. It should be clear that given array of size $$$n$$$ and $$$n$$$ queries, the total iterations should be around $$$O(n\sqrt{n})$$$ (or plus a log factor depending on which map).

My code: 241999941 (which uses custom hash + unordered map)

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem c, doesn't the phone lose charge at 0 moment and also will the phone lose charge after it sends a message or before?

could someone explain?

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

Can please tell me why is this submission giving a TLE for Problem F? (Time complexity: $$$O((N + Q) * sqrt(N))$$$)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Don't declare vectors(prefix sum) for every test case, make them of fixed size [10^5+1][320]

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

I have a nice greedy solution to D which just selects the largest possible distance at every iteration until all elements in $$$a$$$ have been paired, but I don't have a proof.

Code: 242031960

Can anyone prove it?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    I have also used this method during the contest.

    In sorted $$$ a_1, a_2, \cdots a_n $$$ and sorted $$$b_1,b_2, \cdots b_m$$$ , WLOG, let us assume max diff value is $$$ | a_1 - b_i |$$$. Obviously $$$i$$$ could only be $$$1$$$ or $$$m$$$ .

    If $$$i=1$$$,

    • when $$$b_1 < a_1, |a_1-b_1|<|a_n-b_1|$$$ ,
    • when $$$b_1 > a_1, |a_1-b_1|<|a_1-b_m|$$$ ,
    • so $$$i \neq 1$$$.

    If $$$i=m$$$,

    • when $$$b_m<a_1, |a_1-b_m|<|a_1-b_1|$$$,
    • so it must be $$$b_m>a_1$$$ .

    Assume in optimal solution, $$$b_j$$$ paired with $$$a_1$$$ ,

    • if $$$b_m$$$ is not paired with any value in $$$a$$$, we can move $$$a_1$$$ from pair with $$$b_j$$$ to $$$b_m$$$ to get a better solution.

    • If $$$b_m$$$ is paired with some $$$a_k$$$ , since $$$a_1<a_k , b_j<b_m , a_1<b_m , |a_1-b_j|<|a_1-b_m|$$$ , it can be shown that $$$|a_1-b_j|+|a_k-b_m| \leq |a_1-b_m|+|a_k-b_j|$$$.

    So, pair $$$a_1$$$ with $$$b_m$$$ must be in some optimal solution.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks. You motivated me to prove it myself. I came up with a not-so-elegant proof with the same outline as yours

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

Not able to figure out whats wrong with my solution https://codeforces.com/contest/1921/submission/242087071

»
5 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Don't understand the equations in F at all. Feels like editorial has been written for someone who already understands the solution.

"The key idea is that we know how to calculate the sum (i−l+1)⋅ai for l≤i≤r fast – we need to calculate all prefix sums i⋅ai and ai for 1≤i≤k, then take the difference between the r-th and (l−1)-th of i⋅ai and subtract the difference between the r-th and (l−1)-th multiplied by l−1"

This certainly could have been explained in a better way.

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

Thanks for the editorial!

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

Can somebody explain solution of problem E to me? I am just gonna type what I understood so somebody else won't have to type much.

From what I understood, Alice can only win when the distance is odd and vice versa(This part was intuitive). Draw happens when loser tries to dodge winner in the game as he knows he is gonna lose. So to draw losing player can run to either extreme left or right and If there's enough distance in either left or right they successfully dodge the winner.

Is this correct or am I missing something? Beside calculating all of this is too much as well.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Correct. They will meet on some row which is predefined. At the meeting junction if its alice turn then bob has to run for draw or alice win or vice versa.It has comments

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

I can't understand what is the code doing in problem D like why are you using this code with some define lines that are not even written , please don't forget that there are some beginners here I can't figure out what is mdash

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Somebody in comment already said that its just minus. Here's the link.

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      did you understand the code because I'm trying for more than 5 hours and reached nothing and I feel so tilted, the idea is so complicated , or maybe I'm just so dumb

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        There's a youtube video for this entire contest. It's in english by some master or cm. Link.

        NO, I couldn't understand the solution they have given in editorial.

        I'll try to explain how I did it.

        Look from array b you want to choose n integers and arrange it in a order such that diff is maximum as stated in problem.

        Now for every position if you think about it there are only four options.

        First this is something for sake of notation. min of array a = mna, max of array a = mxa min of array b = mnb, max of array b = mxb

        Now just create all 4 pairs using above numbers let's say d1 = abs(mna — mxa), d2 = abs(mna — mnb) and so on.

        Now you just have to pick whatever is maximum.

        So if you keep both a and b sorted and create 4 pointers each pointing to above mxa, mxb, mna, mnb. You can increment decrement pointers based on which one is maximum.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          nice explanation thanks but there should be no point of trying (mna-mnb) and (mxa-mxb) and the other two will be enough right ?

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yeah those two cases are useless.

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

how did so many people solve D ,like is there any standard problem for it or I'm just bad at this because even after reading editorial and tracing almost 10 different codes I still don't think that I can come up with this my self at all, and with the problem being 1100 it's more frustrating

  • »
    »
    11 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    DP/greedy problems are usually difficult to prove but the solutions are rather intuitive and rely largely on observation. After solving lots of DP/greedy problems, you will start to observe the patterns in these types of problems.

    Basically the solution herein lies in the fact that we know the maximum sum is formed by using the largest/smallest elements in b.

    To maximize the sum, greedily we want to pair largest b elements with smallest a elements, and vice versa because doing so, we get larger absolute differences.

    The first idea is to greedily pair elements one by one such that their absolute difference is the largest. However, you may have noticed this solution does not always work.

    The reason lies in the non-greedy structure of this problem, pairing something affects the maximum sum of absolute difference of remaining pairs in the future, and another pair which is not chosen greedily may be better.

    Rather than forming the maximum sum, we could instead bruteforce over all possible maximum sums and update ans = max(ans, s). We know we could form the maximum sum by pairing elements of a with k largest elements and n-k smallest elements in b, for some k.

    For simplicity's sake, we will use words and slowly transition into using variables.

    After sorting a and b, we have..

    a = smallest, smaller, .., smaller, .. largest
    b = largest, larger, .., larger, .. smallest
    

    Let's start by pairing a with the n smallest elements in b. There are many ways to arrange these in some order such that we get the maximum possible sum, but we can easily observe that the optimal order is always to pair the smallest with largest, for each element.

    |smallest - larger| + .. + |largest - smallest| >=
    |smallest - smallest| + .. + |largest - larger|
    

    thereby using the corresponding indices,

    |a[0] - b[m-n]| + .. + |a[n-1] - b[m-1]| >=
    |a[0] - b[m-1]| + .. + |a[n-1] - b[m-n]|
    

    With similar logic, we iteratively form the next sum by replacing the pair a[0],b[m-n] with a[0],b[0] and so on. We can easily calculate this updated sum in O(1) using S = S - |a[i]-b[m-n+i]| + |a[i]-b[i]|

    Thus we form the possible maximum sums as such,

    S[0] = |a[0] - b[m-n]| + .. + |a[n-1] - b[m-1]|
    S[1] = |a[0] - b[0]| + (S[0] - |a[0] - b[m-n]|)
    S[2] = |a[1] - b[1]| + (S[1] - |a[1] - b[m-n+1]|)
    .
    .
    .
    S[n] = |a[n-1] - b[n-1]| + (S[n-1] - |a[n-1] - b[m-1]|)
    

    and thus, ans = max(S[0], S[1], .., S[n]).

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

Hello everyone. I am having trouble with problem F. I understand that its a standard problem but the part where we need to hop by d steps is making it hard for me to understand.

I have a scenario can someone please explain on this. d = 5, k=6, s=3

Here the sequence required is: a3 + 2a8 + 3a13 ... 6a28

I have 2 series which can be computed in O(1): S1 = a1 + a2 + a3 ... an S2 = a1 + 2*a2 + 3*a3 ... n*an

How can I get the required sum if someone is available to dry run it.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Precomputed prefix sums starting from index 3 with step size 5:

    ps1 = a3 + 2a8 + 3a13 + 4a18 + 5a23 + ...

    ps2 = a3 + a8 + a13 + a18 + a23 + ...

    Let's say you want to compute the sum for 3 elements starting from index 13:

    a13 + 2a18 + 3a23 = (3a13 + 4a18 + 5a23) -2*(a13 + a18 + a23)

    You can get get these two parts from prefix sums ps1 and ps2.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    There's a youtube video for this entire contest. It's in english by some master or cm. Link. Actually he just explains brute force approach so don't waste your time on it.

    Brute force approach is easy to figure out but I am not able to understand editorial. All I understand is they are multiplying it by some value in order to reduce time complexity when running the queries. What is even the intuition behind the solution?

    Can somebody explain the intuition or Is it just way above my level so I should leave it?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Maybe putting summed indexes this way helps:

    1 2 3 4 5 6
      2 3 4 5 6
        3 4 5 6
          4 5 6
            5 6
              6
    

    If you need sum from 4 to 6 then you have to subtract triangle 1..3 and rectangle of top 3 lines which is (4+5+6)*3 = (sum without multiplication) * (s/d)

    After some optimisations you get answers quite fast.

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

243976867 that was tight

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can problem D be solved with using two pointers?

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

c[i] = b[m — n + i]; anyone???

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

247587440,the solution of D,You can use a two-pointer to solve this problem