codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1998.md (3323B)


      1 Source: https://codeforces.com/blog/entry/132512
      2 
      3 [1998A - Find K Distinct Points with Fixed Center](/contest/1998/problem/A "Codeforces Round 965 (Div. 2)")
      4 
      5 **Idea**
      6 
      7 Chose $A_1 = (K*X_C,K*Y_C)$.  
      8 The remaining points such that sum of x coordinates and y coordinates is 0.
      9 
     10 My submission — [275541733](/contest/1998/submission/275541733 "Submission 275541733 by aryanc403")
     11 
     12 **Video editorial**
     13 
     14 [1998B - Minimize Equal Sum Subarrays](/contest/1998/problem/B "Codeforces Round 965 (Div. 2)")
     15 
     16 **Hint 1**
     17 
     18 Sum of all elements will be equal in both permutations.  
     19 So no of such $(i,j)$ is atleast 1.  
     20 Can you find a permutation $Q$ such that this count remains 1?
     21 
     22 **Hint 2**
     23 
     24 Set $Q_i = 1$ if $P_i = N$,  
     25 Set $Q_i = 1 + P_i$ if $P_i \lt N$, otherwise
     26 
     27 **Hint 3**
     28 
     29 Set $Q_i = P_{(i+1) \mod N}$
     30 
     31 My submission — [275547485](/contest/1998/submission/275547485 "Submission 275547485 by aryanc403")
     32 
     33 **Video editorial**
     34 
     35 [1998C - Perform Operations to Maximize Score](/contest/1998/problem/C "Codeforces Round 965 (Div. 2)")
     36 
     37 **My solution is a bit overkill, check out** [neal](/profile/neal "International Grandmaster neal") submission [275613185](/contest/1998/submission/275613185 "Submission 275613185 by neal")
     38 
     39 **Hint 1**
     40 
     41 Lets forget about $A_i$ and focus on $C_i$ first.  
     42 If we have and array of $N-1$ elements $A_i$ and binary array of $N-1$ elements $B_i$.  
     43 What is the maximum median we can get using atmax $K$ operations?
     44 
     45 **Hint 2**
     46 
     47 We can binary search for median.  
     48 We can directly count how many elements are more than mid, and how many elements we can make more than median.  
     49 Using segment tree, walk on segment tree and blah blah blah............
     50 
     51 My submission — [275635373](/contest/1998/submission/275635373 "Submission 275635373 by aryanc403")
     52 
     53 **Video editorial**
     54 
     55 [1998E1 - Eliminating Balls With Merging (Easy Version)](/contest/1998/problem/E1 "Codeforces Round 965 (Div. 2)")
     56 
     57 **Hint 1**
     58 
     59 Notice that at any point all the elements are sum of continous subarray.
     60 
     61 **Hint 2**
     62 
     63 Define a function solve(L,R) which returns true, if we can convert element with weight $\sum A_L+A_{L+1}+....+A_{R}$ into an element with weight $\sum A$
     64 
     65 **Hint 3**
     66 
     67 Use greedy, for fixed index $L$ and $R$, find a minimum $nxtL$ such that $\sum A_{nxtL} + A_{nxtL+1} + ... + A_{L-1} \le A_L+A_{L+1}+....+A_{R}$, make a direct jump to $nxtL,R$ segment.
     68 
     69 **Hint 4**
     70 
     71 Do similar for $nxtR$, and memorise all the answer of solve function.
     72 
     73 My submission — [275608667](/contest/1998/submission/275608667 "Submission 275608667 by aryanc403")
     74 
     75 **Video editorial**
     76 
     77 [1998E2 - Eliminating Balls With Merging (Hard Version)](/contest/1998/problem/E2 "Codeforces Round 965 (Div. 2)")
     78 
     79 **Hint 1**
     80 
     81 For each element $j$ there is a range $(L_j,R_j)$ in which it can be present as last elemt.
     82 
     83 **Hint 2**
     84 
     85 Modify the Solve function to now return what is the minimum index $L_j$, instead of boolean earlier.
     86 
     87 Basically find minimum $L_j$ such that element $j$ can become $\sum A_1+A_2+...A_{Lj}$
     88 
     89 **Hint 3**
     90 
     91 Also for each index $i$ precalcute how much right it can go.  
     92 Use this to calculate $R_j$ based on $L_j$.
     93 
     94 **Hint 4**
     95 
     96 Otherway around you can also return this range in your solve function.
     97 
     98 My submission — [275619707](/contest/1998/submission/275619707 "Submission 275619707 by aryanc403")
     99 
    100 **Video editorial**