diskoteka's blog

Codeforces Round #894 (Div.3) Editorial
By diskoteka, 15 months ago, translation, In English

We would like to thank all the participants who helped us and Codeforces to overcome the 40.000 registered users for the first time

1862A - Gift Carpet

Idea: diskoteka

Tutorial
Solution
Rate the problem

1862B - Sequence Game

Idea: diskoteka

Tutorial
Solution
Rate the problem

1862C - Flower City Fence

Idea: playerr17

Tutorial
Solution
Rate the problem

1862D - Ice Cream Balls

Idea: diskoteka, Ivang

Tutorial
Solution
Rate the problem

1862E - Kolya and Movie Theatre

Idea: pavlekn

Tutorial
Solution
Rate the problem

1862F - Magic Will Save the World

Idea: diskoteka

Tutorial
Solution
Rate the problem

1862G - The Great Equalizer

Idea: diskoteka

Tutorial
Solution
Rate the problem
  • Vote: I like it
  • +96
  • Vote: I do not like it

Comments Comments (93)
| Write comment?
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Code of problem C is giving WA on test 1 and it is written that ai <= n ( There won't be any memory issues since all ai≤n ) but in the problem it is given that ai is upto 1e9

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

    yes but the first element is N and the numbers are sorted in decreasing order so all numbers are at most N.

    → Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why there are only 3 comments, even though the edt was published 8 hours ago?

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

    because the editorial has not been attached to the round so only those people who search the recent actions will get it

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

      To be honest, the solution was not very good.

      → Reply
»
15 months ago, # |
  Vote: I like it +20 Vote: I do not like it

If someone prefers video explanations. Here is my Live Screencast of solving problems [A -> F] (with commentary).

PS: Don't judge me by my current rating :(

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain me the thought process of C, I cannot seem to understand from the editorial :(

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

    Which part did you had trouble understanding ?

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

      The main part

      vector<int> b;
        for (int i = n; i >= 1; i--) {
            while (b.size() < a[i]) {
                b.push_back(i);
            }
        }

      This part while (b.size() < a[i]) why are we doing this?

      → Reply
      • »
        »
        »
        »
        15 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        U can try to draw an example and ovserve, it's easy to find that when you rotate the original shape, the 'height' (the value of a[i]) is the wide(the number of 'i's) of the new shape. just do it by using this code.（maybe my code is clearly enough and U can have a look)

        → Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

When will we get the ratings for the problems we've solved? Im new here and just started giving contests so im sorry i dont properly know how things happen and how long it takes

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

    after maybe 5 hours the main tests will run which will take roughly 2 hours to complete, after that it takes another 2-4 hours for the rating changes to update. You can use an extension like cf predictor to predict your rating change accurately.

    → Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm so bad that I only thought of the dichotomy of O (n log n) for problem C. I'm sorry for my poor English

→ Reply
»
15 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

220231839 Maybe there is another way to solve D.

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    No... sqrt() takes logarithmic time complexity, the same as binary search...

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

      Thanks for your comment! I didn't know this until you told me.

      → Reply
»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

There are many grammar typos in Problem D if someone wants to correct them for future people upsolving it.

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

Why is it giving WA if I use Combination to solve problem D?

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Combinatorics isn't entirely wrong, but requires some observations.

    Take the sample of making 179 different ice creams as an example. If we use a combinatorics approach, we find that; 19C2 = 171 and 20C2 = 190

    However, note that the question asks for 179 to be the exact number of ice creams; therefore 190 is in fact incorrect as there are TOO MANY flavours.

    The work-around is the observation that we can increment the number of flavours by 1 simply by doubling up on a same-kind flavour. Thus, we can use combinatorics to find the lowerbound with distinct flavours, and then double up on each flavour until we end up with the correct answer.

    My solution is attached for clarity: https://codeforces.net/contest/1862/submission/220240409

    Note that you must optimise your starting point to prevent TLE

    → Reply
»
15 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Actually, problem F can be solved using random algorithm, which means you can randomly swap several monsters and defeat them from left to right using water mana first and then fire mana. After approximately 10000 times of attempts, you may pass all the tests, and it runs really fast.

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

    RIP scam failed

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

    Actually, problem F can be solved using random algorithm, which means..

    Hello (from RHEXAOC), don't be upset (too much) about system retesting. I (as well as you) enjoy nondeterministic approaches.

    You basically, changed, so-called, knapsack, which is, taking advantage of natural numbers, to sampling a permutation of monsters. There are too many permutations but the specific projection of that permutations to { yes, no } allowed you to pass preliminary tests. I made a test by myself that your program behaved differently than my program. I would be surprised in other case, that's why.

    As a bonus let me teach you a knapsack, if you wish. Here we, as I said before, take advantage, that a problem is defined on natural numbers. Which allows us to allocate a cell to every sum. So we can store in that sell a maximum cost. In this problem there are no costs just sum.

    bitset<10000 * 100 + 1> btst;
btst[0] = true; // don't forget (I have had forgotten)
for (auto a : aa)
    btst |= btst << a;

    Now we have bits set on every possible sum. In case you don't see: when we don't take any element, we have all sums { 0 }; than we take an element and we have { 0, a }, then we take the next element and sums become { 0, a, b, a + b } and so on.

    In general case of knapsack, for all possible sums, we store a maximal cost, not just one bit. I guess it is somehow possible to do the opposite (for all costs store something...). You might enjoy a math notation of knapsack problem for some purposes of your own. That's it.

    → Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My D question is WA9 at C++20, but the code passes when I hand it over to C++17, can any god help me to explain the reason of this condition, thanks!

C++20

C++17

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this round unrated?

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In D, if x represents 2 balls shouldn't we seek to minimise 2x+y? I am not getting the part with the inequalities:(

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

    what is y?

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

    I think you misunderstood a little bit here (the editorial isn't that clear as well, in my opinion) $$$\newline$$$ We're not minimizing $$$x+y$$$, we're maximizing it. Let assume that we've found a suitable value of $$$x+y$$$, denote this value $$$x+y=m$$$. Then solving for $$$x$$$ and $$$y$$$, we get $$$x=n-\frac{m(m-1)}{2}$$$, $$$y=\frac{(m+1)m}{2}-n$$$ and $$$2x+y=n-\frac{m(m-3)}{2}$$$. $$$\newline$$$ (Keep in mind that $$$m$$$ has to be chosen such that $$$x,y$$$ are non-negative, this will be important later)$$$\newline$$$ Now consider the function $$$f(x)=\frac{x(x-3)}{2}$$$, we want to maximize it. Because $$$f(1)=f(2)$$$ , we can just ignore the case where $$$m=1$$$ and just consider $$$m \geq 2$$$. Since $$$f(x)$$$ is strictly increasing for $$$x\geq 2$$$, we just have to maximize $$$m$$$ now. From $$$x \geq 0$$$ and $$$n=x+\frac{m(m-1)}{2}$$$ we get $$$n\geq \frac{m(m-1)}{2} (*)$$$. $$$\newline$$$ Let $$$m_0$$$ be the largest integer such that that when plugging $$$m=m_0$$$ in $$$(*)$$$, the inequality is true. Our correct answer is obtained when $$$m=m_0$$$ and we can prove it, $$$2x+y$$$ is minimized because $$$m$$$ is maximized, $$$x$$$ is obviously non-negative, $$$y$$$ has to be positive, because if $$$y\leq 0$$$ then $$$n\geq \frac{(m_0+1)m_0}{2}=\frac{(m_0+1)(m_0+1-1)}{2}$$$. $$$\newline$$$ This will contradict our choice of $$$m_0$$$ at $$$(*)$$$ because now the largest such integer $$$m$$$ is $$$m=m_0+1$$$, not $$$m=m_0$$$ and we're done

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

      This proof is quite hard to think during the time of the contest !

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

        I agree! I believe the author created the problem base on a famous result in math that is the function $$$f(x,y)=x+\frac{(x+y)(x+y+1)}{2}$$$ is a bijection from $$$\mathbb{N^2}\to \mathbb{N}$$$. But in the end, it's not a math competition so proofs aren't that necessary as long as you're doing the right things even if you can't prove it :D

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

    just get minimum value x such that x(x-1)/2 <= n
    //number of ways of choosing 2balls from x balls

    now add the diff //repeated balls

    int n; cin >> n;

    int x = sqrt(2 * n);

    if (x * (x + 1) <= 2 * n) x++;

    int diff = n — (x * (x- 1) / 2);

    cout << x + diff << endl;

    → Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me why greedy approach doesn't work for F.
The problem breaks down to checking whether all the items can be filled inside 2 bags of different sizes.
Here's what I thought:
- Sort the items by their weight in descending order.
- Iterate over the items array and put them inside the bag which has more space left.

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

    sin_shark Consider the bag sizes to be — 14 and 10.The items are- 10,8 and 6. If we use greedy approach,1st item goes in bag 1 (new size=14-10=4),2nd item goes in bag 2(new size=10-8=2) ,3rd item will be left as bag are of sizes 4 and 2.

    Instead, we can put 2nd and 3rd item in bag 1 and 1st item in bag 2.(works)

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

      Thanks, but can you give an intuitive idea on why it wouldn't work.

      → Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain to me the first part of the tutorial of G?

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

    Lets say the sorted array is

    a1 a2 a3

    3 2 1

    As you can see we are adding 2 to a2 and 3 to a1.It means the difference between the adjacent elements is reduced by 1 when we add this AP to sorted sequence. This will go on until the maximum difference between the adjacent elements is reduced to zero. Then we will have same elements and we can remove one element.

    Thus the answer is maximum element + maximum difference.

    Hope it helps !!

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

Can anyone tell me, why Online Judge is giving different output than my local machine for following code:

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

using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ull = unsigned long long;
int mod = 1e9 + 7;


void solve(){
	ull n;
	cin >> n;
	ull x = ((ull)1 + sqrt(1 + 8*n))/2;
	ull count = x;
	ull y = 0;
	if(!(x&1)){
		y = x/2;
		y *= (x-1);
	}
	else{
		y = (x-1)>>1;
		y *= x;
	}
	count += n - y;
	cout << count << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);  

    int t = 1;
    cin >> t;
	
    while(t--){
        solve();
    }

    return 0;
}

220249582

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

    Its because you have used sqrt. Use sqrtl for long long integers. You can also use binary search to find the square root.

    → Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, in problem F, the knapsack method that is used, wont the number of computations be of the order 10^8, since knapsack is of time complexity O(N*SUM). How is it accepted then?

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

Problem F: Can some one tell me why isn't the tutorial solution giving TLE as it is order of O(sum*n) i:e O(10^8), or am I wrong...

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

    It is guaranteed that the sum of n over all test cases does not exceed 100.

    So the total time complexity is O(10^8) as u said, and this fits perfectly for the time constraint :D

    → Reply
  • »
    »
    15 months ago, # ^ |
    ← Rev. 3   Vote: I like it -19 Vote: I do not like it

    Because vector<bool> can be understood as bitset, they are both very fast and have a complexity of O(n*sum/64).

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

      vector does not support shift operations thus you can't get 1/64 constant factor improvement which is possible when using bitset.

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

    This is a very common scenario for bitset.

    → Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B,

For b=[4,6,3] why a=[4,6,3,3] is not a valid sequence ?

→ Reply
»
15 months ago, # |
  Vote: I like it -10 Vote: I do not like it

In third question i am getting --> wrong answer Answer contains longer sequence [length = 10000], but output contains 9969 elements. does anyone know how to fix this?

→ Reply
»
15 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

how to do E ques by dp (knapsack maybe dp[currIdx][prevIdx][moves_till_now])

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain as to why commented code is giving TLE for G.

Thanks in advance for the help :).

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody explain that dp state in the solution for problem F?

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

    dp[i] == true means putting weight i into knapsack is possible.

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

    $$$dp[i]$$$ means that if we can get the value i from the sum of any number in s(the vector in the solution).

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

      map<int, bool> ex; what does ex define in your solution

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

        It means the sum exists(can be made by adding any number of monster's value).

        → Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Note that the total strength of the monsters is given to us. Therefore, it is enough for us to spend as much of the available water mana as possible, so that there is enough fire mana left for the remaining monsters. This is a well-known knapsack problem.

Can anyone tell me which well-known knapsack (variation) this is?

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

    0-1 knapsack.

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

      Can you please explain why is it a 0-1 knapsack.
      Where are weights and capacities etc. which are parts of knapsack.
      I can't understand.
      Also, If possible suggest some resources(problems) to learn these types of implicit knapsack.

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

        The total sum of the monsters' strength is the knapsack' s capacity. Each strength of the monster is both its weight and capacity.

        Then in my first solution(220277552) which is MLE dp[i][j] means The maximum amount of capacity that the first i monsters can occupy without exceeding the capacity j.Then I used scrolling array optimization in my second solution(220282293) and AC.

        Then we can get a set including the sum of the strength by selecting any number of monsters from all and adding their strength together.

        Then we can enumerate all the divisions of the sum of the strengths of all monsters into two parts, and use the set we just got to judge whether it can be divided in this way, and constantly update the least amount of time, that is, the answer.

        I don't have good advice on the specific problems of some implicit knapsack, you can search the Internet to find them.

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

          include <bits/stdc++.h>

          using namespace std;

          long long knapsack(long long W, vector& weights, vector& values) { long long n = weights.size();

          vector<long long> dp(W + 1, 0);

for (long long i = 0; i < n; ++i) {
    for (long long w = W; w >= weights[i]; --w) {
        dp[w] = max(dp[w], values[i] + dp[w - weights[i]]);
    }
}

return dp[W];

          }

          long long minTimeToDefeatMonsters(long long w, long long f, vector& monsters, vector& values) { long long totalWeight = accumulate(monsters.begin(), monsters.end(), 0LL); long long low = 0, high = totalWeight / f + 1;

          while (low < high) {
    long long mid = (low + high) / 2;

    long long takenWeight = knapsack(mid * w, monsters, values);

    if (totalWeight - takenWeight <= mid * f) {
        high = mid;
    } else {
        low = mid + 1;
    }
}

return low;

          }

          int main() { ios_base::sync_with_stdio(false); cin.tie(NULL);

          long long t;
cin >> t;

while (t--) {
    long long w, f, n;
    cin >> w >> f >> n;

    vector<long long> values(n);
    vector<long long> monsters(n);
    for (long long i = 0; i < n; ++i) {
        cin >> monsters[i];
        values[i] = monsters[i];
    }

    long long result = minTimeToDefeatMonsters(w, f, monsters, values);
    cout << result << endl;
}

return 0;

          } CAN YOU PLEASE HELP ME , THIS SOLUTION GIVING TLE ON TESTCASE 29 , HOW CAN I OPTIMIZE IT EVEN FURTHER

          → Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain the TC of problem F.

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

problem G is bad because of its TL and n = 1 case

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem D

just get minimum value x such that x(x-1)/2 <= n //number of ways of choosing 2balls from x balls

now add the diff //repeated balls

int n; cin >> n;

int x = sqrt(2 * n);

if (x * (x + 1) <= 2 * n) x++;

int diff = n — (x * (x- 1) / 2);

cout << x + diff << endl;

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why we take min(2e9, 2 * n) in D?

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

    Don't confuse brother you can look at my code or other high rated programmer. My code — 262501894

    → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I misunderstood problem C. In this problem, for a very long time, I was stuck by calculating the total no of diff balls that are required to get different pairs>=n. I was considering that to be my answer, but here I was asked to calculate the minimum no of balls required to get exactly n different ice-creams not more than that. So for this using binary search I calculated the minimum no of different balls required to get the different pairs>=n. Let's say I got res if (res*(res-1))/2==n then this res will be my final answer. Otherwise, I need to do some manipulations. I will go do res--, now this res will make less no of pairs than n find out how much n exceeds this, assume it to be temp. We will be requiring this difference many balls. Hence, in this case our final answer will be (res+temp).

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

can anyone tell that i am correct or not in approach for 1862B- Sequence Game where the output is For each test case, output two lines. In the first line, output a single integer the length of the sequence (2). In the second line, output

integers 1,2,3,, (1109) the assumed sequence that Vika could have written on the first piece of paper. since the output sequence is can be equal to n length so input sequence can also be answer everytime as n <= m <= 2n given in the question, it can be possible that the he thought the same sequence already for Custom Input 1 2 3 4 5 Custom Output 1 2 3 4 5

→ Reply