Kirill_Maglysh's blog

By Kirill_Maglysh, history, 4 weeks ago, translation, In English

1945A - Setting up Camp

Idea: Kirill_Maglysh

Tutorial
Solution

1945B - Fireworks

Idea: NToneE, Gadget

Tutorial
Solution

1945C - Left and Right Houses

Idea: Gadget, NToneE

Tutorial
Solution

1945D - Seraphim the Owl

Idea: Kirill_Maglysh

Tutorial
Solution

1945E - Binary Search

Idea: Kirill_Maglysh

Tutorial
Solution

1945F - Kirill and Mushrooms

Idea: Kirill_Maglysh

Tutorial
Solution

1945G - Cook and Porridge

Idea: Kirill_Maglysh

Tutorial
Solution

1945H - GCD is Greater

Idea: Kirill_Maglysh

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

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

For problem G the editorial has the swapped inequality it should be suffixMax_p >= k(Q2_front), because that indicates there is a larger k in the suffix of Q1 that highest priority person in Q2 would be waiting behind.

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

E was subtle

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

For problem D we can consider a dp approach: let $$$dp_i$$$ the minimum ammount of coins for reach the position $$$i$$$, thus:

$$$ dp_i= \begin{cases} a_n & \text{if } i = n \\ \min\{a_i+dp_{i+1}, a_i+dp_{i+1}-a_{i+1}+b_{i+1}\} & \text{otherwise} \end{cases}$$$

We can calculate solutions from $$$dp_1$$$ and choose $$$\min\limits_{1 \le i \le m}{dp_i}$$$. The basic idea is to choose between pay $$$b_i$$$ or $$$a_i$$$ for all $$$i$$$.

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

    can you explain the first sample test case of D. the answer should be swap with place 2 and pay 3+8 = 11. how is it 14?

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

      If we swap with the 2nd position, you also must pay $$$b_n = 5$$$ because initially you will stand in $$$n+1$$$ place and this give you $$$16$$$. I'll simulate the solution for the first test case

      Consider $$$dp_4 = 9$$$, so we move on to $$$dp_3$$$, we must choose:

      $$$dp_3 = \min\{a_i+dp_{i+1}, a_i+dp_{i+1}-a_{i+1}+b_{i+1}\}$$$
      $$$dp_3 = \min\{6+dp_{4}, 6+dp_{4}-9+5\}$$$
      $$$dp_3 = \min\{15, 11\}$$$

      $ So, $$$dp_3 = 11$$$. The second part of the $$$\min$$$ function represent that we consider took $$$b_{i+1}$$$ instead of $$$a_{i+1}$$$, in this case $$$dp_3$$$ choose $$$b_4$$$ because if we want to reach $$$i=3$$$, it will be optimal to choose $$$a_3+b_4$$$. At this moment we have $$$dp_3=11$$$, so we will calculate $$$dp_2$$$ as follows: $$$dp_2 = \min(3+11, 3+11-6+8) = \min(14, 16)$$$ so $$$dp_2 = 14$$$ and actually this is the minimum value for $$$dp_i, 1 \le i \le 2$$$. This solution says that is optimal to choose $$$a_2+a_3+b_4$$$.

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

Problem E Video Editorial Audio : (Hindi)

YOUTUBE VIDEO LINK ---Click Here

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

There's actually quite an elegant implementation for problem F:

https://codeforces.com/contest/1945/submission/252463604

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

Please guys, l'd like to know why I het a WA? Problem F: https://codeforces.com/contest/1945/submission/252370876

Thanks.

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

At problem B,

"At the moment x, there will be fireworks in the sky, released at moments [x, x+a, …, x+a⋅⌊m/a⌋]"

Please explain.

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

Problem F can be simulated with an ordered statistic tree :p

252626826

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

Solving B using binary search - The key to solve this problem lies in the concept of binary search on the answer. We aim to find the largest integer value x such that x * a — a <= m.

  • We start by initializing a binary search range with st = 0 and en set to a sufficiently large value, say 10^20 (we can't in c++ so use python). Then, we perform a binary search within this range. At each step, we calculate the midpoint mid and check if mid * a — a <= m. If this condition holds true, it means we can increase our search range. Thus, we update st = mid. Otherwise, we need to decrease our search range, so we update en = mid — 1. We repeat this process until we find the maximum valid value for x. This process has a time complexity of O(log n).

  • We apply the same binary search approach to determine the maximum number of fireworks launched at intervals of b, 2b, 3b, and so forth.

  • Finally, we sum the maximum values obtained from both binary searches to obtain the total maximum number of fireworks launched within the given time frame m. This sum represents our answer. https://codeforces.com/contest/1945/submission/252638271

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

In C sample 1.

3
101
outut:2

"can't we insert at 0 the villagers to right side 2 of 3 are satisfied ?

If there are multiple suitable positions i with the minimum ∣n2−i∣, output the smaller one."

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

    In that problem n/2 is not rounded to an integer, it may be a decimal value

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

Well For the Problem E only one swap is sufficient in every case ? my solution got accepted but don't know how....? can anyone explain

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

nvm, i got it lol good contest btw

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

For C,why n/2, it's a real number didn't mention in the problem statement?

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

Can someone please help me in finding my mistake for submssion 252896905 to problem F?

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

I think the problem G's statement is still not 100% clear. If 2 students with the same priority, finishing their dishes at the same time, who will go to the queue first?

I tried to solve this solve this by assuming the one who goes out eating first will come back first, but apparently this seems to not be the case. The comparator function in the solution prioritize the student with higher eating time first. This seems very unnatural to me.

Though the problem idea didn't change much if a more strictly description was added. This is still a cool problem. Though this bug me for hours, not know where I was wrong.

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

    Question does say

    "If several schoolchildren return at the same time, they will return to the queue in ascending order of their si."

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

Can anyone explain E? Not able to get it from the tutorial.

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

    We know this binary search gives a number which is always <=X. (If you are not sure about that, you can try some examples.)

    Assume P is position of X.

    If we change this result and P, we can find X. Because only once we asked to P. And smaller number will give same answer(make l = mid). So we will get same index before don't swapped P and result.

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

https://codeforces.com/contest/1945/submission/253021750

why this solution is giving runtime error on testcase 2 in problem D

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

in problem H why if a bit is 0 in more than 2 numbers then its 0 in the AND ? i understand that if we have 3 or more numbers with bit x 0 in them then it'll always be zero in the finally AND but sometimes we can have only 1 number with bit x equal to 0 and still the finally AND will have that bit 0 if we dont consider it in the red numbers ? the middle paragraph is unclear hope somebody rewrites it in a more clear way , thanks

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

    Your understanding is correct. Suppose we are dealing with $$$x^{th}$$$ bit. There are 3 cases:

    1. None of the numbers contain a 0 at this position : The AND would contain 1.
    2. There are $$$> 2$$$ 0 at this position. The AND would contain 0.
    3. There are 1 or 2 zero at this position. Then, we are not sure about the AND. But, let's pick one element with zero at this position, move it to the blue set, and then, let's try to pair it up with all possible elements. If no match could be found, then we know for sure that the element belongs to the red set, hence making the AND zero.

    I've added more details here

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

      Yea thanks I got it , it wasn't clear at the beginning I feel like it would've been more clear if they stated why we try all numbers where the bit is 0 in no more than 2 but now that I get it I feel like it's self explanatory

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

Understanding problem statement C is 80% and solving it is 20%. Problem statement of [problem:C] is really confusing.

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

for D question is tough to understand

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

Someone please explain what this line means in tutorial for problem H: "We will iterate through each of these numbers as one of the red numbers, and iterate through the second one for n " , where are we iterating for second number and how? Need some explanation .

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

Problem D editorial contains typo, $$$b_k$$$<$$$a_k$$$ should be there.

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

Problem D

before reaching the position m why not simply take the minimum of a[i] and b[i] ?? and then consider the sum of pref and bSum ??

something like this

int n,m; cin >> n >> m;

vector<int> a(n);
vector<int> b(n);


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

if(m==n){
    cout << a[n-1] << endl;
    return;
}

long long ans = 0;
long long c = 0;
for (int i = n-1; i >=m; i--)
{
    ans+=min(a[i],b[i]);
}
long long ans1=1e18;

for (int i = m-1; i >=0; i--)
{
    ans1 = min(ans+a[i]+c,ans1);
    c+=b[i];
}





cout << ans1 << endl;
»
10 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B: Please explain this line: At the moment x, there will be fireworks in the sky, released at moments [x, x+a, …, x+a⋅⌊m/a⌋[user:Gadget].