When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

n0sk1ll's blog

By n0sk1ll, 15 months ago, In English

1779A - Hall of Fame

Author: n0sk1ll

Hint
Solution
Bonus Problem

1779B - MKnez's ConstructiveForces Task

Author: n0sk1ll

Hint 1
Hint 2
Solution
Bonus Problem

1779C - Least Prefix Sum

Author: n0sk1ll

Hint 1
Hint 2
Solution
Bonus Problem

1779D - Boris and His Amazing Haircut

Author: n0sk1ll

Stupid Hint
Hint
Solution
Bonus Problem

1779E - Anya's Simultaneous Exhibition

Author: n0sk1ll

Hint
Lemma 1
Lemma 2
Solution
Bonus Problem

1779F - Xorcerer's Stones

Author: n0sk1ll

Hint 1.1
Hint 1.2
Hint 1.3
Hint 2.1
Hint 2.2
Solution
Bonus Problem
Bonus Problem Hint

1779G - The Game of the Century

Author: Giove

Hint
Solution
Bonus Problem

1779H - Olympic Team Building

Author: n0sk1ll

Huge thanks to dario2994 for helping me solve and prepare this problem.

Hint 1
Hint 2
Fake Solution
Lemma
Solution
Bonus Problem
Tutorial of Hello 2023
  • Vote: I like it
  • +356
  • Vote: I do not like it

| Write comment?
»
14 months ago, # |
  Vote: I like it +97 Vote: I do not like it

very fast tutorial ;)

»
14 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Is this the fastest published editorial?

»
14 months ago, # |
  Vote: I like it +143 Vote: I do not like it

These are, as of now, surely the best CF problems of 2023!

»
14 months ago, # |
  Vote: I like it +3 Vote: I do not like it

F is very similar to : THis Problem

»
14 months ago, # |
Rev. 6   Vote: I like it -12 Vote: I do not like it

I want to know in Prob.A when I was submitting like for LR the answer is 1, why its wrong?

Since only 1 operation will be enough in this case if we find an "LR" occurence we can just swap it and it's done

  • »
    »
    14 months ago, # ^ |
      Vote: I like it -25 Vote: I do not like it
    import java.io.BufferedOutputStream;
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.io.PrintWriter;
    
    public class HallOfFame {
       public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          PrintWriter pw = new PrintWriter(new BufferedOutputStream(System.out));
    
          int t = Integer.parseInt(br.readLine());
          while (t-- > 0) {
             int n = Integer.parseInt(br.readLine());
             String str = br.readLine();
    
             int cR = 0;
             for (int i = 0; i < n; i++) {
                if (str.charAt(i) == 'R') {
                   cR++;
                }
             }
    
             if (cR == 0 || cR == n) {
                pw.println(-1);
                continue;
             }
    
             int res = 0;
    
             for (int i = 0; i < n - 1; i++) {
                if (str.charAt(i) == 'L' && str.charAt(i + 1) == 'R') {
                   res = i + 1;
                   break;
                }
             }
    
             pw.println(res);
    
          }
    
          br.close();
          pw.flush();
          pw.close();
       }
    }
    
    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I know this too I just want to know that why it's not 1 but i+1. Only 1 can do the work or not?

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

        Consider the case: RRRLLR. If you intended to swap index 1 (or the 0th index), you fail to illuminate the trophy since index 1 and 2 are the same. Obviously, 'L' and 'R' are not fixed at index 1, so outputting 1 will be unreasonable.

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

          I am so stupid I didn't read it right I thought it said to input the operation .

          So stupiddddddddddd of me!!!!!!!!!!

»
14 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Queue forces on C and D

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

my sol for C was basically to do some math. Starting at m you check all the contiguous sums down from m and up from m. For the sums on the left, they have to be less than or equal to 0 and for the sums on the right, they have to be greater than or equal to 0

Did anyone use a similar approach that worked? I got a WA on pretest 2.

Edit: So I looked at the editorial and while I'm still not clear on the solution, its helped. However, can someone poke holes at my logic here? I manipulated the inequality for cases where k was smaller than m and for cases where k was larger than m. When you do that, you get the following inequalities:

Case 1: (k < m) a_k+1 + a_k+2 + a_k+3 + . . . + a_m <= 0

Case 2: (k > m) a_m+1 + a_m+2 + a_m+3 + . . . + a_k >= 0

So for the first case, you get these inequalities that I've numbered on the left

(1) a_m <= 0

(2) a_m + a_m-1 <= 0

(3) a_m + a_m-1 + a_m-2 <= 0

. . .

(m-1) a_m + a_m-1 + a_m-2 + . . . + a_2 <= 0

For the second case, you get these inequalities that I've numbered on the left

(1) a_m+1 >= 0

(2) a_m+1 + a_m+2 >= 0

(3) a_m+1 + a_m+2 + a_m+3 >= 0

. . .

(n-m) a_m+1 + a_m+2 + a_m+3 + . . . + a_n >= 0

So I assumed that as long as you solved these cases independently and in order, you would get the optimal answer (go through inequalities numbered 1 through m-1 in case 1, and then go through the inequalities numbered 1 through n-m in case 2.

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

    For the sums on the left, you must iterate till i > 0, not i >= 0. Had made the same mistake at first. AC code: https://codeforces.com/contest/1779/submission/187800612

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

      I did do this in 187817105 though

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

        I did the same thing, we are not considering the maximum number from each subarray, I don't know why we should take that though in the pq

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

          How then would you find the max when you need it?

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

        As explained in the editorial you need to choose such element to perform operations on that causes our target prefix sum to decrease as much as possible. Current element i.e. $$$arr[i]$$$ will not always be that element.

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

          Could you help provide a test case that showcase why it is necessary? Thanks in advance!

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

      did this because I assumed n == 1 is a special case :/

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

      But Why?

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

      Thank you for your code.I got it now. :)

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

      hey! , can you explain the reason for making i>0 instead? I was also making the same mistake but I didn't get why it doesn't work.

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

    If you are still not clear, consider the inequalities a_m+1 + a_m+2>=0, let say they are 4 and -4 respectively, so techincally you dont need to change anything and now lets the next inequality , let a_m+3 be -2 so, now the sum is <0 , so you must change some elements, which will you prefer to change -2 or -4, obviously -4 since it contributes more to the positive sum, thats why you need to keep a priority queue or set for this purpose

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

      Thanks so much! That test case is pretty eye-opening.

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

    Your approach is right! You have to consider one more thing.

    Case 1: (k < m) a_k+1 + a_k+2 + a_k+3 + . . . + a_m <= 0

    In this case, there can be u and v (u > v) such that, a_u + a_u+1 + . . . + a_m-1 + a_m <= 0 will hold, but a_v + . . . + a_u + a_u+1 + . . . + a_m-1 + a_m > 0

    Here, I think you are changing the sign of a_v. What if a_u > a_v?

    Changing the sign of a_u will be more significant than changing the sign of a_v.

    I think your algorithm changes the sign of a_u instead of a_v!

    Think what will happen. You will find the error. Your approach is correct. I got the correct verdict from your approach.

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

      Thanks for the comment! That was the problem I had lol. This was a really educational C!

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

    can u explain the logic of ur solution. i dont understand the first part where u are taking a1 + a2 + a3___ +am<=0

    Upd:- Thanks i have understood the code

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

Why is this solution to C wrong? 187783695

  • »
    »
    14 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    you are storing all the elements at first and then trying to compute the number of operations this doesn't take into consideration that a element at index X s.t. X<M would have the choices of only the elements in range (X,M] for negating in order to make any relative change to the values. .

    please see this for reference: https://youtu.be/kzCF4qpsjWQ let me know if you need further help :)

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

      i_pranavmehta, variety-jones Can you tell me what i'm doing wrong? Here is my approach-

      case1: i<m, then we calculate the sum and compare with it preSum(a1+a2+...am) and if it is smaller than preSum, then we do an operation on the maximum element in subarray (0,m). case2: i>=m, then we calculate sum, and if it is smaller than preSum, we do the operation on the minimum element. I don't know what I'm doing wrong. Here is my submission I'd Your text to link here...

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

    Take a look at Ticket 16656 from CF Stress for a counter example.

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

Could someone help? Why I got runtime 187832356

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

wow, so fast!

»
14 months ago, # |
  Vote: I like it +8 Vote: I do not like it

super fast

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

E is brilliant!

»
14 months ago, # |
  Vote: I like it +11 Vote: I do not like it

submitted editorial in 0ms

»
14 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Damn, B was very sneaky! Great problems!

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

    I messed up the maths once and kept wondering why is the solution wrong :P

»
14 months ago, # |
  Vote: I like it +42 Vote: I do not like it

Bonus for E (hopefully it's correct :)) Let's find outdegree for all people, call it deg[i]. It's sufficient to find minmum R such that there exists subset of people of size R such that their sum of outdegrees equals nCr(R, 2) + R * (N — R). I was thinking about this during contest but how do you implement it if you want to recover answer as well?? I mean can you do this faster than O(N^4), and in particular in better space complexity?

Btw amazing problemset.

»
14 months ago, # |
  Vote: I like it +3 Vote: I do not like it

My first contest in my life and the first contest in 2023

»
14 months ago, # |
  Vote: I like it -8 Vote: I do not like it

For problem F, the editorial says "Time complexity is $$$O(n.A^2)$$$ and memory complexity is $$$O(nA)$$$. It is possible to optimize this, but not necessary". I believe my code has the same complexity as said above but it got TLE at test 10 :( 187833020

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

    Never mind, I figured it out. Because of vector assignment(s).

»
14 months ago, # |
  Vote: I like it +1 Vote: I do not like it

The way you meet the New Year is the way you live the whole year: that fast editorial for all 2023 contests :)

»
14 months ago, # |
  Vote: I like it +5 Vote: I do not like it

The n = 3 case in B was really terrifying.

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

Why did we look for i > j in problem E (lemma 2)? It seemed to me that i < j should. If I'm wrong, please explain why.

Sorry for my poor English

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

    You are right! $$$i<j$$$ should have been written. Thank you for pointing it out, I fixed it now.

»
14 months ago, # |
  Vote: I like it +3 Vote: I do not like it

FST is not a funny joke.

About E:

Interactive problems takes a lot time to test the sample of it , so I submit it with out testing the sample .

My program WA on pretest 2 , but pretest 2 is a sample and I don't think this should be deducted from the score .

If there many samples , and I get WA on 2 , in codefoeces's rules , should my score be deducted ? Is this a mistake ?

I don't know , TAT.

(My English is so bad.)

  • »
    »
    14 months ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    And I think E is a good problem . But many people solve it with mindless guessing.

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

    Only the first pretest is penalty-free, as per the rules.

»
14 months ago, # |
  Vote: I like it +31 Vote: I do not like it

I think that the author should swap E and F, it's so confusing.

»
14 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Bonus problems. Yeah !!!

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

I even cannot come up with the lemma 1 of problem E during the contest. Perhaps I've forgotten the knowledge of the Graph Theory I've learned.

»
14 months ago, # |
Rev. 3   Vote: I like it +47 Vote: I do not like it

Bonus E :

View the match where player $$$u$$$ beat player $$$v$$$ as a directed edge from node $$$u$$$ to $$$v$$$ in a complete graph of $$$N$$$ vertices. Candidate masters are nodes that can be visited from all other nodes through some simple path (in other words, there exist a series of matches(=edges) to disqualify all other players).

All possible candidate masters are the nodes located in the last/terminal Strongly Connected Component(SCC) (SCC that doesnt have any outgoing edge to another SCC). As the graph is complete, this terminal SCC is unique.

For each node, find its outdegree. For the first $$$N-1$$$ nodes, do a simuls againts all other node(player) and count each of their loss match, with a total of $$$N-1$$$ queries. For the final node, calculate its outdegree from the remaining out/in-going edges from the previous $$$N-1$$$ nodes.

The terminal SCC (the candidate masters) are composed of the $$$x$$$ nodes with smallest outdegree such that their sum is equal to the number of edges among those $$$x$$$ nodes $$$=\frac{x(x-1)}{2}$$$. Pick minimum such $$$x$$$.

»
14 months ago, # |
  Vote: I like it +42 Vote: I do not like it
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Very fast tutorial and Bonus Problems are really interesting

»
14 months ago, # |
  Vote: I like it +2 Vote: I do not like it

I don't know why this solution gets AC while it shouldn't (Problem D)

187838626

i used sparse table for RMQ but i forgot to initialize the logs array but it passed with no problem!

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

What will be generalized approach for Problem B bonus part ?

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

Bonus task for B:

Let n = km + r where 0 <= r <= m-1. Similar with original problem we get (k-1)s_m+s_r=0, where s_m = a1 + a2 + ... + am. When k = 1, r = 1, there's no solution because in this case a1 = s_1 = 0. Otherwise there exist some { a1, a2, ..., am } satisfy the condition. We let ai = a_(i-1)%m+1 for 1 <= i <= n and get a solution.

»
14 months ago, # |
  Vote: I like it +5 Vote: I do not like it

For rank1 to rank4, all of them got "wrong answer on pretest 2" at B for one time.

What a great problem!

»
14 months ago, # |
  Vote: I like it +18 Vote: I do not like it

I used vector in the iteration of F, and get stack overflow(maybe in fact MLE?) in the system test. Can anyone explain the reason? Thank you.

»
14 months ago, # |
  Vote: I like it +4 Vote: I do not like it

As a candidate master, I even CANNOT solve the problem E which is about finding "candidate master".

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

Why in problem C we are going till i>=1 and not i>=0?

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

    Baltic's favorite number is m, and he wants a1+a2+⋯+am to be the smallest of all non-empty prefix sums.

    "non-empty" means there's no need for p0 >= pm

»
14 months ago, # |
  Vote: I like it -15 Vote: I do not like it

Even though I liked problem E myself, it felt weird that it was interactive, and not just giving degrees for each vertice, and asking the same. Can someone explain to me the reason it was given in such a way?

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

    Because red herrings make for cruel funny problems I suppose.

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

    But if they give you the degree, It became easier, because you knew that you need the out degree to solve the problem. But in problem E, you maybe think of other paths instead of asking the out degree. (Mistake path came from weaker players like me awa)

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

anyone can explain this??

problem B solution
»
14 months ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

Alternative explanation for Div2D.

Observation 1: If $$$a_i<b_i$$$ for any $$$i$$$, then the answer is NO.

So we may assume WLOG that $$$a_i \geq b_i$$$ for all $$$i$$$.

Observation 2: We can restrict to using scissors in descending order of $$$x_1 \geq x_2 \geq ... \geq x_n$$$ (i.e use taller scissors first, then go down in size). This is because if there is a solution using another order (not descending), then the same solution intervals but sorted in descending order of the scissors length is still a feasible solution.

Observation 3: We need a scissors of length $$$b[i]$$$ to cut index $$$i$$$.

Notation: For index i, let $$$nx_i$$$ denote the next index after $$$i$$$ such that $$$b[nx_i] > b[i]$$$ (i.e next bigger element in $$$b$$$). This can be preprocessed using a monotonic stack. This is a standard problem so I'll skip the details, but I'll assume you can precompute $$$nx_i$$$ for all $$$i$$$ in $$$O(n)$$$ time. See https://leetcode.com/problems/next-greater-element-ii/ for example.

I'll also treat $$$b$$$ as a set using $$$v\in b$$$ to denote a value in the array $$$b$$$.

For each $$$v \in b$$$, let $$$indices[v]={u_1, ..., u_k }$$$ be a set of all the indices with value $$$v$$$: $$$b[u_j]=v$$$. We can divide $$$indices[v]$$$ into "slots" $$$[u_1, u_2, ..., u_{i_1} ], [u_{i_1+1},..., u_{i_2}],..., [u_{i_r+1}, ..., u_{k}]$$$ where each slot is separated by an element with $$$b$$$ value greater than $$$v$$$. For example, first slot separated from second by $$$nx_{u_1}$$$, and so on.

This means that the interval for scissor with length $$$v$$$ cannot cross the slots in $$$indices[v]$$$.

Now we proceed greedily. If $$$x_i \not\in b$$$, then there is no point using $$$x_i$$$, so skip it.

If $$$x_i \in b$$$, then we look at $$$indices[x_i]$$$. Take the smallest index $$$i_{\min}\in indices[x_i]$$$, and let $$$j_{\max}=nx_{i_{\min}}$$$. We trim all the indices in $$$indices[x_i]$$$ in the range $$$[i_{\min}, j_{\max})$$$ by repeatedly removing the smallest index until the slot is entirely trimmed. Some care should be taken if $$$a_{i_{\min}}=b_{i_{\min}}$$$ since we can skip this index (without starting a new slot).

And that's it, in the end, we check if $$$a_i=b_i$$$ after all the trimming. If it is, we return true, otherwise False.

C++ Implementation Details: $$$indices[v]$$$ is implemented as a map from int (value of $$$b$$$) to set where $$$indices[v]$$$ contains all the indices with value $$$v$$$ in $$$b$$$.

Code: https://codeforces.com/contest/1779/submission/187842280

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

Can someone please explain lemma 2 of problem E in more simple words. I don’t get why degree of every vertex in Si will be higher than Sj for (i<j).Also why S1 is set of candidate masters.

»
14 months ago, # |
Rev. 2   Vote: I like it -15 Vote: I do not like it

i may sound a fool or someone who have less knowledge but in problem H cant we just do :

  1. sort the array ( not the original but make another array that have same elements )

  2. Then we have the sorted array , so 1...n/2 elements we will put in an array namely smallelements(lets say), and next n/2+1...n elements in an array namely largeelements(lets say)

  3. Then with repsect to original array we will check that whether a[i] is present in which array (smallelments or largeelements)... if a[i] is in smallelements we will print '0' else if a[i] is in largeelements we will print 1.

  4. FOR THE CASES WHERE DISTINCT ELEMENTS ARE JUST '1' we will simply print 1 for n times

  • anyone can correct me please? why my this approach is wrong?
  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why would you think that it's correct?

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

      i am not saying this is correct, but i am asking to correct my thinking

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

        An easy way to see why it's incorrect is 1 2 3 10.

        There is simply nothing correct in your solution(except that the answer is all 1s if the elements are all equal). I'm really confused by how you came up with that solution.

  • »
    »
    14 months ago, # ^ |
    Rev. 5   Vote: I like it -14 Vote: I do not like it

    Because the problem H is designed for LGMs, so if someone is not, their approach will be very likely wrong.

    Update: wtf downvote???

    Update2: It's awful to get downvoted but don't know why...

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

Fast & perfect editorial

»
14 months ago, # |
  Vote: I like it +1 Vote: I do not like it

This contest was probably not good for #1 tourist

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

That moment when you realize all that time you were trying to solve a version of $$$E$$$ where in each game only $$$1$$$ player is chosen and the other is the winner of the previous game.

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

More and more vegetable,what should I do?

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

I had great difficulty in C.

My idea was to use Segment tree but I WA on 2 many times. (Who can help to hack me? Please)

The Segment Tree includes the maxinum and the mininum of each section.

First, Reverse traversal [1~m-1].

s1 = 0

if sum[i] < sum[m] — s1:

s1 = s1 + 2 * query_max{a_i+1~m}

update(the location of the maxinum, -maxinum)

Then, traversal [m+1~n].

s2 = 0

if sum[i] + s2 < sum[m]:

s2 = s2 — 2 * query_min{a_m+1~n}

update(the location of the mininum, -mininum)

Please help.... QWQ

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

will there be a tutorial for bonus problem :")

»
14 months ago, # |
  Vote: I like it +11 Vote: I do not like it

jiangly fanbase strong

lol
»
14 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

can anyone please tell me where my solution is wrong:

https://codeforces.com/contest/1779/submission/187871735

Thanks in advance

Edit: nvmi.. i was stupid

»
14 months ago, # |
Rev. 3   Vote: I like it +26 Vote: I do not like it

Bonus F: After using the hint 6, you will find that this problem equals to choosing some non intersecting subtrees and make them have an xor sum of $$$s$$$. After you get a solution using whatever way (not neccessary with <=6 operations), you can make it within 6 steps using this simple trick about xor vector basis, and you will find that if it is possible to do so, you will always get an answer with less than $$$\log v+1$$$ steps.

  • »
    »
    14 months ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it

    Really appreciate that there is a 'bonus' for every problem, and can keep me think deeper about those interesting problems:)

»
14 months ago, # |
  Vote: I like it +5 Vote: I do not like it

n0sk1ll, any insights on how you implemented the adaptive checker for E?

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

    Usually, adaptive jury is implemented by fixing some invariant in the input. In this one, I fixed the whole tournament graph, but allowed permutations (i.e. the resulting graph after all participants' queries have been asked will be isomorphic to the jury's initially intended one). Jury permutes the graph in a way such that the newly asked vertices will always have the smallest possible (available) out-degree, meaning that there is practically no information about the winners before $$$n-1$$$ queries are asked.

    In fact, there exists a solution which uses exactly $$$n-1$$$ queries — the tests seem to be strong. (and in practice, all fake solutions fail to squeeze into $$$2n$$$ queries, which was the constraint in the problem)

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

      Yeah, I always wondered how adaptive interactors are written. It seems an impressive idea to always have smallest possible out-degree during interaction.

      Thanks a lot for sharing!

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

I passed problem H with the following fix of the fake greedy:

While expanding from size 2 to size 4, we enumerate all the 15 ways instead of using greedy.

I don't know if it's correct or not. Can anyone prove its correctness or come up with a counterexample?

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

    My intuition suggests that this is wrong, but I also see why it may be hard to construct a counter test.

    n0sk1ll: Do you know how to construct a hack?

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

      My intuition tells me that one should still check at least $$$50\,000$$$ subsets (in a greedy solution), and that there exist counter-tests. Although, I don't have a particular hack.

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

In Problem E Lemma 2,

We can also conclude that x has a higher out-degree than y for each x∈Si, y∈Sj, i<j.

How are we able to conclude this?

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

    Please someone explain this

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

    Because for every pair (i,j) (i<j) all players in Si beat all players in Sj. If that was not the case, then Si and Sj would be the same SCC.

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

Anyone have solution Bonus Problem for C ?

»
14 months ago, # |
  Vote: I like it +3 Vote: I do not like it

1779D in second hint, I think it will be x >= bi

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

    $$$x \geq b_i$$$ is correct, I fixed it now :)

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

How did some people used DSU in solving D ? Example jiangly

»
14 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Can anybody explain me D problem solution using segment trees???

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

    I solved it using segment tree 187802839. The only purpose of the segment tree is to be able to calculate the maximum element of b in the range [l, r).

    I'll try to explain my solution.

    1. If for any i, b[i] > a[i], answer is NO.
    2. If a[i] == b[i] then this hair doesn't need a razor.
    3. If a[i] > b[i], then we need to cut hair i, and so there must be a razor with length b[i], else answer is NO.

    Now the only thing is that when we make a cut using razor x on the interval [l, r), there must not be any element of b in the range [l, r) such that b[i] > x. If there exist such b[i] > x, we will cut short i to length x < b[i] which can not be grown back.

    A conclusion from above is that maximum element of b in range [l, r) must be <= x. To find the maximum element of b in range [l, r) in O(log n) time, we use a segment tree. A even better data structure to use is a sparse table which can return the maximum of a range in O(1).

    All I do is store in a map, razor of which length will have to cut which indices. And then I try to distribute the ranges among all razors available of that length.

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

About problem H, I have two questions:

  1. How to construct a test with over $$$1000$$$ subsets we have to consider (not $$$8000$$$, just $$$1000$$$).
  2. How to implemented quickly in the meet in the middle part (I only know to use sort and binary search).
  • »
    »
    14 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it
    1. Make all (reachable) big subsets intersect. I used different strategies, the simplest of which is generating $$$15$$$ numbers close to each other by value. There will be $$$\binom{15}{8} = 6425$$$ different subsets, all having similar value, and all are intersecting. Fill the rest of the array in a way such that the "smallest" subset can be extended into a full solution, but others cannot. In practice, more than $$$1000$$$ subsets would have to be considered in any solution.

    2. Write two pointers instead of binary search. As for sorting, It is possible to sort all subsets of an array of length $$$n$$$ in $$$O(2^n)$$$. Consider that all subsets of some prefix $$$a_1, a_2, \ldots a_i$$$ are already sorted, let their array be $$$b_1,b_2,\ldots b_k$$$ where $$$k=2^i$$$, and let $$$x = a_{i+1}$$$ be the new element we consider. The new subsets we add will have sums $$$b_1+x, b_2+x, \ldots b_k+x$$$, and in that order since $$$b$$$ is sorted from previous steps. We only need to merge two already sorted arrays, which is possible in $$$O(k)$$$.

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

Can anyone explain how non-intersecting subtrees can be ensured in problem F?

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

I love these bounce problems thank you for the good contest (⁠。⁠♡⁠‿⁠♡⁠。⁠)

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

nvm

»
14 months ago, # |
  Vote: I like it +4 Vote: I do not like it

I solved problem D all by myself (after the contest of course) using a monotonic stack approach. I have no one to share it with but I feel happy because that's probably the most challenging problem I've solved with no hints

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

In problem C, I'm wondering why moving from right to left is correct than moving from left to right

»
14 months ago, # |
  Vote: I like it +24 Vote: I do not like it

We have a simple way to solve E with $$$n$$$ querys, and to be skipped.

My submission: 187829528 and the one coincides with mine: 187788613.

The code is short and simple so it is easy to be close with others without leaking I think.

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

    So how can I complain for this. :(

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

Anyone mind to post the solution for E's bonus problem?

Thanks in advance

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

In F, I have a solution in mind for finding if it is possible to get xor=0 but how to restore the steps is what I can't figure out. I would love it if someone could help. Thankyou

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

What does "we are only interested in the closest road of each direction to the big triangle's side" means in G's solution? More specifically, what does the "closet road of each direction" means?

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

    same question here. The expression is so confusing and suprisingly there are not much people talking about it.

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

Why this Seg tree implementation of D is giving WA?? https://codeforces.com/contest/1779/submission/187831216

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

Problem G's solution is very confusing. Maybe too obvious to explain the meaning of "closest road to the big triangle's side"?

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

    Solved it. "closest road to the big triangle's side" refer to the closest road that is parallel with the corresponding big triangle's side. And the proving is fun, it only takes me about 3 hours of my sleep to do the "case works"

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

For everyone struggling with H's TLE, here's a little something too TRIVIAL for the solution to mention: just ignore all the cases of which sum is lower than (S * k / 32) (k is the number of elements of the case and S is the total sum of all elements). Pretty TRIVIAL right? Works like magic(at least for me 1000ms -> 100ms) and here's the code (In Java)190213361 btw since it only takes less than 10% of the TL, it makes you wonder what will happen if you replace some of the techs with brute force.

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

Can someone help me in F? It is clear that if we can find 2 non intersecting even subtrees whose XOR sum is XOR sum of all nodes, then we can solve the problem. But why is this condition necessary?

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

202603354 Can anyone tell me why this submission for problem D fails for test 2?

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

You gave it too early, I was expecting it to be released by Hello 2024 contest

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

How can i solve this problem using DSU ??

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

Why did I have this code title? Help!!

#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <list>
#include <string>
#include <cmath>
#include <bitset>
#include<stack>

#define ll long long

#define N 200005



void solve() {
	int n; cin >> n;
	ll a[N], b[N]; 
	int cnt = 0;
	for (int i = 0; i < n; i++)
		scanf("%lld", &a[i]);
	map<int, int>use;
	map<int, int>need;
	bool flag = 0;
	pair<int, int> pi[N];
	for (int i = 0; i < n; i++) {
		scanf("%lld", &b[i]);
		if (b[i] > a[i])
			flag = 1;
		if (b[i] != a[i]) {
			pi[cnt] = { b[i],i };
			need[b[i]]++;
			cnt++;
		}
	}

	int m; cin >> m;
	for (int i = 0; i < m; i++) {
		ll num; scanf("%lld", &num);
		use[num]++;
	}

	if (flag) {
		cout << "NO" << endl;
		return;
	}


	ll f[N][20];//st表记录区间最大值
	memset(f, 0, sizeof(f));
	for (int j = 0; j < 18; j++)
		for (int i = 0; i + (1 << j) - 1 < n; i++) {
			if (!j)f[i][j] = b[i];
			else
				f[i][j] = max(f[i][j - 1], f[i + 1 << (j - 1)][j - 1]);
		}

	sort(pi, pi + cnt);
	auto p1 = 0, p2 = 1;//进行区间合并
	while (p2 < cnt) {
		if (pi[p1].first != pi[p2].first) {
			p1++; p2++;
			continue;
		}
		else {
			int k = log2(pi[p2].second - pi[p1].second + 1);
			
			if (max(f[pi[p1].second][k]
				, f[pi[p2].second - (1 << k) + 1][k]) <= pi[p1].first)
				need[pi[p1].first]--;//st表查询区间最大值

			p1++; p2++;
		}
	}

	for (auto nd : need) {
		if (nd.second > use[nd.first]) {
			cout << "NO" << endl;
			return;
		}
	}

	cout << "YES" << endl;

}
int main() {

	int t; cin >> t;
	while (t--)
		solve();

	return 0;
}


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

n0sk1ll Regarding D, don't understand in editorial, why we need to keep l small as much as possible.

I used monotonic stack and I have kept l as long as possible unless it affects any B[i] such that razer < B[i].

https://codeforces.com/contest/1779/submission/237616405