Vladithur's blog

By Vladithur, history, 7 weeks ago, In English

Thanks for participating in the round, we hope you liked the problems!

Solve count predictions (official div. 2)

1712A - Wonderful Permutation

Hint
Tutorial

Bonus: solve for every $$$k$$$ from $$$1$$$ to $$$n$$$ for $$$n \le 10^5$$$.

1712B - Woeful Permutation

Hints
Tutorial

Bonus: try to prove the solution without the editorial!

1712C - Sort Zero

Hints
Tutorial

Bonus: solve for when $$$a_i$$$ can also be negative.

1712D - Empty Graph

Hints
Tutorial

Bonus: solve for every $$$k$$$ from $$$1$$$ to $$$n$$$.

1712E2 - LCM Sum (hard version)

Hints
Tutorial

Bonus: solve the problem in $$$\mathcal{O}((n + t) \log n)$$$ or better.

1712F - Triameter

Hints
Tutorial

Bonus: solve for $$$n, q \le 10^6$$$.

Don't forget to rate the problems!

Problem Feedback

PS: Solution codes probably will be added later.

UPD: explanations of the references:

Click here
 
 
 
 
  • Vote: I like it
  • +325
  • Vote: I do not like it

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

Nice :)

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

    Why did you say that? What's the point of making such remarks? Look, this sentence of yours wasted one precious second of my life, and the reply wasted 30 seconds.

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

;(

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

the gap between C and D is too large.

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

    Maybe yes, but E1 was solvable, you could solve E1 instead of D

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

    We expected C to be a bit harder and D to be a bit easier.

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

      If you know Graph algorithms I think solving D would be easy however in general E1 is much easier

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

        maybe. But for me, I solve D in 30 min but solve E1 in 1h30min(failed to find 6 and 15's apperance, not familiar with the method). And I think D doesn't really have much to do with Graph Algorithms.

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

          Can you please explain the 6 and 15 case, cuz i dont understand it at all?

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

        No spoliers

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

    D isn't so hard, just D, like the ancient times, the C was easy let's gonna admit that

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

    yes

»
7 weeks ago, # |
  Vote: I like it +40 Vote: I do not like it

Problem D is one of the best problems I’ve ever seen. Overall, round is awesome. Hope to see more such great contests!

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

If the formal proof is quite hard, then why is it problem B ?

Do you expect people to solve without proof ?

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

    That's a mistake on my part, I started wondering about the formal proof only on the day of the round, and it turned out to be unexpectedly difficult.

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

    Do you expect people to solve without proof ?

    That's what people usually do...

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

      Yes, but if you guess it wrong, you're gonna get huge amount of penalties and waste a lot of time.

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

      Yea, but for most easy problems usually the gap between intuition and formal proof is not this large. Most of the time all you need to do is to formalize your intuition to turn it into a complete proof, which is definitely not the case for this problem.

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it +12 Vote: I do not like it

    Do you really think that those 13062 participants got Accepted on B all with proofs? :)

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

      Of course not, it's bad that they solved it without proof. My point is, for easy questions, make the proofs easy too.

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

        Or Make the problem with easy proofs. >_< (XD)

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

    While I do think that it may not be appropriate for div2B when the proof is so difficult, I think it's quite intuitive that the optimal result arises when big numbers are paired with big numbers, leaving small numbers paired with small numbers (as opposed to pairing big numbers with small numbers). Even without that intuition, trying it on a few small examples should quickly demonstrate this trend. Add in the observation that adjacent numbers have a GCD of 1 (so none of the factors are "wasted" by the LCM) and we have a straightforward solution that's very easy to implement.

    I didn't prove it during the contest myself, and that did cause me to hesitate before submission, but the intuition was strong enough that I decided to go ahead anyway.

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

      But the intuition was strong enough that I got +2 :(

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

        I think your intuition was correct, but you simply didn't test odd values. The 1 should have been at the beginning, not the end.

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

    rearrangement inequality, and the fact: x and x+1 are coprimes, is a little bit hard to proof but the intuition helps. Sadly many Competitive programmers don't like maths

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

    i just wrote brute force and saw the pattern for (1 to 9) ;) it was just swap(arr[i],arr[i-1]) from back....

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

Can E2 be solved using sqrt decomposition?

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

The editorial doesn’t show up in the bottom right of the problem pages

»
7 weeks ago, # |
  Vote: I like it +81 Vote: I do not like it

I accepted f in the contest, my solution is $$$O(qn \log n)$$$. Maybe because of the large constant, it fst.

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

    And I don't know why it get wa when I optimize it.

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

      for vertices i,j the distance shall be $$$min(f[i]+f[j]+x,dis(i,j))$$$, f[i] means the distance between i and the nearest leaf. I sort f, and check whether the answer can be bigger than ans. Then for every node, it is a suffix of j that $$$f[i]+f[j]+x>=ans$$$ . I prework the suffix diameter and use O(1) lca to find the distance.

»
7 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

This was challenging and editorial is awesome. Thanks for these competitions

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

C can also be solved using binary search.

Find the minimum $$$k$$$ such that the array remains sorted if the first unique $$$k$$$ instances of the array are converted to $$$0$$$.

Solution: 168108392

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

Easiest Div2C ever?

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

    Yes probably. Some newbies solved all A,B,C and still got negative delta.

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

Can you use the rearrangement inequality somehow to get a formal proof for the solution to problem B?

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

Can someone please tell me why i get WA with this source for problem D (greedy solution)?

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

Is anyone getting wrong answer on 21st test of main test 2 for problem D? (the test case isn't visible)

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

prob C failed in main test fk this pretest

»
7 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it
Alternate proof of B
»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

for D: D = max(min(arr[i],arr[i-1]),2*min(arr[0..n-1])) Why do we need bs?

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

    As we can also update the arr at most k times and it is not optimal to just update the first k smallest values. You can also do it without binary search, but for me, binary search approach is simpler.

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

For subproof in problem D: When Imin is < u, can we take u to Imin and then Imin to v path instead of going till node 1? cc: Vladithur

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

    Yes, going to node 1 just ensures that we always cross the min value.

»
7 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

I made video Solutions to the first 4 problems in case people are interested.

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

Great contest!

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

I don’t think we need that proof to solve B I just wrote the numbers down and i got my answers right away But btw nice editorial < 3

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

    During the contest you may be right,but I don't think you can learn something from the problem after the contest.Actually,if it was D or E,probably you would hesitate to submit.

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

Problem C can be solved with binary search

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

How do you arrive at the conclusion: a tuple $$$i \lt j \lt k$$$ is bad when $$$\mathrm{lcm}(i,j,k) = 2 \cdot k$$$ and $$$i+j \gt k$$$?

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

    $$$lcm(i, j, k) = 2 \cdot k \implies 2 \cdot k < i + j + k \implies i + j > k$$$

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

      I meant to ask how you get $$$\mathrm{lcm}(i,j,k) = 2 \cdot k$$$ in particular. Why $$$2 \cdot k$$$?

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

        $$$lcm(i, j, k) < 3 \cdot k$$$, and $$$lcm$$$ must divide $$$i$$$, $$$j$$$, and $$$k$$$. This leaves us with only two possible values for it: $$$k$$$ and $$$2 \cdot k$$$.

»
7 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

as a #008000 rated, I enjoyed solving C

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

Got TLE on TC33 of problem C.

How to optimise this Submission

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

    Instead of map<ll,vll>, make map<ll,ll> m.Store the last position of each number in there.Then you don't have iterate over vectors.Just mx=max(mx,m[v[i]]);

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

Could someone point out my mistake in problem D? I don't understand what the tute is saying very well. https://codeforces.com/contest/1712/submission/168169178 I've also made this edit, but it still didn't work. https://codeforces.com/contest/1712/submission/168199569

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

Problem E1.Who have different idea?I didn't understand tutoriol.

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

Difficulties like ->Easy -> Easy -> Easy -> Hard -> Hard -> Hard -> Hard

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

Where does the "/6" and "/15" come from at problem E1? I ve seen this on many solutions.

I guess its an optimization for finding all triplets i,j,k with a fixed k, but i dont undersand it.

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

    You will see, if(i==6 j==10 k==15), lcm(i,j,k)=30 < i+j+k, if(i==3 j==4 k==6), lcm(i,j,k)=12 < i+j+k, and you may enlarge i,j,k because if lcm(i,j,k) < i+j+k ,then X(lcm(i,j,k)) < X(i+j+k) ,since X is a positive integer.

    And why is the cases (i==6 j==10 k==15) and (i==3 j==4 k==6) ? That's because 1/5+1/3+1/2 > 1 and 1/4+1/3+1/2 > 1

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

    This is for finding $$$(i, j, k)$$$ where $$$lcm(i,j,k)=2k$$$ and $$$i+j>k$$$.

    Note that because of the second condition, $$$\frac{k}{2} < j < k$$$. Since $$$j$$$ divides $$$2k$$$, $$$j$$$ must be $$$\frac{2k}{3}$$$.

    Using the second condition again, $$$\frac{k}{3}<i<\frac{2k}{3}$$$, which implies $$$i$$$ is either $$$\frac{2k}{5}$$$ or $$$\frac{k}{2}$$$.

    So the solution triplets in this case has the form $$$(\frac{2k}{5}, \frac{2k}{3}, k)$$$ (happens when $$$15$$$ divides $$$k$$$), or $$$(\frac{k}{2}, \frac{2k}{3}, k)$$$ (happens when $$$6$$$ divides $$$k$$$).

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

      Nice. Thanks for the clear explanation.

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

Very easy greedy Solution of problem D

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

    can you explain it as well plz?

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

      Try this for an explanation.

      As discussed elsewhere, when doing an update of an a_i you should always update to 1e9.

      There are two possible strategies for doing the K updates of the a_i: 1. Update the smallest K of the a_i, or 2. Update the smallest (K-1) of the a_i, and then use the last update to update a neighbour of the largest of the updated a_i.

      We can split the 2nd strategy into two: if K=1, then the final update is to the largest of the original a_i if K>1, then the final update will be to a neighbour of a_i already updated with value 1e9.

      The final diameter of the graph is min( 2*smallest a_i, max of smaller neighbours a_i, a_i+1 )

      So overall we have to calculate 4 numbers: v11 — strategy 1 — 2*smallest of updated a_i v12 — stratgey 1 — max of smaller of the a_i and a_i+1 v21 — strategy 2 — 2*smallest of updated a_i v22 — stratgey 2 — max of smaller of the updated a_i and a_i+1

      diameter for strategy 1 is min(v11,v12) diameter for strategy 2 is min(v21,v22)

      We pick the strategy for the larger diameter, so the final answer max( min(v11,v12), min(v21,v22) )

      In the code: v22 is cnt — initially calculated for K=1, and overwritten with 1e9 if K>1 v21 is expressed as 2ll*vec[k-1].ff min(v21,v22) is put into "ans"

      The smallest K values of a_i are identified by populating and sorting vector<pair<ll,ll>> vec. Then we explicitly update the a_i array.

      v12 is calculated in maxi2 in a loop that looks at the neighbours min(a[i], a[i+1]); v11 is picked up from 2ll*vec[0].ff and we have maxi2 = min( maxi2, 2ll*vec[0].ff ) to calculate min(v11,v12).

      The final output cout << max( ans, maxi2) selects the diameter from the better of the two strategies.

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

        thanks for the detailed explanation!

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

        thanks for the vid. much appreciated!

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

Finally became CM! Like B & D very much.

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

Why should i to find 6 and 15 in problem E1? How can I think that way. I see tourist's solution seemed iterate in 30 to find such special case. It shows that he is trying to find such special case.

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

    For small numbers multiplication funtion has a low growing, so the idea is use BruteForce for those small values

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

Did anybody solve this clue by the author? I'm still stuck on it.

Edit: I saw the answer in editorial.

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

I really think this round is quite exquisite.

The bonus in every problem, the riddle in the beginning of each task(and ACGN lover here too!), and the nice problems.

Though I was one of those who was stuck in problem D just in lack of a binary search while using a bad greedy, I still have to upvote the problem preparation for all involvers!Thankyou!

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

B Bonus: try to prove the solution without the editorial!

Me: Use the data!

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

Could anyone please explain for what mysterious reasons this solution for D using ordered_set is not passing even small test cases like (n <= 1000)? (168216695)

Hand written Treap passed pretests, but FST'ed mostly likely due to bug in my implementation (168172650)

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

In my opinion, E1 and E2 are good problems. Thanks for the great contest!

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

In C iterating from last index, I checked if Ai < Ai-1. If yes then simply print number of distinct elements before Ai and break. If no then check whether count of Ai>1 && Ai!=Ai-1(i.e its duplicate lies in prefix of the array) then also print number of distinct elements before Ai and break.

https://codeforces.com/contest/1712/submission/168175298

Please help me where am I doing wrong

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

    I am not confident that your idea would work in general, but here is an immediate error I found: when line 34 is executed, i.e., decreasing the hash value of an element if it appears multiple times in a row, the decrement --c at line 37 is still executed, even though the number of distinct values in the prefix has not decreased. Here is are three test cases I encourage you to check:

    3
    4
    1 3 2 2
    5
    1 3 2 2 2
    6
    1 3 2 2 2 2
    

    Each occurrence of 2 decreases the number of distinct characters, with the final test case even reporting a result of -1.

    I think you intended to put a continue; after line 34. I'm still a little skeptical of whether this would be enough to correct the program (since the logic feels like it still has loopholes), but that should be a good step forward.

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

For prob D can someone explain this TC?

6 2
2 1 2 4 2 1

My solution is to replace the 2nd and 6th values with $$$10^9$$$. So the diameter here would be $$$d(2,6) = 4$$$ (going through one of the nodes with value 2), but the expected result is 2. Am I missing something here?

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

    The length of the edge connecting node $$$2, 6$$$ is $$$2$$$, because $$$\min{a_2, a_3, a_4, a_5, a_6} = 2$$$.

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

      Oh shit I misunderstood the problem for the whole night. Thank you!

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

In fact, we can prove in E1, $$$j = \frac{2}{3}k$$$ if $$$\operatorname{lcm}(i, j, k) = 2 \cdot k$$$ and $$$i + j > k$$$. So we can solve this problem in complexity $$$\mathcal O(n \sqrt n + \sum_{i = 1}^n \sigma_0(i))$$$ per testcase, which is faster than the editorial.

code 168224359

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

    Yes, but I don't really like number theory, so I didn't want to include more of it in the solution.

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

C feels amazing, I can only think of BFS to solve it

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

Very good contest, one of the best I have seen yet :)

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

I think problem D is much harder than problem C.I solved C in ten minutes but didn't solve D in the contest.

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

personally liked all the anime references.

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

Bonus solution of C. Sort Zeroes, when a[i]<0,

we traverse from the left of the array [n-1 till 0] , we break the moment we find a[j]>a[j-1], now we know j is the index up to which all the ai values need to be zero. Still, there may be chances that some elements within [0,j] may also be within [j+1, n-1] ( think why? ) to check that, we maintain a set of unique elements within [0,j], and once again traverse from [n-1 till j+1] and break the moment we find an a[i] which already exists within the set of unique elements from [0,j], now once again maintain the set of unique elements till the index of the last break. The answer is equal to the size of the new unique elements set.

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

    Damn!, this is exactly how I solved it lol

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

But I can't understand D. /sad

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

Here is my proof for B. The key claim is the following:

Claim: Let $$$a,b$$$ be positive integers such that $$$a\ne 1$$$ or $$$b\ne 1$$$ (or both), then $$$\operatorname{lcm}(a,b) \leq \frac{a^2+b^2-1}{2}$$$.

Proof: If $$$a\neq b$$$, then

$$$\displaystyle{\operatorname{lcm}(a,b)\leq ab = \frac{a^2+b^2-(a-b)^2}{2} \leq \frac{a^2+b^2-1}{2}}.$$$

Otherwise, $$$a=b$$$, then

$$$\displaystyle{\operatorname{lcm}(a,b) = a \leq \frac{2a^2-1}{2}}.$$$

Hence, the claim is proven $$$\blacksquare$$$

Now, we just use the claim (note the exception at $$$1$$$):

$$$\displaystyle{\sum_{i=1}^n \operatorname{lcm}(i,a_i) \leq \frac 12 + \sum_{i=1}^n \frac{i^2+a_i^2-1}{2} = \sum_{i=1}^n i^2 - \frac{n-1}{2}}.$$$

If $$$n$$$ is odd, then this is the desired bound. Otherwise, note that this quantity is not an integer, so we actually reduce the bound by $$$\tfrac 12$$$. One can check that this yields the equality.

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

Can someone explain the graph proof in tutorial of Problem B? Also didn't get the $$$x_{1}, x_{2}, ... x_{k}$$$ optimal value part with how $$$ ( x_{1}^2 + x_{2}^2 + ... x_{k}^2)$$$ is obtained because even with no restriction how is maximum value of $$$f(i,x_{i}) = x_{i}^2?$$$

»
7 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Bonus Problem's Solution for A
We have to find $$$ans_1, ans_2, \ldots ans_n$$$

  • First Initialize each $$$ans_i$$$ to $$$0$$$.
  • Then traverse the array p from end
  • Now say element x appears at index i and $$$x<i$$$. This implies that x is at wrong position, after its ideal position x.
  • This will cause the $$$ans_j$$$ to be increased by $$$1$$$ for $$$x \le j < i$$$
  • We can perform this range increment lazily. Hence, ans array will be computed in O(n) time.

Implementation

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

    instead of arrray we could do this with condition if(element>k && index of element <k)cnt++

    ll n,k,cnt=0;
        cin>>n>>k;
    
        FOR(i,0,n){
            ll x;
            cin>>x;
            if(x>k && i<k)cnt++;
        }
    
        cout<<cnt<<endl;

    Implemented

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

About Bonus Problem of C

  • If any $$$a_i$$$ is $$$\le 0$$$ and any $$$a_j$$$ is $$$ \ge 0 $$$ such that $$$j<i$$$ , then all numbers from $$$a_1$$$ to $$$a_i$$$ have to be converted to 0. (Because $$$a_j$$$ will always be $$$ \ge 0$$$ )
  • Hence we can convert the array such that either all negative number are changed to $$$0$$$ or all negative number are on the left side of the array.
  • Then we can apply the original problems's solution.
»
7 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

A-E2 video Editorial for Chinese :

Bilibili

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

Comeback after almost a year ... I did pretty bad

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

for E2. "Turns out that for the current constraints, for every k, we can iterate over all pairs of 1≤i<j<k, where i and j are divisors of 2.k and check if the triplet is bad."

Why can we do this? I know that the sum of number of factors of all numbers from 1 to n is O(nlogn), but here we are iterating over each pair of factors for every number, what is the bound for that?

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

In editorial of problem D, what is the "another case to work"?

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

Can someone tell me what is wrong with this submission? The logic seems to be right 168276229

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

In problem E how can I find this $$$\frac{(r - l + 1) \cdot (r - l) \cdot (r - l - 1)}{6}$$$ .

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

    It's just $$$C_{r - l + 1}^3$$$ — the number of ways too choose three elements from $$$r - l + 1$$$ elements (if we don't care about the order).

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

Can someone help me to know why my solution fails for problem C?

#include <bits/stdc++.h>
using namespace std;
#define ln '\n'
#define fast cin.tie(0), cout.tie(0), cin.sync_with_stdio(0), cout.sync_with_stdio(0);
#define all(v) v.begin(), v.end()
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define ll long long

const int N = 1e5+1;

void solve(){
    int n; cin >> n;
    vector<int> arr(n);
    multiset<int>mst;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
        mst.insert(arr[i]);
    }
    if(is_sorted(all(arr))){
        cout << 0 << ln;
        return;
    }
    int i = n-1;
    for ( ; i > 0; --i) {
        if(arr[i] < arr[i-1] || mst.count(arr[i]) != 1){
            i--;
            break;
        }
    }
    set<int>st;
    while (i >= 0){
        st.insert(arr[i]);
        i--;
    }
    cout << st.size() << ln;
}
int main() {
    fast
    int t = 1;
    cin>>t;
    while (t--)
        solve();
    return 0;
}
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the solution for F Bonus?

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

Can somebody help me out with Problem D : Link

My approach is ans = max( min(2 * mn , min(a[i],a[i+1]))) , where mn is the minimum value of a.

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

Any ideas about Bonus Problem for D?

I have solved problem D, but I can't think of any approach for doing it for all k.

Maybe Vladithur can create a separate blog post about the solutions of bonus problems.

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

    I'm too lazy to do that(

    As for the bonus of problem D, the basic idea is to extend the greedy solution.

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

    If we try to extend the greedy solution of D. The complexity reaches O(n^2).

    • To find for any k we need to do O(n) processing.
    • I tried to think how to use the solution of k-1 to solve for k, But there seems a lot of casework, and even after that complexity still seems to be O(n^2) in some worst cases.

    Can someone help me here ?

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

      What I meant is that you process the values of $$$a$$$ in increasing order and then maintain a couple of sets / multisets to find the answer for every $$$k$$$. Try to find what information you need to know to get the answer for some $$$k$$$ (and is easy to maintain when you move on to $$$k + 1$$$).

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

I found C to be bit on a tougher side, compared to the no of solves during the contest :/

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

I am very confused about the use of i+= i & (-i) loop from many of the fastest solutions of problem E2. For example, this, this and this.

It seems to me that there are some hidden patterns that I am not aware of. Could anyone help me?

»
7 weeks ago, # |
Rev. 15   Vote: I like it -6 Vote: I do not like it

.

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

Problem D(Empty Graph) tutorial help. Can someone please explain the second proof or the below paragraph from the tutorial? I will be thankful to you!!

"2. The diameter of the graph is equal to max1≤i≤n−1d(i,i+1)=min(max1≤i≤n−1min(ai,ai+1),2⋅min(a1…an)). Proof: since the minimum of a subsegment can only decrease when it's length increases, it is optimal to look only at the distance between two adjacent vertices."

What does it mean " the minimum of a subsegment can only decrease when its length increases" ? and how are we coming to an intuition where considering d(i,i+1) is an optimal choice

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

Can someone explain the binary search solution for problem D? I am not sure I understand

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

Could any warm-hearted baby provide a previous code of D? I try my best but owing to my poor intelligence not to be able to do with it

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

Can anyone tell me why I got the wrong answer in https://codeforces.com/contest/1712/submission/168392728 of problem d?

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

Test cases of B were very helpful. Couldn't have solved without them.

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

Thanks for amazing round and tutorial but there is a small mistake Div2B Hint 3

lcm(x, x + 1) + lcm(x + 1, x) = x² + (x + 1)²-1

»
7 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

why is this unrated now ?

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

We can probably prove problem B by induction? In addition, I don't understand this sentence in problem B:

So we need to minimize the sum of $$$max(x1…xk)−min(x1…xk)$$$ over all cycles.

Could anyone please explain it?


Sory for my poor English.

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

"If there is at least one operation left, there are two cases: k=1 and k>=2.If the first case, it is optimal to apply our operation near one of the maximums in the array to maximize min(a_i,a_{i+1})"

Would it not be more optimal to change a_i > = ans/2 to 1e9? Consider ans = 18, and the following array-

[0,1,4,5,6,9,10,11,15,17] and nodes [1,2,3,4,5,6,7,8,9,10]

Let k = 6. The binary search solution would turn this to-

[1e9, 1e9, 1e9, 1e9, 1e9, 9, 10, 11, 15, 17] and k = 1.

Now, if we change 15 to 1e9 (as mentioned in the solution), then d(9,10) = 2*9 = 18. But if we change 9 to 1e9, then d(6,8) = 2*10 = 20 > 18?

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

    I meant $$$k = 1$$$ and $$$k \ge 2$$$ for the value initially given, not after we apply the operation some number of times.

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

      I am not sure I follow, consider-

      arr = [2,3,4,5,11,12], nodes = [1,2,3,4,5,6] and k = 1.

      Let ans = 5. In the binary search, no a_i's would be turned to 1e9 as 5/2 = 2 !< 2. First if condition fails as operation wasn't applied. In the second if condition, k==1 and max(a_1,..,a_n) = 12 > 5, hence it will return true.

      But, if we change 11 to 1e9, then d(5,6)= 2*min = 2*2 = 4 < 5?

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

        The division is not floored, $$$\frac{5}{2} = 2.5$$$, not $$$2$$$.

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

          Aha, I think I understand now. Thanks a lot!

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

what is wrong in my code for problem C? please help someone!!! https://codeforces.com/contest/1712/submission/169538290

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

Why tutorial for problem E1 is missing?

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

    Because the main idea of the model solutions is the same in both versions, E2 just uses a data structure to speed up the last part of the solution, which you don't need to use in E1.

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

      Thanks, it would be really helpful if you can mention this information at the start of the tutorial for E2. Or rather one should have made the editorial for E1 because I think people usually solve in order so they won't look up into E2 before they have solved E1 expecting that E2 must have a different solution.

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

Vladithur can u elaborate on the proof for greedy in div2 D. Why is it optimal to consider k-1 minimums in the first place?

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

    This is somewhat similar to the binary search solution. In it you change the smallest values such that all $$$a_i \ge \frac{ans}{2}$$$, and then cleverly choose which remaining values to change. Turns out that there are only two cases: zero values left or $$$\ge$$$ one value left, so in our greedy solution, we also leave one value to do something with, hence we change the $$$k - 1$$$ smallest values.

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

For Problem E2 : It is mentioned as Since i<j<k, a triplet is bad only when lcm(i,j,k)=k or (lcm(i,j,k)=2⋅k and i+j>k) but there is no explanation like why it is true or how do the author arrive to this condition. Vladithur Can you explain this ? Like its is easy to observe that if lcm(i, j, k) = k then it would be bad, but for 2k I am not sure. Also why not the values in between k and 2k.

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

C :

wHERE IS MISTAKE , iT'S FALLING ON 2ND TEST CASE

https://codeforces.com/problemset/submission/1712/170962914

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

Casework O(nlogn) greedy solution for D:

Maintain array v and sorted array v2

One possible solution is to reduce all the k minimum elements to 1e9 then

ans=max(ans,min(v[i]+v[i+1],v2[k]*2)) ****

as elements 0......k-1 in v2 assigned 1e9 in v so the smallest element in v is v2[k]

Now reset v

Another possible solution is to assign the smallest k-1 elements to 1e9 then

ans=max(ans,min(max(v[i],v[i+1]),v2[k-1]*2)); ****

This is because we have an element v[i]. Next or previous element we can assign 1e9 so it becomes min(v[i],1e9) = max(v[i],v[i+1]) as we assign the minimum element to 1e9

Now if k>=2 Another possible solution is to assign the smallest k-2 elements to 1e9 then

ans=max(ans,min(1e9,v2[k-2]*2)) ****

as we have two consecutive elements of the form [1e9 1e9] in the array and the smallest element in the array is v2[k-2]