awoo's blog

Educational Codeforces Round 146 Editorial
By awoo, history, 6 months ago, translation, In English

1814A - Coins

Idea: BledDest

Tutorial
Solution (awoo)

1814B - Long Legs

Idea: BledDest

Tutorial
Solution (awoo)

1814C - Search in Parallel

Idea: BledDest

Tutorial
Solution (BledDest)

1814D - Balancing Weapons

Idea: adedalic

Tutorial
Solution (adedalic)

1814E - Chain Chips

Idea: BledDest

Tutorial
Solution (BledDest)

1814F - Communication Towers

Idea: Neon

Tutorial
Solution (Neon)
  • Vote: I like it
  • +68
  • Vote: I do not like it

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

I know it isn't an "issue", but in problem B the variable names are a,b while here they are n,m

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

In problem B, My thought was ternary search since the values tend to decrease at first and then increase but the problem I faced is that around the middle of the curve, the values don't necessarily keep changing in the same way (X-axis for max K length and Y-axis for cost)

As you notice some irregularities, can this be handled using only ternary search or by iterating over a much smaller range of K's?

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

    I tried a weaker 1-D case (go from 0 to n)
    there $$$\sqrt{n}$$$ seems to be the best leg size. (floor or ceil I don't remember)
    (somewhat related to the fact that $$$x + a/x$$$ minimizes at $$$x = \sqrt{a}$$$ and
    similar is the case with $$$x-1 + \lceil n/x \rceil$$$)
    But ofc the problem is going up a notch to the 2-D case.
    (new to code-forces and I don't know how to write in laTex etc, pardon me for that).

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

problem EF video solution for Chinese：

BiliBili

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

Can anyone please elaborate on the solution of Problem D, please?

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

First question can be directly solved using concept of LDE Let g = gcd(2,k) If(n%g == 0) cout<<yes<<endl; Else cout<<no<<endl;

Am i wrong ???

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

A can be solved by just checking parity of n and k 

if (n % 2 == 0 || k % 2)
     yes
    else no
→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please give an explanation of this? Also, what is meant by parity check?

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

      parity means it's odd or even.

      if n is even, it can be made with 2 coins.

      if n is odd then k must be odd as well otherwise it is not possible.

      example

      For a more formal proof

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

    nice solution. It takes me some time to understand your solution. How can I improve my problem solving skills?

    → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it 
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
void solve();
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
}
void solve()
{
    long long n, s1, s2;
    cin >> n >> s1 >> s2;
    long long r[n];
    vector<pair<long long, long long>> v;
    for (int i = 0; i < n; i++)
    {
        cin >> r[i];
        v.push_back({r[i], (i + 1)});
    }
    // for (auto &it : v)
    //     cout << it.first << " " << it.second << endl;
    sort(all(v));
    long long tc1 = 0;
    long long tc2 = 0;
    vector<long long> lista;
    vector<long long> listb;
    for (int i = n - 1; i >= 0; i--)
    {
        long long cost1 = v[i].first * s1;
        long long cost2 = v[i].first * s2;
        tc1 += cost1;
        tc2 += cost2;
        // cout << tc1 << " " << tc2 << endl;
        if (tc1 > tc2)
        {
            listb.push_back(v[i].second);
            tc1 -= cost1;
        }
        else
        {
            lista.push_back(v[i].second);
            tc2 -= cost2;
        }
    }
    // cout << endl;
    cout << lista.size() << " ";
    for (auto &it : lista)
    {
        cout << it << " ";
    }
    cout << endl;
    cout << listb.size() << " ";
    for (auto &it : listb)
        cout << it << " ";
    cout << endl;
}

can anyone please explain me why this code will not work for problem B?

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

    I think you mean C

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

    The cost is different depending on where you put it. Say that the current number of elemnts in list_a is k1, and in list_b is k2, then the cost of adding an element S is S * (k1 + 1) * S1 in the first case, and S * (k2 + 1) * S2 in the second case.

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

Can anyone tell me why we need to fix the value of K in B.

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

    Probably because once we increase leg for a, we have no operation to decrease it. It's fixed that way, and we have to utilize it to reach b as well. If we had calculated k separately for a and b, then it may be the case that k(a) is greater than k(b), which is a move we can't make!

    So we simply choose leg size that is optimal for both a and b, hence, k is fixed for both. At least that's how I think it goes.

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

    Let's say we are calculating answer for $$$b$$$ only (you can extend this to $$$a$$$ also).

    Now, let's say you are using 2 values of $$$k$$$ i.e. $$$k_1 < k_2$$$. So your answer would be kind of $$$b/k_1 + b/k_2$$$, here if you just replace $$$b/k_1$$$ with $$$1$$$ you would get better answer and we can always do this since we will always increase value of $$$k$$$ from 1 to $$$k_2$$$ and $$$k_1$$$ is working on just the remainder of $$$b/k_2$$$.

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

E Has a nice observation, we would never take 3 consecutive edges. Any elegant solution using this observation.

(Take , NotTake, Take) is better than (Take, Take, Take) and both achieve our goal. f(i) = min(2*e(i,i+1) + f(i+2) , 2*[e(i,i+1)+e(i+1,i+2)] + f(i+3))

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

Solution to problem B seems pretty complicated. Can someone please explain a simpler approach?

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

    It's not difficult. You should just know the answer is $$$\lceil\frac{a}{k}\rceil + \lceil\frac{b}{k}\rceil + (k - 1)$$$ when you add your feet to k long. Then if you remove the ceil, you can get $$$\frac{a + b}{k} + k - 1$$$, it's just an inequality $$$a + b \ge 2 \times \sqrt{a \times b}$$$ when $$$a = b$$$ the equality is achieved. Therefore, for this function, it's $$$\frac{a + b}{k} = k$$$, .i.e $$$k^2 = a + b$$$. So $$$k = \sqrt{a + b}$$$, you can get the smallest value. However, you remove the ceil, so there maybe 2 off the correct answer. You should check around. Anyway, 1e5 is enough.

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

      How did you come to the conclusion that

      (A+b)/k)=k ?

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

        Because the inequality I wrote abode. $$$\frac{a + b}{k} + k \ge 2 \times \sqrt{a + b}$$$, and when $$$\frac{a + b}{k} = k$$$ the equality takes.

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

Hi

Can someone explain how the output for case:

1

5 3

is 5 for the problem: (B)Long Legs

Thanks

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

    Let, a=5, b=3, leg=1. Make leg=2, so move=1. Go 2 steps forward. 3 steps remain to reach 5. Move=2 (1 to increase leg, 1 to move 2 steps forward) Make leg=3. Move=3. Go one step forward. so move=4. Now, leg=3. Value of b=3. So we need one more step to reach b.

    So, move=5.

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

can someone recommend more problems similar to E

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

Sorry for necroposting, but I want to share my solution of F without using KRT.

Consider doing lazy tag on rollback DSU, when we visit to a certain time, add a tag with time stamp on the representative of vertex $$$1$$$, and when we rollback(assume this edge point to $$$boss$$$), if this edge is added before the tag on $$$boss$$$ is added, then push down the tag. At the end just check whether each vertex have tag on it.

I found it is quite amazing that we can do lazy tag on DSU, maybe there also have some potential application of it?

→ Reply