awoo's blog

By awoo, history, 2 months ago, translation, In English

1809A - Garland

Idea: BledDest

Tutorial
Solution (Neon)

1809B - Points on Plane

Idea: BledDest

Tutorial
Solution 1 (adedalic)
Solution 2 (adedalic)

1809C - Sum on Subarrays

Idea: BledDest

Tutorial
Solution (BledDest)

1809D - Binary String Sorting

Idea: BledDest

Tutorial
Solution (Neon)

1809E - Two Tanks

Idea: BledDest

Tutorial
Solution (awoo)

1809F - Traveling in Berland

Idea: BledDest

Tutorial (Neon)
Solution (awoo)

1809G - Prediction

Idea: BledDest

Tutorial
Solution (BledDest)
  • Vote: I like it
  • +139
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

What is the purpose behind setting limits such that (na + nb + ab) logn solutions fail E?

I have tried to optimize it, i got it down to 2.5s in a mashup with adjusted limits, couldnt get it to pass.

The problem was already quite hard enough without the limits, imo n<=1e3 wud be much better.

Good contest otherwise though, i liked both C and D

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    If you let $$$n = 1000$$$, squeezing $$$O(nab)$$$ with some constant optimizations into TL feels very probable

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      That was just an instance, even n = 5000 allows both my solutions (segment tree/bs + sparse) to pass (i think though it might be tight for seg)

      Especially sad for us since a slightly different idea and the same complexity passes due to good constant.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My (na + nb)logn solution seemed to pass pretty comfortably: https://codeforces.com/contest/1809/submission/198874838.

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

      Your solution has a completely different idea (and is similiar to the actual idea i guess)

      I will explain my solution : If each operation moved the maximum amount it could, the problem was simple, so lets try to simulate each process for a certain starting position till the next time we dont move the maximum amount. This can be done easily with a segment tree.(or bs + sparse table) If we memoize the values, this becomes O(na + nb + ab) logn Reasoning : there are atmost 2*na + 2*nb + ab states because after each operation, because each simulation is run either at a starting position(ab of them) or when atleast one tank is either empty/full (2na + 2nb)

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

    I don’t even know how to optimise my solution more to get it to less than 2 seconds, it’s at 7 seconds mark.
    the issue is that it feels that it may pass, so we waste time coding it

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wait, really? $$$10^7$$$ times log operations (also including the fact that this logarithm comes from segment tree, so the constant is big) feels passable in 2 seconds? Can you show any problems where it actually passes under those constraints?

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        Yeah it is very tight i agree, 1e7 * 2 * log (1000) * segtree constant = 2e8 * segtree constant, so mathematically I didn’t feel like it’d certainly TLE

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        1) you do not need a segment tree, you can use binary search + sparse table 2) the log factor is a logn, which is around 13, so its about 2.5 * 10^8 complexity, not unreasonable 3) my recursive segment tree runs in 4s which is only twice the TL. If i could write iterative segmemt tree, i am pretty sure it would pass

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        https://codeforces.com/problemset/problem/1523/H Intended solution complexity : 4e4 * 900 * log in 2s If i am not mistaken thats 3.6e7 log.

»
2 months ago, # |
  Vote: I like it -7 Vote: I do not like it

I tried every combination for problem C after setting the number 2 and it got accepted. Here is the CODE : 198939113

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your code is not understandable, Could you explain your idea?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Its simple i just take 2 and created an array of just 2 till the no. of positive subarrays in it is <=k then there can be two cases :

      1) no. of positive subarrays = k this is the best case so we will just put -1000 on the rest of the places.

      2) No. of positive subarrays>k .Then i just removed a 2 then look for a negative element which satisfy the condition no. of positive subarrays=k by brute force.This will have at max = 30*30*1000=9*10^5 operation for the worst case. which is under the time limit.

      P.S: i think i just poorly implemented it but yk thats just the first thing which came to my mind and it worked XD

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me prove my solution for C? I thought my solution was an elegant linear time solution but it did rely on one claim I was only probably sure was true. My claim was that: for any number 0 <= k <= n*(n+1)/2, and with access to the numbers 1...n, we can always greedily choose the largest n that fits and add it to the sum until we reach k. If this claim is true, then we can solve C using the following strategy:

Initialize an array of length n, all 0s

If we "set" index i of the array, then it will create n-i positive subarrays. We set the largest indices that fit into the sum of k.

Now we iterate through the array backwards and set the values such that the set indices make every subarray ahead of them positive and the unset indices make every subarray ahead of them negative.

Solution: 198783142

I didn't prove that we can always make k greedily using the numbers 1...n, but I thought it might be true because it felt similar to the Div 4 G problem.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "If we "set" index i of the array, then it will create n-i positive subarrays". I'm pretty sure this is not true. For example, array 00100 has exactly 5 positive subarrays. However, I think that you probably wanted to say that if I turn on all the bits from 0 to i-1, then turning i on would add exactly n — i — 1 positive subarrays.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem E becomes more interesting if instead of requesting all (c,d) pairs we only request q pairs. Limits like n<10^4, a+b<10^18, q<10^6

»
2 months ago, # |
  Vote: I like it +34 Vote: I do not like it

1809F - Traveling in Berland could be solved in $$$O(n)$$$ by using 2 pointers

We can duplicate $$$a, b$$$, st $$$a[i + n] = a[i]$$$ and $$$b[i + n] = b[i]$$$

Suppose we are solving for $$$k$$$ so our path starts at $$$k$$$ and ends in $$$k + n$$$

For example we have $$$x, y, z, \dots, last$$$ st $$$k \le x \le y \le z \le \dots \le last \le k + n$$$ and $$$b[x] = b[y] = b[z] = \dots = b[last] = 1$$$

We can split path into $$$k \rightarrow x \rightarrow y \rightarrow z \rightarrow \dots \rightarrow last \rightarrow k + n$$$

For points $$$x, y, z, \dots$$$ we can use 2 pointers. For example in point $$$x$$$ we will buy $$$\min(len[x \rightarrow y], limit)$$$ if $$$limit < len[x \rightarrow y]$$$ we will buy more in other points with cost 2

For $$$k \rightarrow x$$$ and $$$last \rightarrow k + n$$$ we can compute naively. Total complxity $$$O(n)$$$ 198830497

»
2 months ago, # |
Rev. 3   Vote: I like it +29 Vote: I do not like it

Graph explanation of E: (consider for all cases of (c, d) with same value of c+d)

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

    Agree that nO(log n) is overkill.

    I used a similar (the same) idea (199142190) — in gas station i with $$$b_i=\$1$$$ (let's call it 1-station) you always fill the minimum of full tank, and fuel required to reach the next station j that is 1-station or j is final.

    You could pre-compute the amount you fill (call it $$$w_i$$$) at the 1-station i. Given starting position start, the total you fill at all 1-stations is $$$\sum(w_i, i \in 1-station) - w_j + FilledAtj$$$, here j — is the last 1-station on a journey started at start.

    So it is enough to keep track of the last 1-station on a journey and compute filled amount at this station — easy given that the end of journey is at start.

    P.S.: Obviously your answer for each journey is 2 * Total Fuel Required — Total Filled At 1-stations.

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

if anyone solved D using dp, can you pls tell me the approach?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I just memoized all states using DFS. If we are at a position and it is a 1, we can either continue or delete it and incur the cost. There is a third option of swapping with the number in front of it if it is a 0 and we have no other 1's to the left. If we are at a position and it is a 0, we can delete it and incur the cost. If there are no 1's the left, we can either continue or swap it with the number in front of it. The memoization will look like memo[pos][has_0][swapped] for each state

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      wouldn't the third option need another condition where the next element (0) to be swapped has to be the last 0 in the string? otherwise we will have to swap the current element (1) more than one time, which would be costlier than just deleting it?

      also could you explain in terms of recurrences/subproblems if possible, i'm sorry, i am unable to understand your method completely.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    Let $$$dp_{i, j}$$$, be the cheapest way to process the first $$$i$$$ characters of the string with the following states:

    • $$$j = 0:$$$ The modified string is of the form $$$\dots 0$$$.
    • $$$j = 1:$$$ The modified string is of the form $$$\dots 01$$$.
    • $$$j = 2:$$$ The modified string is of the form $$$\dots 11$$$.

    You can see the transitions in more detail here: 198854887.

    Or without array<int, 2>: 198995188.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why do we work with length prefix 1 in the same way as with prefixes of greater length? 2 out of 3 configurations require 2 known characters

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

    I defined $$$d[i][c]$$$ as the solution for a string of length $$$|s|-i$$$, where the first character is exactly $$$c$$$, and the suffix is exactly the last $$$|s|-(i+1)$$$ characters of the original string. If the indexing confuses you, think about how we can fill $$$d$$$ from right to left (starting with $$$i=n-1$$$ and moving down to $$$i=0$$$).

    Now, $$$d[i][0]$$$ is easy; it is equal to $$$d[i+1][c]$$$ where $$$c = s[i+1]$$$. The challenge is with $$$d[i][1]$$$; there are 3 options:

    1. Deleting this leading $$$1$$$ and just solving for what remains; this is equal to $$$(10^{12}+1) + d[i+1][c]$$$ for $$$c=s[i+1]$$$.

    2. Keeping this leading $$$1$$$; observe that in this case, any $$$0$$$ to the right of this $$$1$$$ should be deleted. This gives us $$$(10^{12}+1) \times (\text{# of 0's in }s[(i+1)..])$$$.

    3. Swapping the leading $$$1$$$ with $$$s[i+1]$$$. If $$$s[i+1]=1$$$, nothing has changed, and we can solve with options 1 and 2. But if $$$s[i+1]=0$$$, then we have $$$10^{12}+d[i+1][1]$$$; essentially, we are solving for the string $$$s' = 1 \cdot s[(i+2)..]$$$ ('$$$\cdot$$$' is the concatenation operator).

»
2 months ago, # |
Rev. 2   Vote: I like it -49 Vote: I do not like it

I actually didn't like the tutorial for task B

It's way too complicated for beginners

O(1) Solution

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
int32_t main() {
	int T;
	cin >> T;
	while(T--) {
	    int N;
	    cin >> N;
	    int r = ceil(sqrt((double)N)/2);
	    while(4*r*r < N) r++;
	    int mx = 2*r - 1;

	    r = ceil((sqrt((double)N)-1)/2);
	    while(4*r*(r+1)+1 < N) r++;
	    int mxx = 2*r;

	    if(N == 1) cout << "0\n";
	    else cout << min(mx, mxx) << "\n";
	}
	return 0;
}

O(logN) Solution

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
int binarySearchEven(int N) {
	int start = 1, end = 1e9, r;
	while(start <= end) {
		r = start + (end - start)/2;
		if(N > 4*r*(r+1)+1) start = r+1;
		else end = r-1;
	}
	return start;
}
 
int binarySearchOdd(int N) {
	int start = 1, end = 1e9, r;
	while(start <= end) {
		r = start + (end - start)/2;
		if(N > 4*r*r) start = r+1;
		else end = r-1;
	}
	return start;
}
 
int32_t main() {
	int T;
	cin >> T;
 
	while(T--) {
	    int N;
	    cin >> N;
	    
	    int s = 2*binarySearchOdd(N) - 1;
	    s = min(s, 2*binarySearchEven(N));
 
	    if(N == 1) cout << "0\n";
	    else cout << s << "\n";
	}
	return 0;
}
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try to format the code while commenting.
    Otherwise it becomes unreadable, and will result in huge downvotes.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It appeared in order, but after posting it took a random configuration... Don't know why

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        There is an option while commenting, if you want to write source code.
        You can use that.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        sqrt() method isn't O(1) . so your O(1) solution is not really O(1).

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

I solved F after the contest with a solution that is O(n) 198883707, then noticed that each b_i is limited to either 1 or 2. The 1 or 2 constraint is essentially not required and would only slightly simplify the code.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain your solution?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      First detect consecutive sequence of cities with non-descending fuel cost per liter. A round trip started at a city not in the sequence would visit all the cities in order from begin to end. A round trip started at a city within the sequence would visit the suffix cities and later all the prefix cities in the sequence. In either cases, because the fuel price is non-descending, it is always optimal to purchase as much fuel as sufficient to reach the end of the sequence limited to the tank capacity of course.

      For each such sequence [B,E], we run DP to compute the pre[] and suf[] array where pre[i] is cost to reach i from B and suf[i] is the cost to reach E+1 from city i. Such computation is O(M) where M is the length of the sequence. I will skip more details to compute the pre and suf array.

      Once we have all the individual sequences handled, for each city i, its round trip cost includes the whole cost of all other sequences it does not belong to, plus pre[i] + suf[i]. It takes O(N) to compute the value for all the cities as answer. Overall the complexity is O(N).

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

    Agree, the F has a solution with complexity O(n). No need of graphs, binary search or any complex data structures. Just calculate the lengths of suffixes and prefixes for some city with the fuel cost of 1 and then for each city the travel cost is the sum of travel to this city and from this city to the starting one.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain B's given test case? Why is answer for 975461057789971042 987654321? I am sure it should be 987654320.

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

    the answer would have been 987654320 if the input was 975461057789971041 (1 less than the current input)

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Use 'sqrtl' to find the square root. The input is of the order 10^18 so sqrt will give precision errors. The exact square root of 975461057789971042 is 987654321.000000000506249999, ceil of that minus 1 is the final answer ~ 987654321.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks! I was using sqrt! Learned something new today.

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    There are 4 * m points (x, y) that satisfies |x|+|y| = m for m >= 1. The diagram below shows points 4 + 12 = 16 points for m = 1 and 3. The total number of points for m = 1, 3, 5, ..., 2 * k — 1 is 4k^2. For k = 493827161, the value is 975461059765279684 which is greater than 975461057789971042, so the answer should be <= 2k-1 = 987654321.

                .
                o
             o  .  o
          o  .  o  .  o
    .  o  .  o  .  o  .  o  .  .
          o  .  o  .  o
             o  .  o
                o
                .
    

    An illustration that 987654320 won't work: if we use m = 0, 2, 4, 6, ..., 987654320, the total number of points is 1 + 4 * (2 + 4 + ... + 987654320) = 1 + 987654320^2 = 975461055814662401 which is one less than the required 975461055814662402 in your example.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you keep points on even (|x| + |y|) then it starts from (0, 0) and goes like (1, 1) , (-1, -1), (1, -1), (-1, 1) that is it form a pattern where you get first point on (0, 0) and next points on a cube with vertices |x| = 1 and |y| = 1 and so on...

    It makes formula as 1 + 4*2 + 4*4 + 4*6 + 4*8 + . . . . = 1 + 4*2*(1 + 2 + . . .) = 1 + 8*(Sum of first r natural numbers) = 1 + 8*(r*(r+1)/2) = 1 + 4*r*(r+1)

    If you keep points on odd then it starts from (1, 0) , (0, 1) , (-1, 0) and so on which makes formula as 4*1 + 4*3 + 4*5 + . . . = 4*(1 + 3 + 5 + . . .) = 4*(Sum of A.P.) = 4*r*r

    Solve the inequality for both the formula

    N <= 1 + 4*r*(r+1)

    N <= 4*r*r

    You could either solve for r in terms of N or do Binary Search on the inequality either way you will have to find the minimum of the two possible arrangements of odd or even locations

    Remember for even answer will be 2*r and for odd answer will be 2*r — 1 as points with 2, 4, 6,... were 2*r for every natural no. and points with 1, 3, 5,... were 2*r-1 for every natural no. in the above formula you could verify...

    In both the ways the answer will be 987654321

    I have posted the solution in the above comments, scroll up to check it...

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What about this solution : 198977706

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It's the same thing, only difference is that I have mathematical proof to what I did in code, whereas your program is the best optimized solution, but a beginner will feel, it's observation, but no, it's mathematically correct too...

»
2 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

A simple solution for task B is just print " (int) sqrt(n-1)" ;)

your have to define int to long long int.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i think my solution for C is not bad 198788496

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have two almost similar logic solution for problem B, one is failing while the other one is working.

Failing one- https://codeforces.com/contest/1809/submission/199048077,

Working one- https://codeforces.com/contest/1809/submission/199048367

Could someone help understand what's going wrong here? Also I see that for c++ sqrt(n-1) works while not for JAVA, why is that so?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    there are precision errors. in java , the number is converted to double before taking the root. eg — root 25 can be 4.999 and the int of this would be 4 , so we need to add this line while(x * x < n) x++; so if there is any precision error it would be corrected

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Another possible solution for D:

  • Start by skipping all leading 0's and trailing 1's, because these 2 parts are already sorted and we don't have to worry about them, let left be the index of the 1st '1' that we encounter from the left and right — the index of the first '0' that we encounter from the right. It is easy to see that if right < left then the string is already sorted.
  • Count the total amount of 0's and 1's in substring s between left and right.
  • We are going to iterate over s from right to left and each time we are going to count the consecutive number of 0's and 1's, meanwhile decreasing the total amount of 0's and 1's. Each time after we have iterated over 2 segments of consecutive 1's and 0's we have several options:
  1. Let's consider keeping current amount of 0's and deleting current 1's, then this would mean that we also have to get rid of all 1's left up to left, so the string would become sorted, this way we can estimate the answer immediately.
  2. If we delete the current amount of 0's then we have two more options: we would have to delete all 0's left in s up to left or we can keep the 0's and get rid of the 1's instead. This way we get 2 more estimates of our answer, also we are going to keep track of all possibly deleted 0's for future estimations.
  3. Extra case: if current amounts of 1's and 0's are both equal to 1 and the total left amount of 0's is not less than amount of 1's then we get another estimate for our answer: deleting all left '1' with previously deleted 0's and adding a cost for one swap.

Iterating over s from right to left each time we assign our answer the minimum value of 3 + 1 possible estimates and our current answer.

Submission: 199079054

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

O(1) solution for B:

Solution: If N is a perfect square then the answer is √N — 1 and otherwise it's just √N

198856454

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you can just calculate floor(sqrt(N-1))

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

1809G is similar to 1437F, although the constraint of 1809G is tighter.

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

In problem D, how do they determine that it is optimal to have at most one delete operation.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem D, suppose a case is 111000 and we were to sort it. According to my understanding this case would take the cost of 3 * (10^12 + 1) because you could either remove the three ones or zeros but I think the answer the judge is providing is 2 * (10^12 + 1). Is there some optimization I am missing?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Perhaps few person remember that EDU rounds may reuse old problems.

Actually 1809E - Two Tanks is a resemble of an old task OneDimensionalRobot from SRM 608 authored by rng_58.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://youtu.be/xvyXv1IO7yg

Video sols for A,B,C

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

F can be solve in O(n) instead of O(nlogn). You can preprocess (not sure how to say it, you get the idea) the prefix and suffix of every position with gas price 2, then calculate the answer of any city with gas price 1.
The difference between different starting points will be: the concecutive price 2 cities that got seperated by the starting position. Just calculate the offset with prefix and suffix then you get the correct answer.
199636012

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is D solvable if it was given a permutation instead of a binary string?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I get Wa5 because of I mul 1e12 and I dont realize it, terribly

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem C if we were asked to construct array of size n with exactly k subsequences with sum positive?

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

can anyone recommend problems similar to E