Greate contest,thanks!

Can't there be cycles in problem D? ( EDIT: Ignore I accidentally looked at D1 D and it said 'tree' so got confused. )

Problem D video Editorial: Solution

Brute force O(1023 * n * log(n)) ~= O(n^2 * log(n)) solution passed in part B. I simply tested all values of k from 1 to 1023 until one worked.

82505984

Video Editorials to A + B(Div.1) / D + E(Div. 2)

seemingly simpler solution for problem C

ll res=0;
while(n){
    res+=n;
    n/=2;
}
cout<<res<<endl;

I wrote "2*n — #bits set" but it gave WA. Pls correct the tutorial/editorial.

EDIT: Sorry @below, you missed the absurdism

wow fast editorial

Is there anyone "Wrong answer on test 41" in div1.A like me ?

div 2 C had so many solutions!

1.  2*n-setbits(n).

2. authors solution.

3.  my solution which I found after an hour of analysis-all 2*n give 1 , all 4*n+1 give 2,all 8*n+3 
   give 3..and so on...

Div 1 A was so confusing, their output makes ABSOLUTELY no sense. Why can't i just print 1 2 3 instead of 2 1 3?

Order does not matter!

It took me more time to solve A and B then C and D combined. I did not freak out initially and so was able to eventually solve C and D. Overall a great contest for me. Hopefully I will become an expert.

This round tests participants' English level.

Solution C is a sequence from OEIS. $$$a(n) = a(floor(n/2))+n$$$

Will the solution given by editorial of problem B of div 2 not give tle? Since,the time complexity will be O(T*N*N) which is O(N*N*N)!

Pretests for Div2 C should have been stronger.

Can someone please explain why this code for Div2 C fails:

#include <iostream>
#include<cmath>
using namespace std;
typedef long long ll;
int main() {
  int t;
  cin>>t;
  while(t--){
    ll n;
    ll res = 0;
    cin>>n;
    int highestBit = floor(log2(n)) + 1;
    
    for(int k = 0; k < highestBit; k++){
      res += (n/(pow(2, k)));
    }
    cout<<res<<endl;
  }
}

In Johnny and His Hobbies question will the given solution not give time limit as t value is also upto 1024 and we are using O(n*n) solution so it can go upto 10**9 ??

In the Div2B editorial:

It uses the observation that if $$$k$$$ satisfies the required conditions, then for every $$$s \in S$$$ there exists such $$$t \in S$$$ ($$$t \ne s$$$) , that $$$t \oplus s=k$$$.

Can someone give proof of this?

Seems like the pretests were pretty weak in Div2C and Div1A, a lot of solutions failed in System Testing.

Will the solution given by editorial of problem B of div 2 not give tle? Since,the time complexity will be O(T*N*N) which is O(N*N*N)! Please if anyone knows ,please explain me!

DIV2 B -> gave TLE in system testing on test case 7 https://mirror.codeforces.com/contest/1362/submission/82518343 Can someone please explain the reason

C was simple. I saw the pattern but couldn't implement it on time.

In problem D1A, \textbf doesn't work. In fact some of LaTeX's text commands doesn't work in codeforces. (but works in polygon)

Example :

\dots \ldots \textit \texttt \textbf \t \url

Does there exist an O(n) solution for Div2 B?

Having macro #define int long long in code for div2B Johnny and His Hobbies gave TLE at test case 7 in the system testing, after removing this macro it passed all the test cases :(. Can someone please explain

div2C has easier solution.

If we write down binary representation of numbers from 0 to n in a column. We can notice a pattern:

the first bit(counting from the right) changes its value each time as we go from 0 to n

the second bit changes its value after every second number

the third bit changes its value after every fourth number ...

I dont understand, the solution discussed for B is n^2 complexity right and for 1000 tc, the complexity will be 1000*1000*1000

For a more general version of the variant you proposed in C (which, sadly is how I read the problem in the first place), there exists an answer if and only if the frequency of the maximum frequent color is $$$ \leq n$$$.

Proof : This condition is clearly necessary as for each $$$i$$$, at max one of $$$p_{2i}$$$ and $$$p_{2i+1}$$$ can have color $$$c$$$.

For sufficiency, consider the strategy where we always choose the most frequent remaining color $$$c$$$, other than the current color (the right end of the rightmost pair) and append a pair such that $$$c$$$ is its left end. We will maintain the invariant that no color has frequency more than half of total remaining length. If $$$2 m $$$ pearls were remaining and the maximum frequency was $$$ \leq m - 1$$$, the invariant holds. Else, if there were two colors $$$p$$$ and $$$q$$$ with frequency $$$m$$$, one can either append a pair $$$(p, q)$$$ if it exists and if it doesn't exist, there must be atleast one pair $$$(p, p)$$$ and one pair $$$(q, q)$$$, and we can append these pairs in one of the two orders. Clearly, the invariant holds for the remaining length of $$$2m - 4$$$. If there is a unique color with frequency $$$m$$$, and it is not equal to the last color, the invariant holds as well.

Only remaining case is when there is only one color with frequency $$$m$$$ and it is the same as the last color. We prove that this never happens. For this, go back till the right end of a pair is not equal to $$$c$$$ (say at position $$$2i$$$), or to the beginning if there doesn't exist such a pair. In front of this pair, no pair could have had left end as $$$c$$$, else we'd have frequency of $$$c$$$ > half remaining pearls at that point. But after the position $$$2i$$$, $$$c$$$ must have been the only maximum frequent color and could have been added as the left end, so a contradiction.

Now, at the end of the process, if the first and last colors are different, we are done, as we can complete a cycle. Else, say the sequence of colors is $$$p_1 = q, p_2, \ldots, p_{2n} = q$$$. Find the last $$$i$$$ such that $$$p_{2i} \neq q$$$ and $$$p_{2i + 1} \neq q$$$ and reverse the suffix after it. If there doesn't exist such an $$$i$$$, the frequency of $$$q$$$ must have been $$$\geq n + 1$$$, as $$$p_1 = p_{2n} = q$$$ and for each $$$1 \leq i \leq n - 1$$$, $$$p_{2i} = q$$$ or $$$p_{2i+1} = q$$$.

[deleted]

Does someone mind explaining why Div.1 B works with the given solution? I still don't understand how it works!

Setting OEIS task must be banned it took me 60-70 minutes to just realise the pattern and solving the formula with bitmasking and observations after this task I was not having much time to solve an easy DIV2 D which was purely implementation based and I suck in implementation ,really I suck.

And that compared to another person who just googled it out breaks the spirit of competition and I think codeforces is not meant for such activities . Hope problem setters will not set OEIS tasks in future. Actually those who solve or do the competitive programming for learning or as a hobby and purely for improving their problem solving skills will never google out this things but such contestants are fewer and too fewer nowadays as ratism is prevailing over the programmers and they want to get ratings either by hook or crook ,which in long run is not gonna benefit. Thus Hoping my comment provides message to all those who are googling solutions during the contest.Please be motivated and happy coding

It would have been nice if the Problem Statement of Div1 A was more clear or Explanation of the 3rd test case was available from the beginning.

The statement of D was very bad. It took me 15mins to understand.

in div1A/div2D since there is no restriction on blogs for which neighbours have not been written, shouldn't a case like

6 5
1 2 
1 3
1 4
1 5
1 6
5 1 1 1 1 1

be doable by writing blog 1 first and then writing the other blogs in whatever order?

To Contest Committee: I think it's time to feel sorry first for the weak pretests and further for the weak systests.

Here is a submission for D:https://mirror.codeforces.com/contest/1362/submission/82565932

And it gets AC despite failing on:

4 3
1 2
2 3
3 4
1 3 3 1

In Div. 1 B, if you were lazy and did not want to (for whatever reason) keep track of $$$s/p^k$$$, it is also possible to pick some prime numbers from a large set of primes (let's say, from the first $$$10^9$$$) at random. If you pick enough of them, then with high probability, $$$s = 0$$$ only when these primes divide $$$s$$$. A good bound can be proven by noting that $$$p^{10^6}$$$ can have at most $$$\approx 10^6$$$ unique prime divisors. So the chance of a comparison failing would be at most $$$10^{-3m}$$$, where $$$m$$$ is the number of primes chosen. Thus, you can do some operations modulo these primes. It was actually possible to pass in the contest by picking some large hardcoded primes, but you would risk getting hacked. But without hacking, there's not really a sure way to block these solutions.

E.g., see this solution, which got uphacked: https://mirror.codeforces.com/contest/1361/submission/82528165

I suspect from the number of solves on Div1C/Div2F that many people, even in Div1 (myself included), did not know off-hand how to efficiently construct an Eulerian cycle when one exists.

Testing for existence of an Eulerian cycle is well known and easy enough to implement: A graph has an Eulerian cycle if and only if no vertex has odd degree and the vertices of positive degree form one connected component. The constructions for such a cycle I had seen, however, are not easy to directly apply to a problem of this size. The approach I came up with, which I wasn't quite able to implement within contest time, was to use (implicit) linked lists to efficiently combine cycles in the graph, and to find cycles by greedily following and removing edges not already used until there are none left.

This cycle-finding approach uses a simple invariant: At each step, either the current vertex is the start vertex and every vertex has even degree, or the start vertex differs from the current vertex and these two are exactly the vertices with odd degree. In particular, there is always another edge to follow except at the start vertex.

To create a full Euler cycle, pick an arbitrary starting vertex with positive degree, and generate some cycle from that point. Then, traverse this cycle around the graph, but whenever a vertex is reached that still has positive degree, call the basic cycle-finding method at that vertex and insert the basic cycle found at the current point in the cycle being traversed. To see that the resulting cycle includes every edge and is thus an Eulerian cycle, note that it contains every edge out of every vertex visited by the cycle. Since the set of (initially) positive-degree nodes is connected and it starts at some (initially) positive-degree vertex, this means that it visits every (initially) positive-degree vertex and hence includes every edge.

My solution, as it was ten minutes after contest end (i.e. unpolished and poorly documented but functional): 82567455

This isn't quite the approach taken by the solution in the editorial, which (at a quick glance) uses recursion to accomplish something similar using vectors. I thought about taking a similar approach, but was afraid a stack overflow might be possible on some test cases since the recursion depth might reach 250000 on malicious inputs unless special care is taken.

Can anyone tell me why my solution for B is showing tle? https://mirror.codeforces.com/contest/1362/submission/82505539

In Div2 problem A if we fix the size of max number of bits to 64 and had allowed overflow then can somebody please suggest me a solution

Solution of C is very easy:

while(q--){
    long long int a,c=0; cin>>a;

    while(a){
        c=c+a;
        a=a/2;
    }
    cout<<c<<endl;
}

language was very tricky in this round...overall good contest...thanks

I think the time limit for Div1 B could have been relaxed to 3/4s as the modulo operation is slow. Many solutions failed even if they had the desired asymptotic complexity.

Div2D/Div1A — Johnny and Contribution The hardest readforces statement ever seen.

I feel there is some issue in question A, i used a simple approach of dividing the maximum of them by minimum and then that dividend must be in powers of 2 and then i applied log to the the power value.

After this i simply from 3 two'2 to get 8 2 two's to get 4 and 1 two to get two, and it's running for the test cases in the problem.

Please help out.

link to the solution : https://mirror.codeforces.com/contest/1362/submission/82512703

Thank you

For Div2E/Div1B-Johnny and Grandmaster, why does the strategy given in the editorial works?

Not solving C cost me Another Rating Drop