Codeforces round #435 editorial

Правка en1, от mohammedehab2002, 2017-09-17 20:57:21

[problem:A]

One can see that in the final set all the elements less than x should exist, x shouldn't exist and any element greater than x doesn't matter so we will count the number of elements less than x that don't exist in the initial set and add this to the answer, If x exists we'll add 1 to the answer because x should be removed .

Problem author : mahmoudbadawy .

Time complexity : O(n+x) .

Solution link (me) : TODO .

Solution link (mahmoudbadawy) : TODO .

[problem:B]

The tree itself is bipartite so we can run a dfs to partition the tree to the 2 sets, We can't add an edge between any 2 nodes in the same set and we can add an edge between any 2 nodes in different sets so let the number of nodes in the left set be l and the number of nodes in the right set be r, The maximum number of edges that can exist is l * r, n - 1 edges already exist so the maximum number of edges to be added is l * r - n + 1.

Problem author : me .

Time complexity : O(n) .

Solution link (me) : TODO .

Solution link (mahmoudbadawy) : TODO .

[problem:C]

There are multiple ideas for this problem, I will mention some of them.

Common things : n = 2, x = 0 is the only case with answer "NO" and PW = 217 .

First solution by me

Let's define a block of integers as 4 consecutive integers where the first one is divisible by 4, The bitwise-xor sum of a block is 0.

proof: let the first integer be x, as x is divisible by 4, , and so the bitwise-xor sum is

So let's print some blocks and reduce n by 4 until n is 4 or less, Don't print the block that starts with 0 or the block that contains x (You'll know why later) .

Now we want a bitwise-xor sum equals x with n ≤ 4, Let's try to find a set of integers such that for any n ≤ 4 and x, There exists a subset of it with size n that has the bitwise-xor sum x, Try to prove that the set fulfills the condition, You can try all its subsets that has n elements in O(94) or O(9!), We didn't use the block (0, 1, 2, 3) or the block that contains x because we need them in our set.

Second solution by mahmoudbadawy

First print 1, 2, ..., n - 3 (The first n - 3 positive integers), Let their bitwise-xor sum be y, If x = y You can add PW,PW * 2 and , Otherwise you can add 0,PW and .

Handle n = 1 (print x) and n = 2 (print 0 and x) .

Problem author : mahmoudbadawy .

Solution link (me) : TODO .

Solution link (mahmoudbadawy) : TODO .

Your thoughts are welcome in the comments .

[problem:D]

There are also multiple solutions to this problem .

In the editorial we suppose that the answer of some query is the number of correct position which is n-(the hamming distance), For convenience.

Common things : Let zero(l, r) be a function that returns the number of zeros in the interval [l;r] minus the number of ones in it, We can find it in one query after a preprocessing query, The preprocessing query is 1111..., Let its answer be stores in allones, If we made a query with a string full of ones except for the interval [l;r] which will be full of zeros, If this query's answer is cur, zero(l, r) = cur - all, That's because all is the number of ones in the interval plus some trash and cur is the number of zeros in the interval plus the same trash .

First solution by mahmoudbadawy

Let's have a searching interval, initially this interval is [1;n] (The whole string), Let's repeat this until we reach our goal, Let mid = (l + r) / 2 Let's query to get zero(l, mid), If it's equal to r - l + 1, This interval is full of zeros so we can print any index in it as the index with value 0 and continue searching for an index with the value 1 in the interval [mid + 1;r], But if its value is equal to l - r - 1, This interval is full of ones so we can print any index in it as the index with value 1 and continue searching for a 0 in the interval [mid + 1;r], Otherwise we can continue searching for both in the interval [l;mid], Every time the searching interval length must be divided by 2 in any case so we perform O(log(n)) queries .

Second solution by me

Let's send 1111... and let the answer be ans1, Let's send 0111... and let the answer be ans0, We now know the value in the first index (1 if ans1 > ans0, 0 otherwise), We can binary search for the first index where the not-found value exists, which is to binary search on the first value x where zero(2, x) * sign(non - foundbitvalue) ≠ x where sign(y) is 1 if y = 0,  - 1 otherwise .

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en37 Английский mohammedehab2002 2017-10-28 02:52:57 0 (published)
en36 Английский mohammedehab2002 2017-10-28 02:52:04 2 Tiny change: 'r be stores in $all$,' -> 'r be stored in $all$,' (saved to drafts)
en35 Английский mohammedehab2002 2017-09-21 14:27:38 0 (published)
en34 Английский mohammedehab2002 2017-09-21 14:26:53 2 Tiny change: 'str_i,str_i+1)$, That c' -> 'str_i,str_{i+1})$, That c' (saved to drafts)
en33 Английский mohammedehab2002 2017-09-20 22:58:24 0 (published)
en32 Английский mohammedehab2002 2017-09-20 22:57:47 2 Tiny change: 'ty : $O(n+m+qlog(m))$ .' -> 'ty : $O(n+(m+q)log(m))$ .' (saved to drafts)
en31 Английский mohammedehab2002 2017-09-19 22:48:59 0 (published)
en30 Английский mohammedehab2002 2017-09-19 22:47:46 60
en29 Английский mohammedehab2002 2017-09-19 22:45:52 244 (saved to drafts)
en28 Английский mohammedehab2002 2017-09-19 20:26:52 0 (published)
en27 Английский mohammedehab2002 2017-09-19 20:26:04 50 Tiny change: 'n[problem:F]\n\nFirs' -> 'n[problem:862F]\n\nFirs'
en26 Английский mohammedehab2002 2017-09-19 20:23:58 426
en25 Английский mohammedehab2002 2017-09-19 13:18:36 4 Tiny change: 'd is $l*r-n+1$.\n\nTime' -> 'd is $l*r-(n-1)$.\n\nTime'
en24 Английский mohammedehab2002 2017-09-19 12:34:58 3 Tiny change: 'stogram the contains ' -> 'stogram that contains '
en23 Английский mohammedehab2002 2017-09-19 12:22:24 730
en22 Английский mohammedehab2002 2017-09-18 21:09:10 52
en21 Английский mohammedehab2002 2017-09-18 21:07:16 177
en20 Английский mohammedehab2002 2017-09-18 20:54:38 242
en19 Английский mohammedehab2002 2017-09-18 18:45:08 18
en18 Английский mohammedehab2002 2017-09-18 18:39:35 231
en17 Английский mohammedehab2002 2017-09-18 18:18:15 288
en16 Английский mohammedehab2002 2017-09-18 16:02:34 110
en15 Английский mohammedehab2002 2017-09-18 15:53:55 240
en14 Английский mohammedehab2002 2017-09-18 15:23:54 28
en13 Английский mohammedehab2002 2017-09-18 15:22:00 39
en12 Английский mohammedehab2002 2017-09-18 15:19:11 1535
en11 Английский mohammedehab2002 2017-09-18 15:11:10 12
en10 Английский mohammedehab2002 2017-09-18 15:08:16 14
en9 Английский mohammedehab2002 2017-09-18 15:01:03 4080
en8 Английский mohammedehab2002 2017-09-17 21:45:21 11
en7 Английский mohammedehab2002 2017-09-17 21:44:01 188
en6 Английский mohammedehab2002 2017-09-17 21:41:36 1236
en5 Английский mohammedehab2002 2017-09-17 21:28:24 11
en4 Английский mohammedehab2002 2017-09-17 21:27:42 6 Tiny change: '-b_{i+j})|=|\sum\lim' -> '-b_{i+j})|$\n\n$=|\sum\lim'
en3 Английский mohammedehab2002 2017-09-17 21:26:23 1 Tiny change: '}*b_{i+j}|' -> '}*b_{i+j}|$'
en2 Английский mohammedehab2002 2017-09-17 21:25:24 438
en1 Английский mohammedehab2002 2017-09-17 20:57:21 5044 Initial revision (saved to drafts)