Apparently there is no official announcement, so I hijack this. Ask questions here.

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.

I allways wanted to write an editorial, it seems like that very simple contest is my chance to do so.

1351A - A+B (Trial Problem) This is a most trivial problem, we just need to literaly output what is written in the statement, cout<<a+b<<endl; 79277814

1351B - Square? In this problem we need to observe that we can build a square from the two given rectangles if, and only if the sum of the two smaller sides equals the longer side of one of the rects, and both longer sides are equal.

How to implement this? Well, since there are four cases which sides could be the longer and the shorter ones, we can implement all four cases. Or simpler, change the side lengths of the rectangles if they are not in order. We end up with something like this

bool ans=min(a,b)+min(c,d)==max(a,b) && max(a,b)==max(c,d);

79287825

1351C - Skier First we need to understand that a "segment" in this problem is the way between two points. And the given path denotes the step from a current position to a next one, which uses one segment. We need to observe that it does not make a difference in which direction we use a segment.

For implementation it seems natural to somehow mark the used segments, and on every step check if we use a previously used segment, or a new one. We allways step from a previous position to a current position, and the current position is the previous position of the next step.

Marking a segment works fine by putting the allready seen segments into a map or set. Since a segment can be defined in two ways (the order of the two points) we can put both definitions into the set. Or while querying the set query for both. 79286682

Hello,

I am trying to solve https://cses.fi/problemset/task/1163, but got some problem to understand it. It states that "There is a street of length x whose positions are numbered 0,1,…,n. " That should be "0, 1,..., x", not n, isn't it?

Then the example:

Input:
8 3
3 6 2

Output:
5 3 3

I think output should be 5, 3, 2, not 5, 3, 3. Since obviously the longest segment without a traffic light is 2, not 3.

0 1 2 3 4 5 6 7 8
    x x     x

Can somebody explain? A lot of people solved that problem, I think I am missing something. Thanks.

Hi,

I have got a hard time understanding the problems given in the Quantum contest. So, to understand the sentence I first have to understand the words. To understand the words, I have to recognize the characters... kind of like starting at zero.

So, where is the entrance, the "Hello World" tutorial which makes me understanding even the notation of the problems, described for example here: Wikipedia Bra-Ket

Thanks

Working with fractions usually we get a hint like "You should compute P⋅Q−1 modulo 109+7, where Q−1 denotes the multiplicative inverse of Q modulo 109+7."

So, I more (or less) understood what that means. I can express, say 1/5 by the number 400000003. I can calculate that number using https://www.geeksforgeeks.org/fermats-little-theorem/ implemented by some code I found somewhere (see below).

BUT: How do I add (and/or multiply) fractions with huge values?

i.e. how to calculate and express something like this: Let E=10e9+7 Then, how to express: ((E+1) / (E+2)) + ((E+3) / (E+4))

Any hint or link to an understandable explenation would be really helpfull. Thanks.

The code I use so far, based on that fermat thing: ' class Inv { companion object { val defaultMod = 1000000007L var MOD = defaultMod

fun toPower(a: Long, p: Long, mod: Long = MOD): Long {
            var a = a
            var p = p
            var res = 1L
            while (p != 0L) {
                if (p and 1 == 1L)
                    res = res * a % mod
                p = p shr 1
                a = a * a % mod
            }
            return res
        }

        fun inv(x: Long, mod: Long = MOD): Long {
            return toPower(x, mod - 2)
        }

        fun simpleInf(nenner: Long, zaehler: Long): Long {
            return nenner * Inv.inv(zaehler) % Inv.MOD
        }
    }
}

'