Editorial for Hello 2023

1779A - Hall of Fame

Author: n0sk1ll

1779B - MKnez's ConstructiveForces Task

Author: n0sk1ll

1779C - Least Prefix Sum

Author: n0sk1ll

1779D - Boris and His Amazing Haircut

Author: n0sk1ll

1779E - Anya's Simultaneous Exhibition

Author: n0sk1ll

1779F - Xorcerer's Stones

Author: n0sk1ll

1779G - The Game of the Century

Author: Giove

1779H - Olympic Team Building

Author: n0sk1ll

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

• 37 hours ago, # ^ | very fast comment

  • 37 hours ago, # ^ | very fast reply

    • 37 hours ago, # ^ | ← Rev. 2 →   +8 all of you very fast

      • 37 hours ago, # ^ | very fast seen

      • 37 hours ago, # ^ | not me :(

        • 37 hours ago, # ^ | very very fast

          • 36 hours ago, # ^ | late reply to something very fast

            • 36 hours ago, # ^ | very fast late reply

              • 36 hours ago, # ^ | very fast seen the very fast late reply

              • 36 hours ago, # ^ | Very last reply! Now stop!!

              • 35 hours ago, # ^ | very fast swipe....!!

              • 33 hours ago, # ^ | very fast stuff

              • 18 hours ago, # ^ | fast reply on same level

• 34 hours ago, # ^ | thank you for tutorial :)

• 37 hours ago, # ^ | 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(); } }

  • 37 hours ago, # ^ | 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?

    • 37 hours ago, # ^ |

    • 36 hours ago, # ^ | 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.

      • 36 hours ago, # ^ | I am so stupid I didn't read it right I thought it said to input the operation . So stupiddddddddddd of me!!!!!!!!!!

• 36 hours ago, # ^ | Output: For each test case print −1 if it is impossible to illuminate all trophies by performing one operation (or doing nothing). Otherwise, print 0 if you choose not to perform the operation (i.e., the trophies are illuminated by the initial positioning of the lamps), or an index i (1≤i<n) if you choose to swap lamps i and i+1.

. . .

. . .

• 37 hours ago, # ^ | 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

  • 37 hours ago, # ^ | I did do this in 187817105 though

    • 37 hours ago, # ^ | 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

      • 37 hours ago, # ^ | How then would you find the max when you need it?

    • 37 hours ago, # ^ | 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. will not always be that element.

      • 36 hours ago, # ^ | Could you help provide a test case that showcase why it is necessary? Thanks in advance!

    • 36 hours ago, # ^ | Take a look at Ticket 16655 from CF Stress for a counter example.

  • 36 hours ago, # ^ | did this because I assumed n == 1 is a special case :/

  • 35 hours ago, # ^ | But Why?

  • 21 hour(s) ago, # ^ | can you explain your solution ..

  • 16 hours ago, # ^ | Thank you for your code.I got it now. :)

• 37 hours ago, # ^ | I`m too

• 33 hours ago, # ^ | I'm stucking in the second case since I cannot get min flips I need, I'm using the same approach, just try this in the second case ... a[m] 12 -11 -2 -3 you can flip just -11 and you won't need to flip -2 and -3 so the min answer is 1 not 2

• 24 hours ago, # ^ | I also used the same approach. After reading the tutorial what I am getting is that our approach was right but it does not always lead to the optimal answer. The constraints from the math can be satisfied with lesser operations using priority queue. Like the priority queue only picks a subset of numbers from the set of numbers modified in our approach and still satisfies the constraints.

• 20 hours ago, # ^ | 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

  • 10 hours ago, # ^ | Thanks so much! That test case is pretty eye-opening.

• 36 hours ago, # ^ | ← Rev. 2 →   +1 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 :)

• 36 hours ago, # ^ | Take a look at Ticket 16656 from CF Stress for a counter example.

• 36 hours ago, # ^ | I messed up the maths once and kept wondering why is the solution wrong :P

• • 37 hours ago, # ^ | Wow, I'm so stupid. Obviously this is not equivalent to knapsack, since the answer always consists of some prefix of biggest outdegree guys...

• 36 hours ago, # ^ | Never mind, I figured it out. Because of vector assignment(s).

• 36 hours ago, # ^ | You could have derived it. check here — https://youtu.be/2L326KCBqug ,but yes it gave a feeling that for odds answer would be NO :P!

• 37 hours ago, # ^ | You are right! should have been written. Thank you for pointing it out, I fixed it now.

• 37 hours ago, # ^ | And I think E is a good problem . But many people solve it with mindless guessing.

  • 37 hours ago, # ^ | What sort of mindless guessing?

• 36 hours ago, # ^ | Only the first pretest is penalty-free, as per the rules.

• 22 hours ago, # ^ | Potatohead orz

• 35 hours ago, # ^ | ← Rev. 2 →   0 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

  • 35 hours ago, # ^ | Thanks ! Got it.

  • 10 hours ago, # ^ | I still didn't get it. Can you explain it again

• 30 hours ago, # ^ | Because red herrings make for cruel funny problems I suppose.

• 14 hours ago, # ^ | Take a look at Ticket 16663 from CF Stress for a counter example.

• 35 hours ago, # ^ | they have performed mathematical operations and resolved it ... you might find this helpful : https://www.youtube.com/watch?v=2L326KCBqug&t=4s happy coding :)

• 34 hours ago, # ^ | In problem b you can have two cases when n is even and when even is odd, this is how we derive the solution for both cases. case 1: n is even:-> let the total sum of the array be s then a1+a2+....+an=s, and we also know that a1+a2=s and a3+a4=s and so on, therefore we get the equation, s*(n/2)=s. Now since n can not be 0 we conclude that s has to be 0,so the array looks something like [x -x x -x....x -x]. case 2: n is odd:-> let the total sum of the array be s then a1+a2+....+an=s, now we already know what we have to do when n is even therefore it makes sense to divide the array as 1(odd part)+(n-1)(even part), now we can extend the idea of case 1 for a2 to an, so we know that a2+a3=s, a4+a5=s and so on.. therefore the equation becomes a1+(n/2)*s=s, and we also know that a1+a2=s. Solving these two linear equations we get a1=s*(1-(n/2)) and a2=(n/2)*s, for simplicity i took s as 1. so the array looks something like: [(1-n/2) (n/2) (1-n/2) (n/2).....(1-n/2) (n/2)] here is my implementation of the problem: https://codeforces.com/contest/1779/submission/187770011

  • 25 hours ago, # ^ | so....what if n/2 bigger than 5000?

    • 24 hours ago, # ^ | see the range of n mate, it is upto 1000, and also i took s as 1 for that purpose.

• 35 hours ago, # ^ | Why would you think that it's correct?

  • 35 hours ago, # ^ | i am not saying this is correct, but i am asking to correct my thinking

    • 34 hours ago, # ^ | 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.

      • 34 hours ago, # ^ | thanks for letting me know why it is incorrect, with time the approach will get good.

• 27 hours ago, # ^ | ← Rev. 5 →   -24 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 hours ago, # ^ | Take a look at Ticket 16662 from CF Stress for a counter example.

  • 11 hours ago, # ^ | ← Rev. 2 →   0 Thanks.. Didn't know about this.

• 25 hours ago, # ^ | ← Rev. 2 →   +11 Really appreciate that there is a 'bonus' for every problem, and can keep me think deeper about those interesting problems:)

• 20 hours ago, # ^ | 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 queries are asked. In fact, there exists a solution which uses exactly queries — the tests seem to be strong. (and in practice, all fake solutions fail to squeeze into queries, which was the constraint in the problem)

  • 20 hours ago, # ^ | 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!

• 8 hours ago, # ^ | 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?

  • 8 hours ago, # ^ | ← Rev. 2 →   0 My intuition tells me that one should still check at least subsets (in a greedy solution), and that there exist counter-tests. Although, I don't have a particular hack.

• 21 hour(s) ago, # ^ | Please someone explain this

• 21 hour(s) ago, # ^ | 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.

• 21 hour(s) ago, # ^ | is correct, I fixed it now :)

• 16 hours ago, # ^ | 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. If for any i, b[i] > a[i], answer is NO. If a[i] == b[i] then this hair doesn't need a razor. 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.

• 17 hours ago, # ^ | Make all (reachable) big subsets intersect. I used different strategies, the simplest of which is generating numbers close to each other by value. There will be 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 subsets would have to be considered in any solution. Write two pointers instead of binary search. As for sorting, It is possible to sort all subsets of an array of length in . Consider that all subsets of some prefix are already sorted, let their array be where , and let be the new element we consider. The new subsets we add will have sums , and in that order since is sorted from previous steps. We only need to merge two already sorted arrays, which is possible in .

• 9 hours ago, # ^ | ← Rev. 2 →   0 Let m=5, We need p5<p4 => p4+a5<p4 => a5<0 (regardless of a1,a2,a3,a4) We need p5<p3 => p3+a4+a5<p3 => a4+a5<0 => a4<-a5 (regardless of a1,a2,a3) We need p5<p2 => p2+a3+a4+a5<p2 => a3+a4+a5<0 => a3<-a4-a5 (regardless of a1,a2) .................

• 3 minutes ago, # ^ | Let m=5, We need p5<p4 => p4+a5<p4 => a5<0 (regardless of a1,a2,a3,a4) We need p5<p3 => p3+a4+a5<p3 => a4+a5<0 => a4<-a5 (regardless of a1,a2,a3) We need p5<p2 => p2+a3+a4+a5<p2 => a3+a4+a5<0 => a3<-a4-a5 (regardless of a1,a2) .................