Kirill_Maglysh's blog

Codeforces Round #935 (Div. 3)
By Kirill_Maglysh, history, 2 years ago, translation, In English

Pay attention to the unusual round start time.

Hello, Codeforces!

Codeforces Round 935 (Div. 3) will start at Mar/19/2024 11:05 (Moscow time). The problems are expected to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

You will be given 8 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round is 10 minutes.

Remember, that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

  • take part in at least five rated rounds (and solve at least one problem in each of them)
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

The problems are based on VKOSP.Junior. Authors: Kirill_Maglysh, NToneE, Gadget.

We would like to thank:

  1. Vladosiya for coordinating the round.

  2. nigus, Gheal, KKT_89, Noinoiio, systy, FBI, SiERic, moonpieXXIV, nik.danilov, JuicyGrape, Pa_sha, FedShat, an_na, khaser, MountAim, Boris_Ber, PUFL, blook, yakuri354, iluminat_Btopou_AkkayHT for testing.

  3. gurovic for improving the quality of the statements.

  4. MikeMirzayanov for Polygon and Codeforces platforms.

Всем удачи!

UPD: Editorial is out

  • Vote: I like it
  • +122
  • Vote: I do not like it

Comments Comments (171)
| Write comment?
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Kirill_Maglysh (previous revision, new revision, compare).

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

Different start time.

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

Yay! Div3 Round. Note the unusual time!

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

As a tester, I tested some tasks

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

It's on my birthday!!! But I have to go to the school ... T_T

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

Hope to bring my rating back after this round

Good luck for everyone!

→ Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it +1 Vote: I do not like it

if i dont submit anything or may submit the first one,will my rating fall?

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Any submission results in a rated contest. It won't be rated if you did not make a single submission tho, even you registered beforehand

    → Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it -7 Vote: I do not like it

Why is the timing so unusual? Problemsetters please try to hold contests in the regular times only as it's really inconvenient for people studying in universities(as most of them are students) and it's quite difficult to make it on a weekday on such an odd time.

→ Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it -7 Vote: I do not like it

I want to author a Div.3 , how I can do ? Vladosiya

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +7 Vote: I do not like it

What an unsual time! Maybe there will be less participants than usual days orz.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

Cf round >>>>>>> school

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +14 Vote: I do not like it

Sleep schedule ruined enough to the point where a 1 AM contest will not affect my mental state. Good luck to all my fellow competitors, and may you gain a cool new color!

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

Wishing everyone a great round and a positive delta !

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

I appreciate the unusual start time, much more convenient for me since contests are typically at 2am for me. You guys should do this more often :)

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

I am excited about Div3 but this time wont allow me to participate

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

School Time here in China :(

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

speedforces!

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Thanks for this "unusual time". In the month of ramadan this time is perfect for me( from Bangladesh)

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +14 Vote: I do not like it

fun fact!
today is the last day of the persian calendar (I guess it's called new years eve)
so, if the round was at it's usual time, most of persian users couldn't participate, so thanks for this
love from Iran, Happy nowrooz <3

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

What an unusual start time! But it's suitable for Chinese students.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

great questions, but I wonder if problem setters intentionally make div3D easier than div3C most of the time. Problem C took way too much time to understand and implement.

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    How to do D ?

    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it +1 Vote: I do not like it

      DP

      → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it +9 Vote: I do not like it

      Assuming $$$f(i)$$$ is the minimum cost to stand at exactly position $$$i$$$, we have $$$f(i) = a_i + \sum_{j=i+1}^{n} min(a_j, b_j)$$$.

      The answer will be the minimum of $$$f(i)$$$ under $$$1 \le i \le k$$$. All $$$f(i)$$$ can be calculated through a linear iteration of the array from $$$a_n$$$ back to $$$a_1$$$.

      → Reply
      • »
        »
        »
        »
        2 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        Nice solution, I tried to think in greedy way for some time and then gave up and settled with DP

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          At this point I don't know if this solution of mine is classified as DP or greedy :D

          Kinda a mixture of both, DP in the way speeding up the calculation, greedy in the fact that $$$a_i$$$ and $$$b_i$$$ can interchange freely in the background without damaging the solution's validity.

          → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it +1 Vote: I do not like it

      while i > m, if a[i] <= b[i] jump to i

      then find i <= m, with minimum cost of jump

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

Announcement for C was given only after I asked about n/2 being floating point number. Explanation could have been better, wasted so much time in C due to that

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    But overall problems were good. Not too easy. Even A and B required some math work.

    → Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Problem Statement of B and C was not good. Especially C

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Unusual timing and kinda tough.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

C makes me want to broke my keyboard.

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

how to E

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

    Follow the given algorithm strictly and at last swap positions of l and x's index

    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Why this works can you give idea or intuition

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

        At all mids,

        If p[mid] <= x, l=mid else r=mid;

        So, basically you have to find what is the last index where l was updated.

        and in some cases, l may not be updated at all, there after simply swapping the l's position and x's position will make your array valid.

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          please, bro, explain me : when the last ind you updated is greater than target and in between the process mid come to our target. now if we swap last ind and target then mid again comes to the last ind and moves in the wrong dirn because initially the num is =target but now it it > tar. in between my code got accepted without thinking this how i am still confused.

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

            From my code,

            https://mirror.codeforces.com/contest/1945/submission/252251419

            I will not actually swap them

            First I will let this loop run

            where my l is getting updated only if p[mid-1]<=x

            ll l=1,r=n+1;

            while (r-l>1)

            {

    ll m=(r+l)/2;

    if(p[m-1]<=x){
        l=m;
    }

    else{
        r=m;
    }

}

            and now after breaking out from them loop I will not care about the r. I will only think about the l.

            Now if l == target's index then no problem else swap is required

            so the answer will be

            1 l target's index

            → Reply
  • »
    »
    2 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +1 Vote: I do not like it

    Repeated this process until found a solution:

    • select an ind randomly.
    • swap x and a[ind].
    • check if one operation is enough on the modified array. If yes, then break
    • else swap x and a[ind] back.
    → Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it +2 Vote: I do not like it

C was implementation heavy....

→ Reply
»
2 years ago, hide # |
← Rev. 4  
Vote: I like it +4 Vote: I do not like it

Ignore this comment. Deleted the tutorial, will wait for open hacking phase to complete.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Got the idea of problem E in just 10 minutes and the rest of the time passed just doubting myself that it cannot be this easy!!!

→ Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it -6 Vote: I do not like it

sorry to say, but the worst div3 statement i've seen in a while. It's just a troll if you don't have even the basic knowledge of english and you just set a problemset with whatever you want. Just a waste of time

→ Reply
»
2 years ago, hide # |
 
Vote: I like it -6 Vote: I do not like it

B,C and H are the most awful problems ever.

→ Reply
»
2 years ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

worst div3 ever seen

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

statement of c was not clear at all

→ Reply
»
2 years ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

Man B & C was laden with the weight of implementation intricacies.!!

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +9 Vote: I do not like it

    I beg to disagree. I would say that B and C are somewhat odd than usual, partially wordings, partially mathematical involvements, but implementations for them are nowhere near intricate.

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

      Master, are you taking my comment personally? You see I am not as skilled as you Master. I am a newbie in Codeforces parlance. So I'm not as good at simple thinking & solutions as you are, Master.

      → Reply
      • »
        »
        »
        »
        2 years ago, hide # ^ |
        ← Rev. 2  
        Vote: I like it +22 Vote: I do not like it

        Firstly, I think I should apologize if my words somehow felt like a personal attack. I never meant it that way.

        Secondly, however, I do think my point still stand. Of course, there will be an observable bias coming from me, with more experiences around. However, I do understand where you are coming from to counter-argue, as I had been there (or so I thought).

        For the problems themselves, B is a straight-up math problem, and C literally asks you to do whatever it tells you to.

        Of course, it's not that easy at a glance for newcomers: B's nature might seem dodgy to code at first thinking of how to fit the timespan, or is it required to explicitly define the optimal timespan; C — for now we ignore all the problem statement issues — looks confusing for newer contestants for maintaining the left and right side of the split.

        Still, what I wanna say to defend my point is, it's possible, and very likely, to generalize and abstract your thought process for a clean execution. The mathematical nature of B makes it a three liner if you understand how the math works, C is much cleaner to code once you could visualize how the states of the two sides change when we move the boundary.

        Of course, you don't have to take my thoughtstreams above all at once. One thing, you need to develop your own. Another, it's a steady learning process. You'll get better the more you spend your time thinking and improving. For now, I only state what I did at the original comment, as an opinion that what you have witnessed in your experience is incomplete — I won't say mine is already complete and perfect, but at least today I could cover yours a bit.

        → Reply
»
2 years ago, hide # |
 
Vote: I like it +32 Vote: I do not like it

Is it just me or today's G and H are worth Div2E at least...?

I was quite close to clear G, but cannot really make it — I thought it was just simulating the process but the initial queue order screwed me over.

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

How did you solve F?

i thought it's a ternary search...

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Basically, you do what you are told to greedily.

    Loop through all $$$k$$$ that satisfies $$$2k - 1 \le n$$$, each $$$k$$$'s answer will be the $$$k$$$-th largest element over the unaffected indices multiplying by $$$k$$$ itself.

    To maintain the elements properly, we can make two BSTs (or more regularly streamlined in C++ STL as std::multiset), one for the available elements, one for the already chosen one. Choose the largest element from available and throw it to chosen for the act of taking mushroom, and erasing element from either multiset (prioritizing available over chosen) for the act of "cursing".

    My implementation, for reference: 252244274

    → Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

How is the ans for the third test in problem F "8 2". Shouldn't it be "6 2"?

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

a lot of people solved b : (m * 2 — m) / a + (m * 2 — m) / b + somethings and no body will know why LOL

→ Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it +1 Vote: I do not like it

Can anyone give me intuitive understanding that why Following the given algorithm strictly and at last swapping positions of l and x's index is correct for Problem E?

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

    Consider 2 cases, whether the target is among the elements visited by binary search.

    If not, we can just swap the last l index with the position of the target since that will not change the search sequence itself.

    If yes, we see that swapping the order of any p[m] <= target will not affect the search sequence, since we are setting the left limit regardless every time.

    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Still not understood the Yes part. Can you please Elaborate.

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

        If $$$p_m \le x$$$, assign $$$l = m$$$.

        Say we pick two indices $$$i, j$$$ from the visit sequence such that $$$p_i \le x$$$ and $$$p_j \le x$$$. If we swap $$$p_i$$$ and $$$p_j$$$, will the visit sequence change?

        To add on to this, if $$$x$$$ is in the search sequence and is not $$$p_l$$$, then on the final time we set $$$l$$$, $$$p_l \lt x$$$. We can apply the previous statement to these two indices.

        → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      What if a[l]>target and target is visited ? In that case, search sequence will be altered ?

      → Reply
      • »
        »
        »
        »
        2 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        p[l] can only be larger than target if we have not visited target, since we only set $$$l = m$$$ if $$$p_m \le x$$$.

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          I used this logic during the contest and got WA on test2. Did your solution pass ?

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

            I looked at your submission and I think you calculated m incorrectly. I submitted your code with this change

            ll m = l + r >> 1

            and it passed. link

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              2 years ago, hide # ^ |
               
              Vote: I like it 0 Vote: I do not like it

              Generally, you would do l + r >> 1 for calculating m, but to avoid integer overflow you can do l + (r - l >> 1).

              → Reply
            • »
              »
              »
              »
              »
              »
              »
              2 years ago, hide # ^ |
               
              Vote: I like it 0 Vote: I do not like it

              Yeah, you are right. Unlucky me. Thank you for your help.

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

      The 'm' value that you're talking about should not be visited as mid value in the Binary Search, Right?? So we have to pick that index 'm' that is not visited during the binary search as well as it satisfies the condition p[m]<target.

      How are we sure that one such m will always exist???

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

        The m I am talking about is the m in the problem statement. If we visit the target index during the binary search, we can always switch it with the last time we set l (see logic in previous comment).

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

    First I assume that you are saying why this works, swap(1, position(x)) and then swap(1, l). or n instead of 1.

    Solution with 2 swaps

    UPD : Now, I get your question, my friend also told me this solution.

    Solution with 1 swap
    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it +3 Vote: I do not like it

      Thank you for the two-swap solution. I was wondering why two swaps are even allowed when it could be solved with at most one swap so easily. I thought it was meant to mislead us, haha.

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

252273129 It is the solution for Problem D.I don't know why I'm getting wrong answer on test case 3,jiangly approach and my approach is same even though I'm getting WA.Please help me to find the mistake.

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    You defined int as long long, however INT_MAX stays at its original value i.e. $$$2^{31}-1$$$, which might be smaller than the actual maximum possible answer of around $$$10^{14}$$$.

    → Reply
»
2 years ago, hide # |
 
Vote: I like it +47 Vote: I do not like it

Contest authors:

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

Overall didn't enjoy the contest. Problem A was ok, for B I didn't like the method. A and B could have been swapped. C was horrible, I had to read the problem statement 4-5 times. There was some clarification about not rounding up n/2 was weird. I feel you were going for a heavy implementation round to make the problems more difficult, sadly I am not a fan of it. D and E were smartly designed and I have fun solving them. But for E, I didn't like how I had to put seed values as 1 and n+1...like I spent 20 mins to figure this out, which I felt could have been improved.

What is done is done. Thank you for the contest! I appreciate your efforts for the round <3.

→ Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it +59 Vote: I do not like it

https://mirror.codeforces.com/contest/1945/hacks/1006163

~10 mins after the contest was finished, I realized I forgot to handle one case lol. This submission should fixed it. Anyway, my screencast is still processing and will be available here.

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

for D just a easy greedy! XD 

#include <bits/stdc++.h>
#define int long long
#define rep(i, j, n) for (int i = j; i <= n; i++)
#define pii pair<int, int>
#define psi pair<string, int>
#define pis pair<int, pair<string, int>>
using namespace std;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
template <class T>
using pql = priority_queue<T, vector<T>, less<T>>;
int n,m;
int a[200010];
int b[200010];
int c[200010];
void solve() {
  cin>>n>>m;
  rep(i,1,n){
  	cin>>a[i];
  }
  int aws=0;
  rep(i,1,n){
  	cin>>b[i];
  }
  aws=0;
  rep(i,m+1,n){
  	aws+=min(a[i],b[i]);
  }
  int mins=a[m];
  int sums=a[m];
  for(int i=m-1;i>=1;i--){
  	sums-=a[i+1];
  	sums+=b[i+1];
  	sums+=a[i];
  	mins=min(mins,sums);
  }
  cout<<aws+mins<<endl;
}
int32_t main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
→ Reply
»
2 years ago, hide # |
 
Vote: I like it +78 Vote: I do not like it

This contest was an undercover div 2.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

reading >>>> div1

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

In D-Question, (considering 1based indexing), how does taking the sum of indices m+1 to n inside the min variable actually matter?

My code(give WA on tc3) Code

Correct code Code

By just taking the ans variable out of that min part and directly adding, problem gets fixed I get it that it is more simpler, but I want to know why taking it inside the min part gives problem. Thanks in advance for your help.

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

either bro is too smart or bro is alt id of MikeMirzayanov

check this out

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

In C, n/2 is not an integer division could save my 1.5 hours

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Problem E (Binary Search) Video Editorial : (Audio : Hindi)

YOUTUBE EDITORIAL LINK --Click Here

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

it should have been 2:30 or 3:00 Hours contest , 2:15 wasn't enough

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

Does anyone know why my approach for G is incorrect? Basically I'm using a priority queue to check whether there's someone who already ate with higher priority than the current front of the original queue. I take the appropriate first guy and then schedule its insertion to the priority queue. I'm taking into account order of insertion when multiple ppl are to be inserted at once so idk what's wrong.

https://mirror.codeforces.com/contest/1945/submission/252292126

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +28 Vote: I do not like it

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

H problem hint please:
i concluded that its enough to choose 2 elements for gcd and rets n-2 for bitwise and.. not able to proceed further.

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I've added hints for H : GCD is Greater on CF Step

    → Reply
  • »
    »
    2 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +4 Vote: I do not like it

    Fact : we only choose 2 elements for gcd.

    Proof
    ThinkHint 1
    ThinkHint 2
    ThinkHint 3
    ThinkHint 4
    ThinkHint 5
    ThinkHint 6
    ThinkHint 7
    ThinkHint 8
    ThinkHint 9

    Complete Solution

    → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I haven't implemented this yet, but I think it should be fast enough:

    Spoiler
    → Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it +3 Vote: I do not like it

in problem C: i have read the statement 10 times and i am still confused why in 4th test case answer is 3 and not 2

testcase ->

000

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    omg on each side never mind I thought half of the residents in total should be satisfied!!

    → Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it +1 Vote: I do not like it

252362491

What is wrong in this solution of problem F?

Can anyone explain ?

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I had the same problem.

    See this case:

    3
7 5 8
3 1 2

    The answer is 10 2, not 14 2.

    That's because we remove the elements with indexes $$$p_i$$$, like, choosing $$$k = 2$$$ mushrooms, the magic of the element with index 3 will be zero, because $$$p_1 = 3$$$, so the array will be:

    7 5 0
3 1 2

    It's not the one with index $$$1$$$ or the element with $$$p_i = 1$$$, it's v[p[1]].

    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      This is so confusing, the samples don't have cases like this and the notes don't help.

      Honestly, the problem is good, but I don't know why doing these things just to "overcomplicate" a problem. It's not harder, it's just boring.

      → Reply
»
2 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

When will the ratings be out?

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

I didn't get B. If both are starting at the same time, then ans should be infinity. Can somebody explain.

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    That would just be $$$2$$$ simultaneous fireworks. $$$a$$$ and $$$b$$$ are at least $$$1$$$ so two fireworks of the same type would be at least $$$1$$$ minute apart, rendering them unable to stack indefinitely on top of each other i.e. we always have a finite answer.

    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      sorry bro, i didnt get. Could you please explain with an example. for example 1 1 1.

      In this case both will fire at 1 min then again 2nd min and it will go on. And they are visible for 1 min. So it should be inifinity.

      → Reply
      • »
        »
        »
        »
        2 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        The problem was about what is the maximal possible amount of fireworks visible at one moment. Also for any a and b, both fireworks will start simultaneously at lcm(a, b).

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

Imagine getting hacked for not commenting the debug statements.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

How long does it usually take for rating changes to come, and why is it taking so long for this contest's rating changes ???

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    Because of the large number of participants in Div. 3/Div. 4 competitions, system testing takes a lot of time. And these types of contests have a 12-hour phase of open hacks.

    Please be patient as the user ratings will not be updated until the system testing is complete, which usually takes 1-2 days.

    → Reply
»
2 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Nowadays, Codeforces is taking quite long time for rating updation!

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

I had a solution using binary indexed trees for problem F. But for some reason the case with single value is processing weirdly. https://mirror.codeforces.com/contest/1945/submission/252426399 I have added comments to debug, for the case 1 , 1 ,1 output is coming as 2. can someone help on this ?

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

Can somebody tell me the approx rating of all problems???

→ Reply