Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### A.Kaan37's blog

By A.Kaan37, history, 15 months ago, ,

Saturday there will be COCI exam in this link: http://hsin.hr/coci/ You can study for the old COCI's here: https://oj.uz/problems/source/122 Also this site has an online judge. The contest will begin at:15.12.2018.14:00 GMT/UTC and it will take three hours.The registerations have begun. Good luck to everyone! NOTE: There will be Educational Codeforces Round 56 (Rated for Div. 2) at the same time Please do the Educational Codeforces Round 56 (Rated for Div. 2) a bit earlier or later.

• +18

 » 15 months ago, # | ← Rev. 2 →   0 Please do the contest another time.
 » 15 months ago, # | ← Rev. 2 →   0 Maybe it will be on Monday or at 2.00 pm.
 » 15 months ago, # |   +1 Auto comment: topic has been updated by A.Kaan37 (previous revision, new revision, compare).
 » 14 months ago, # | ← Rev. 2 →   0 How to solve D?
•  » » 14 months ago, # ^ |   +13 Here's how I solved CI have an O(N^2) solution, but it's pretty complicated and I suspect the contest authors must have something solution in mind.Let's call a light "odd" if it is flipped with the third button. First, it should be clear that the order of operations is irrelevant and doing exactly the same operation twice cancels out, so one only needs to determine whether one can flip a subset of rows and columns to leave at most K lights still on (which will be the odd lights).If N is small (up to say 18) you can do a brute-force search for which columns to flip, and after flipping them, flip any rows that are more than half-lit and check if this is a valid solution. Doing this for small N eliminates some corner cases.Suppose a solution exists. We can assume it has at most N/2 odd lights in any row or column (otherwise we could just flip that row/column and get another valid solution with fewer odd lights). We will try to construct it. We want to pick a row with less than N/4 odd lights. At most 4 rows can have >=N/4 odd lights (because K <= N), so we can just pick any 5 rows and try each of them. Suppose this row has P <= K odd lights. Now flip any other row that disagrees with this row on more than half the lights. Any other row with less than N/2-P odd lights will have the correct choice for the row flip, and a counting argument shows there can be at most 2 rows with >=N/2-P odd lights.Now flip every column that is more than half-lit. If this leaves a column with at least more than N/2-2 lights on, then it's possible that we made a poor choice (because there are those two rows which might still need to be flipped). However, there can be at most 2 such columns, so again we can try all possibilities for each other them. After deciding the columns, flip any rows that are more than half-lit, and count the remaining lights.
•  » » » 14 months ago, # ^ |   +17 For C, I wrote a greedy + randomize solution. I always choose a row/column which contributes to the current number of lamps turned on best when I flip all lamps on that row/column. In case the best row/column contributes zero, I choose a random one inside rows/columns which contribute zero. I do this because in the case below:oxxowe must flip at least one row/column at first. After that, it is easy to get a board full of lamps turned on.I made these operations under a 4.8 seconds loop and passed all the cases. I actually could not prove it yet but guess that number of iterations will not be too much.
•  » » 14 months ago, # ^ |   +9 Solution to DWork backwards through the circles, counting the number of fields that were mown that are not also mown by later circles. The grass on all these fields will be the same height at harvest. To process a circle, work one row at a time, with a data structure per row to represent which fields are present/absent. I used a std::map with an entry per contiguous interval still present, but I suspect a segment tree would work too.One concern is memory usage: each operation can grow the size of the data structure in each row. I don't have a formula to bound memory usage, but intuitively, small circles are cheap because they only update a small number of rows, and big circles aren't an issue because they mostly overlap and thus reduce the number of contiguous intervals. According to the results I used up to 13MB.
•  » » » 14 months ago, # ^ |   0 I also used a map for intervals for each row, but I cleared it out for each new row, so overall its size is upto K at any time, so I'm not sure where the memory issue is. I don't see what's false in this approach, but I can't tell since I ended up with WA for every test case...
•  » » » » 14 months ago, # ^ |   0 Oh right, I'd completely missed that the order of the loops can be swapped so that row is the outer loop and circle is the inner loop. That makes the memory concern go away.
 » 14 months ago, # |   0 How to solve E?
•  » » 14 months ago, # ^ |   0 SolutionFor a graph to be good is equivalent to being able to assign a value to every node, such that each edge value is the XOR of the values of its endpoints. Consider just a single bit position. One can assign values to the nodes using a spanning tree, then fix any out-of-tree edges that have the wrong value on that bit. It's not the only way to fix the tree (in fact there are N-1 degrees of freedom, because one can flip any in-tree edge), but it will require the same number of operations (0 if the graph is already good, otherwise 1).The bits can't be treated completely independently though: it's possible that one can fix B bits in fewer than B operations. Construct a matrix in Z2 with a row per bit and a column per edge. Any linear combination of the rows can be expressed as a single operation, so the number of operations is the rank of the matrix. Both the rank itself and the desired operations can be found by Gaussian reduction.What I haven't considered is that the degrees of freedom mentioned in my first paragraph don't necessarily have to be chosen the same for all bits. I unfortunately don't have a proof that this can't improve the solution, just intuition.
•  » » » 14 months ago, # ^ |   0 Wow my solution was so close yet so far :)
 » 14 months ago, # |   0 How to Solve B for Full Score?
•  » » 14 months ago, # ^ |   +1 Just return the smallest difference between two consecutive numbers in the input.
•  » » » 14 months ago, # ^ |   0 I feel so dumb, Lol. Thanks for the Insight.