### kingvarun's blog

By kingvarun, history, 7 days ago,

Greetings, Codeforces Community!

We invite you to participate in Logicode, this Friday, 16th October, 9:30pm on Codechef. This contest is hosted by DotSlash Community of Indian Institute of Information Technology, Nagpur.

The contest consists of 7 problems of varying difficulty and is 2.5hrs long. All problems in this round are prepared and tested by kingvarun, tejasdeore7, adarsh_sinhg, divyevilking, deo002, dracula28, ashok_karwa.

Huge thanks to : qazz625 initial review of problem ideas , mr_cruise for coordinating this round and Codechef Team for their invaluable help and great platform.

We hope you will enjoy the contest! Good Luck!

UPD : Editorials are uploaded on code chef, links are given below

MATMIN1

CHEFG999

FIZZA

FROD

AVGMED

THE SIEGE

• +23

 » 7 days ago, # |   0 Auto comment: topic has been updated by kingvarun (previous revision, new revision, compare).
 » 7 days ago, # |   0 All the best for the contest !!
 » 7 days ago, # |   0 All the best
 » 7 days ago, # |   -14 Legen... wait for it... DARY!
 » 7 days ago, # |   -13 all the best bro
 » 7 days ago, # |   0 Auto comment: topic has been updated by kingvarun (previous revision, new revision, compare).
 » 7 days ago, # | ← Rev. 2 →   -12 .
 » 7 days ago, # |   0 Auto comment: topic has been updated by kingvarun (previous revision, new revision, compare).
 » 7 days ago, # | ← Rev. 2 →   +1 Problems are good. Guess,contest will also be good!
 » 7 days ago, # |   0 All the best !!
 » 7 days ago, # |   0 Can you give a little more context about what do you exactly mean by "Real Life Problems". I mean aren't they usual DSA based problems? or are you talking about the background stories that are given usually in the problems?
•  » » 7 days ago, # ^ |   0 Yes,I am talking about background stories that are given in problems and also there are some DSA problems.
•  » » 7 days ago, # ^ |   0 DSA problems for all users on Codechef. All the best!!
 » 7 days ago, # |   -10 Looking forward to it bro . It will be a great contest as it is from one of the best colleges — IIITs . Btw ,Is it relevant for div2 people ?
•  » » 7 days ago, # ^ |   0 Yes, it is relevant for div2 Codechef users. All the best!!
 » 7 days ago, # |   0 All the Best
 » 7 days ago, # | ← Rev. 20 →   0 Is it at 9:30PM or 9:30AM? It may be clear for indian participants, but I guess there is no harm in being clear about time zone. (I am referring to the poster. It was the first thing I noticed on opening the blog!)
•  » » 7 days ago, # ^ |   0 9.30PM bro
 » 5 days ago, # |   0 Is the contest rated for participants of div 2?
•  » » 5 days ago, # ^ |   0 Unrated for all
 » 5 days ago, # |   0 Nice Contest Folks!
•  » » 5 days ago, # ^ |   0 Thanks dude ☺️
 » 5 days ago, # |   +8 Will an editorial be posted?
•  » » 5 days ago, # ^ |   +1 YES,it will be posted soon
•  » » » 5 days ago, # ^ |   +1 can u post the editorial??? loved the contest
•  » » » 5 days ago, # ^ |   +1 How much later will be soon kingvarun ? The contest was nice and so were the problems. I am waiting eagerly for editorial.
•  » » » » 5 days ago, # ^ |   +1 Will post by today evening bro...
 » 5 days ago, # | ← Rev. 2 →   +1 Can someone give a proof that why pairs having different parity of (i + j) are a GoodPair?
•  » » 5 days ago, # ^ |   +6 Color the grid, like a chessboard.Placing a domino is equivalent to mapping a black/white cell to its adjacent white/black cell.So, it must be clear that the count of white and black cells should be equal.Now, there are many constructive ways that tell us that it will always be possible to place the dominoes if we have only removed a pair of opposite-colored cells.
•  » » » 5 days ago, # ^ |   +3 Makes sense! Thanks a lot for this explanation!
•  » » 5 days ago, # ^ |   0 how to implement this solution ???
 » 5 days ago, # | ← Rev. 2 →   0 I am not very sure, but looking at the solutions from the leaderboard I think that the problem "SEIGE" has an incorrect solution.It seems like all the passed solutions and even the model solution will fail on disconnected graphs.This is the only possible reason I can think of right now as to why my assertions were failing during the contest.
•  » » 5 days ago, # ^ |   0 In question it is clearly given that graph cannot be disconnected
•  » » » 5 days ago, # ^ | ← Rev. 2 →   0 Hmm... I see. ̶I̶ ̶m̶u̶s̶t̶'̶v̶e̶ ̶m̶e̶s̶s̶e̶d̶ ̶u̶p̶ ̶s̶o̶m̶e̶t̶h̶i̶n̶g̶ ̶t̶h̶e̶n̶.̶EDIT You guys messed up :(
•  » » » 5 days ago, # ^ | ← Rev. 2 →   +21 Can you then explain this?https://www.codechef.com/viewsolution/38969108
•  » » » » 5 days ago, # ^ |   +5 I can explain. You actually don't check if the graph is connected, you check if you can go from some warlord to any node. But there can be $0$ warlords.Here are two my submissions: WA, RTEI got my WA during contest because of this
•  » » » » » 5 days ago, # ^ |   0 Ohh I see, but I guess that logically $x = 0$ should imply $r = 0$, but RTE (also evident from my submission above)
 » 5 days ago, # |   0 Weak test cases as always, saw many incorrect solutions being accepted for MPOW.
•  » » 5 days ago, # ^ |   0 Incorrect in which sense?
 » 5 days ago, # | ← Rev. 2 →   0 Problem: Average Median GameVerdict: WAAlso, the add function independetly has been tested(By getting AC in a different problem).I have tried out all possible assertions. Can someone spot the bug in the below code. Codemultiset>maxHeap; multisetminHeap; void add(int data){ if(maxHeap.empty() || *maxHeap.begin()>=data){ maxHeap.insert(data); int bf=(int)maxHeap.size()-(int)minHeap.size(); if(bf<=1) return ; int top=*maxHeap.begin();maxHeap.erase(maxHeap.begin()); minHeap.insert(top); }else{ minHeap.insert(data); int bf=(int)minHeap.size()-(int)maxHeap.size(); if(bf<=1) return ; int top=*minHeap.begin();minHeap.erase(minHeap.begin()); maxHeap.insert(top); } return; } void erase(int data){ if(maxHeap.find(data)!=maxHeap.end()){ maxHeap.erase(maxHeap.find(data)); int bf=(int)minHeap.size()-(int)maxHeap.size(); if(bf<=1) return ; int top=*minHeap.begin();minHeap.erase(minHeap.begin()); maxHeap.insert(top); }else{ minHeap.erase(minHeap.find(data)); int bf=(int)maxHeap.size()-(int)minHeap.size(); if(bf<=1) return ; int top=*maxHeap.begin();maxHeap.erase(maxHeap.begin()); minHeap.insert(top); } return; } int median(){ if(maxHeap.size()>=minHeap.size()) return *maxHeap.begin(); return *minHeap.begin(); } 
•  » » 5 days ago, # ^ |   +3 Its much easier to solve using PBDS. AC_CODE#include #include #include using namespace __gnu_pbds; using namespace std; #define ar array #define int long long template using oset =tree, rb_tree_tag,tree_order_statistics_node_update> ; bool ok(int n){ for(int d=2;d*d<=n;d++) if(n%d==0) return 1 ; return 0 ; } void solve(){ int n,k,ans=0; cin >> n >> k ; vectora(n); for(int &x:a) cin >> x ; oset>s ; int S=0 ; for(int i=0;i=md() && ok(av())==ok(md())) ++ans ; for(int i=k;i=md() && ok(av())==ok(md())) ; } cout << ans << '\n' ; } signed main() { int t ; cin >> t ; while(t--) solve() ; } 
•  » » » 5 days ago, # ^ | ← Rev. 2 →   0 I agree that the PBDS version is far easier. But I want to know why the above code failed.
•  » » » » 5 days ago, # ^ |   0 Sorry your fact isn't funny at all.
 » 5 days ago, # |   +1 Problems were tough . Btw ,will editorials be published for this round, on codechef ??
•  » » 5 days ago, # ^ |   +1 Yes, they will be posted soon.
 » 5 days ago, # |   +3 how to implement this question solution CHEF MAKES GOOD PAIRS problem link —
•  » » 5 days ago, # ^ |   0 The square matrix can be considered as a square chessboard with cells of black and white colour. Initially for N being odd answer is zero as remaining n*n-2 cells will be odd which can't be covered by 1x2 tile in anyway. For N equal to even we can observe that whenever we place a tile of 1x2 on chessboard it always cover a black cell and a white cell. There is no possibility that a tile covers two black or two white cells, so we can say that if one pair of cell with opposite colours are removed then it is always possible to cover the remaining cells of chessboard by 1x2 tiles , which will cover an equal numbers of squares of each colour(black and white). Now when we know the above property we can find the pairs with colour A-B , B-C and A-C simply by counting frequency of colour A,B and C on black and white cells.
 » 5 days ago, # |   +1 Can anyone explain their solution for last problem FROD ? Help Maksim1744 and others who solved it.
•  » » 5 days ago, # ^ | ← Rev. 4 →   +9 There seems to be a greedy solution, but I solved by DP because I could not handle following last type well. The complexity is $O(N\sqrt N)$.There are 4 types. determined: e.g. NNNR, LNNNR. trivial for this case. number of 'N' with no cost. unidirectional: e.g. RNNNR, LNNNNL. change first 'N' into 'L'. (number of 'N'-1) with cost 1. squashed from both sides (odd): e.g. RNNNL, RNNNNNL. 1 with no cost (the middle), (number of 'N'-2) with cost 2 (e.g. RLNNRL). squashed from both sides (even): e.g. RNNL, RNNNNL. 1 with cost 1 (e.g. RRNL), (number of 'N'-2) with cost 2. For each type, distinct values of "number of 'N'" is $O(\sqrt N)$ and each transition is represented simply.Transition for second type: $(0, c, 2c, 3c, \ldots )$ This translation can be handled by an deque.for third type is similar.for last type: $(0, 1, c, c+1, 2c, 2c+1, \ldots )$ This can be handled by splitting into $(0, -\infty, c, -\infty, 2c, \ldots )$ and $(-\infty, 1, -\infty, c+1, -\infty, 2c+1, \ldots )$
•  » » » 5 days ago, # ^ |   +1 Thank you very much. I got quite of insights.
•  » » » 5 days ago, # ^ | ← Rev. 2 →   +1 I did something similar, but I split last type into two more: either we have length two or more. If we have length two, then $(N-2)$ with cost 2 is useless, because it will be zero, so it's just $1$ with cost 1. If we have length at least 4, then it is indeed either 1 with cost 1, or $N-2$ with cost 2. And here is the idea: we don't need to use more than one of (1 with cost 1) of this type. This is because if we have at least two, we can instead use only one with cost 2, and we also will have one more unused segment. Also, if we use some (1 with cost 1), it should be the shortest one.So we will have to consider two cases: either we use one of that type or not. After that, we are left with some segments of cost 2 and some segments of cost 1. It's easy to count maximum now: sort values of each cost in descending order, calculate prefix sums and the result is $max(sum2[i] + sum1[k - i \cdot 2])$P.S.: In the third case it is 1 already and $N-3$ with cost 2, so there is no choice either
 » 4 days ago, # |   0 Auto comment: topic has been updated by kingvarun (previous revision, new revision, compare).