Codeforces round #435 editorial

Revision en7, by mohammedehab2002, 2017-09-17 21:44:01

[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 .

Problem author : mahmoudbadawy .

Solution link (me) : TODO .

Solution link (mahmoudbadawy) : TODO .

Your thoughts are welcome in the comments .

[problem:E]

Let's write f(j) in another way:-

Now we have 2 sums, The first one is constant (doesn't depend on j), For the second sum we can calculate all its possible values using sliding window technique, Now we want a data-structure that takes the value of the first some and chooses the second sum in a good time .

observation: We don't have to try all the possible values of f(j) to minimize the expression if the first sum is c, We can try only the least one greater than  - c and the greatest one less than  - c because for any other f(j) you can prove that the expression will be greater than at least one of them, To do this we can keep all the values of f(j) and try elements numbered

Unable to parse markup [type=CF_TEX]

and

Unable to parse markup [type=CF_TEX]

bound( - c) - 1 and choose the better.

Now we have a data-structure that can get us the minimum value of the expression once given the value of the first sum in O(log(n)), Now we want to keep track of the value of the first sum .

Let the initial value be c, In each update, If the length of the updated interval is even, The sum won't change because x will be added as many times as it's subtracted, Otherwise x will be added to c or subtracted from c depending of the parity of l (the left-bound of the interval) .

Time complexity : O(n + m + qlog(m)) .

Problem author : mahmoudbadawy .

Solution link (me) : TODO .

Solution link (mahmoudbadawy) : TODO .

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en37 English mohammedehab2002 2017-10-28 02:52:57 0 (published)
en36 English mohammedehab2002 2017-10-28 02:52:04 2 Tiny change: 'r be stores in $all$,' -> 'r be stored in $all$,' (saved to drafts)
en35 English mohammedehab2002 2017-09-21 14:27:38 0 (published)
en34 English 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 English mohammedehab2002 2017-09-20 22:58:24 0 (published)
en32 English 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 English mohammedehab2002 2017-09-19 22:48:59 0 (published)
en30 English mohammedehab2002 2017-09-19 22:47:46 60
en29 English mohammedehab2002 2017-09-19 22:45:52 244 (saved to drafts)
en28 English mohammedehab2002 2017-09-19 20:26:52 0 (published)
en27 English mohammedehab2002 2017-09-19 20:26:04 50 Tiny change: 'n[problem:F]\n\nFirs' -> 'n[problem:862F]\n\nFirs'
en26 English mohammedehab2002 2017-09-19 20:23:58 426
en25 English 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 English mohammedehab2002 2017-09-19 12:34:58 3 Tiny change: 'stogram the contains ' -> 'stogram that contains '
en23 English mohammedehab2002 2017-09-19 12:22:24 730
en22 English mohammedehab2002 2017-09-18 21:09:10 52
en21 English mohammedehab2002 2017-09-18 21:07:16 177
en20 English mohammedehab2002 2017-09-18 20:54:38 242
en19 English mohammedehab2002 2017-09-18 18:45:08 18
en18 English mohammedehab2002 2017-09-18 18:39:35 231
en17 English mohammedehab2002 2017-09-18 18:18:15 288
en16 English mohammedehab2002 2017-09-18 16:02:34 110
en15 English mohammedehab2002 2017-09-18 15:53:55 240
en14 English mohammedehab2002 2017-09-18 15:23:54 28
en13 English mohammedehab2002 2017-09-18 15:22:00 39
en12 English mohammedehab2002 2017-09-18 15:19:11 1535
en11 English mohammedehab2002 2017-09-18 15:11:10 12
en10 English mohammedehab2002 2017-09-18 15:08:16 14
en9 English mohammedehab2002 2017-09-18 15:01:03 4080
en8 English mohammedehab2002 2017-09-17 21:45:21 11
en7 English mohammedehab2002 2017-09-17 21:44:01 188
en6 English mohammedehab2002 2017-09-17 21:41:36 1236
en5 English mohammedehab2002 2017-09-17 21:28:24 11
en4 English mohammedehab2002 2017-09-17 21:27:42 6 Tiny change: '-b_{i+j})|=|\sum\lim' -> '-b_{i+j})|$\n\n$=|\sum\lim'
en3 English mohammedehab2002 2017-09-17 21:26:23 1 Tiny change: '}*b_{i+j}|' -> '}*b_{i+j}|$'
en2 English mohammedehab2002 2017-09-17 21:25:24 438
en1 English mohammedehab2002 2017-09-17 20:57:21 5044 Initial revision (saved to drafts)