### spookywooky's blog

By spookywooky, history, 4 years ago, This is unofficial editorial to first Div4 contest Codeforces Round 640 (Div. 4). Please be lenient, this is my first editorial of a real contest.

In 1352A - Sum of Round Numbers there is a definition of a number to be "round". To create the set of round numbers we need to observe that every single digit of the initial number can be used to create a round number. Just add the numbers of zeros according to the position of the digit. ie "123" becomes "100 20 3". 79585673

1352B - Same Parity Summands ask us to create a set of numbers where the sum equals a given n. The summands are limited to be all odd or all even, and the number of summands is given as k. So it turns out it is a case work of n and k being odd or even.

If n is odd and k is even there is no solution, since an even number of summands of same parity will allways result in an even sum.

If n is odd and k is odd we can construct a solution by using 1s and a last, bigger number as $n-k+1$. But we need to check if $k{\geq}n$ since if it is not then there is no solution.

If n is even and k is even the previus solution works, too.

Last case n is even and k is odd. Here we cannot use 1s as summands, because if we do the sum will be odd, but it must be even. So we use 2s intead of 1s. Therefore we need to check that $k\cdot2{\leq}n$ and use last number as $n-2\cdot(k-1)$ 79585325

1352C - K-th Not Divisible by n is a bit mathy. We need to find a number not divisable by n where $k-1$ lower numbers exist not divisable by n. How to do that?

To tell for a given number how much lower/equal numbers exist being divi by n is simple, it is: $k-\frac{k}{n}$ Since every nth number is divi by n we can use blocks of size n to calculate the solution. A block of n numbers has $n-1$ numbers not divi by n. So we need to use $\frac{k}{n-1}$ blocks, plus the remainder of the blocksize. But there is a flaw with this. If the remainder is zero. To workarround that, we can subtract one from solution, and then add one until solution fits.

However, I hope there is a simpler definition, too ;) 79585352

1352D - Alice, Bob and Candies has lengthy statement to make all points clear. We just need to implement all those details. I did using a left pointer and a right pointer. Then, in a loop, I add elements from left according to the rules, and then elements from the right, until left and right meet somewhere in the middle. There the loop ends and the collected numbers can be printed. 79585700

1352E - Special Elements ask to find the number of elements of an array where the sum of some consecutive subarray equals the element. Seen from the other end it is, for every possible sum is there such an element in the array, lets count such elements. The constraint of max 8000 elements gives us a hint that the solution should work in $O(n^2)$

First, collect the frequency of all elements of the array. Then lets make a loop over all elements of the array, and on every step maintain a list of the sums of all subarrays ending at that position. This list of sums can be created on the fly by adding the current element to all existing sums, and afterwards adding the current element as a new sum to the list.

Example for an array with elements $[1, 17, 3, ...]$. After third, before fourth step the list of sums will contain the elements $[1+17+3, 17+3, 3]$.

So, on every loop we create an inner loop over the sums so far, and check using the frequency array how much elements with the sum exist, adding that number to ans.

Since it is asked how much such elements exist, not how much subarrays, we need to care that every element is counted only once. Just set the frequency of an element to zero after having counted it once. Then it is counted as zero the next time, which does not hurt. 79585727

1352F - Binary String Reconstruction makes us constructing a string of 1s and 0s. We are given 3 numbers, which are the number of substrings "00", number of substrings "01" or "10", and number of substrings "11". The constructed string must match these numbers.

One option to create it is first putting the "00" as much as needed, then the "11" as much as needed, then alternating 0s and 1s until n1 is fullfilled. We need to be careful for some corner cases if numbers are zero. But there is no need to check for inconsistency, since the statement says the numbers are so that it is allways possible to create the string. Ie there is no input like 1 0 1. 79585755

1352G - Special Permutation We are aksked to create a permutation of given lenght with adjcent elements being "near" to each other, the diff must be within $(2,4)$. In the examples there is one such array of size 4, it is $[2,4,1,3]$

How to create longer such permutations? Observe that we can reuse the one of length 4 by putting one after the other $[2, 4, 1, 3, 2+4, 4+4, 1+4, 3+4, 2+8,...]$. But by this pattern we can create only permutations of length multiple of 4. If we had solutions of size 5, 6 and 7, we could put them after some of size 4...

I used pen and paper to find such ones: $[1,4,2,5,3], [1,4,2,6,3,5], [1,4,2,6,3,7,5]$ One might use brute force to find them programatically. Edit: And as I just noticed, in the example there are two of length 6 and 7, too.

So we can construct the final permutation by putting $\frac{n}{4}-1$ arrays of size 4 one after the other, and then add one of size $4 + n\%4$

Note that for $n{\lt}4$ there is no solution. 79585776

I hope you enjoyed the contest and level up to Div3 soon. div4, Comments (35)
| Write comment?
 » Auto comment: topic has been updated by spookywooky (previous revision, new revision, compare).
 » 4 years ago, # | ← Rev. 3 →   At first, I thought about the same solution of G, but then come up with simper (in my opinion) solution. We can put elements $[3, 1, 4, 2]$ in the deque (2-ended queue) and then put odd elements to the one end and even elements to the other end. For example, for $n = 8$ we will get $[8, 6, 3, 1, 4, 2, 5, 7]$. Code
•  » » I also used exactly the same method :).
 » Simple solution for G !Put odd elements first in decreasing order then from even elements first put 4 then 2 then same order from 6 till last even element in increasing order.
 » Can anyone help me with QE? I think I did O(n^2) but I still got TLE on test 6. Thank you in advance.https://codeforces.com/contest/1352/submission/79573682
•  » » 4 years ago, # ^ | ← Rev. 2 →   It does not look that bad to me. Try using an array instead of the map, then it should be O(n^2) instead of O(n^2 * log(n)) and hence run 10 times faster.
•  » » » Wow it worked :) Thanks a lot!
•  » » You can use an unordered map as well.
•  » » » Oh yeah I forgot... Thanks!
•  » » The condition in your if statement if (sum <= n && mp[sum]) is the cause of your problem. The problem here is that the square brackets you have used to check whether the frequency of sum is >0 or not is the cause of TLE. What square brackets overload does that first it checks whether the sum is in map or not and if found, it simply returns the value of it and if not found, it inserts the value and the return 0 (default frequency).This doesnot means that changing this will solve the problem but keep this in mind. Just change the if condition to if(sum <= n && mp.find(sum) != mp.end() && mp[sum] > 0)
•  » » » 4 years ago, # ^ | ← Rev. 2 →   Does this mean that if it's not found the time complexity is O(1) and if it exists the time complexity is O(log N)?Also, what is the difference between unordered_map and map (except for the runtime)? Thanks!
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   No, the complexity in both case (if the element present in map or not) is O(log n). The only difference is that the square bracket first checks if the element is present in map of not (time complexity of this is O(logN)) and if present is simply return the value associated with it and if not present is creates a new node in map and then returns 0.And about the difference between the map and unordered_map can be found here Stackoverflow answer
•  » » » » » Oh... Thank you so much!
 » Can anybody pls help that why O(n^2) for question E works ... coz the final complexity would be t * n * n and in worst case that goes like 64 * 1e9 ... I mean it doesn't fit into 1 sec bounds .... I think m missing something ... pls help, would be much appreciated .....
•  » » 4 years ago, # ^ | ← Rev. 2 →   "It is guaranteed that the sum of the values of n for all test cases in the input does not exceed 8000."Which is kind of standard, this statement can be found in a lot or most of problems with a t like this.
•  » » » the moment i saw the ques .. I had the n^2 soln ready in mind .. I went for looking better after seeing the constraints .. Now I missed points .. sed life
•  » » » » Solving three in the first contest is not bad. I solved zero in my first
•  » » » » » Thanks! That motivates... Btw by what time ratings come... Noob here doesn't really know how codeforces works
•  » » » » » » The current contest has a 12 hour hacking phase. So you can still raise your position in the competition by hacking other participant on positions before you.After end of hacking phase some final work is done which ends with updating the ratings some hours later.
•  » » » » » » Right now, it's the open hacking phase for approx 8 hours more. You can expect rating changes till about 14 hours or so
 » Why is this showing that the blog was posted 10 hours ago?
•  » » Because it was. I tested the problems yesterday evening and wrote the first version of the editorial aprox 10 hours ago, this morning.
•  » » » May I know how are the testers chosen for a contest
•  » » » » Round coordinators and problemsetters choose them. You may offer your help, the names of the people are posted with every contest.
 » Some tips about Latex: use \leq for $\leq$, \geq for $\geq$ use \times for $\times$, \cdot for $\;\cdot\;$, better than $*$ for multiplication. use \frac{a}{b} for $\frac{a}{b}$, better than $a/b$ (in some situations).
•  » » Yes, looks better, thanks. What is the mathematical notation and lex symbol for mod, ie $n\%k$ ?
•  » » » The way modular arithmetic is notated in math is different from the way it is used in CS, i.e. in math notation we write $a \equiv b \bmod m$ (you can right click an equation to see the tex commands for it), which is about a relationship between two numbers, whereas in programming we use modulus as an operator, i.e. just $a\bmod m$. You can use $\%$ or $\bmod$, people will understand it either way, although $\%$ is more concise and doesn't get confused with the other notation.
 » I'd like to introduce my binary search solution for problem C: 79542960.Explanation: Search for the smallest number valid. We check validation by the following equation: $mid-{{\left \lfloor{mid\over{n}}\right \rfloor}}$ if that equation is equal to $k$, then that is the answer. But might not be optimal. So, binary search for the smallest.
 » In 1352E,We can just double loop and add sum of subayyays in set,if sum exceeds maximum element of array we will break inner loop.This will insure that our set at max have 8000 elements as 1<=a[i]<=8000.Here is my code for this, 79605945
•  » » Yes, I think this is the more clean algorythm since we do not need an extra array for the frequencies.But I feel you should not use a set for storing the sums, instead use vector of size $n+1$, setting the found sums to true. Breaking the loop on $sum{\gt}n$ does not hurt, but is not necessary. The code must also work without this, since the numbers can be so small that the sum nearly never exceeds n.
•  » » » Yeah,it is better to use vector then set.
 » what is the complexity?
•  » » The complexity of creating such a supposedly simple editorial is surprisingly high. My daily message limit exceeded and just consider all the questions!Big_O_notation
 » I Solved Problem E with two methods (One got Accepted Other got TLE)1)I used an array to maintain the sum of every segment which Got Accepted Solution-797172642)I used map to maintain the sum of every segment which Got Time Limit Exceeded on test 6. Solution-79717344Can Anyone Tell what is a reason behind it? Thanks in advance.
•  » » It is as simple as that, the map is significantly slower than the array.