In 1368A;C+= a=5, b=4,n=100 why the output is 7??

Can someone please explain the problem B solution ? I am not able to get from editorial.

Great contest! Though, I had a doubt regarding a different version of B, which I initially misunderstood the question for. What will we do when we will want exactly k subsequences? (Assuming that an O(N^(1/2)) solution is good enough) Can we simply keep on multiplying the count of a letter by the smallest prime factor of the remaining k(dividing k at each step) and then move on to the next letter(of the cycle) and keep on doing so until k=1?

Btw, there is an extra challenge for problem B. (I wrote about it as my puzzle.)

As mentioned in the editorial, the approach may not work well for subsequence other than "ABCDE" and "CODEFORCES". Could you find such string?

I made a video explaining problem D because I really liked the problem — https://www.youtube.com/watch?v=oHgcHjk2fIM

There are many people with these videos, so let me know if it's worth doing more, thanks!

(Well, I liked problem E too, but I didn't solve it during the contest!)

The 'smaller value of k' leads one to think, the question requires the minimum value of k in Problem C. Otherwise a good problem set!

Are the rating changes adjusted for the fact that this was open for both div. 1 and div. 2? Personally it felt a bit unfair as difference between d and e was huge and i saw many expert coders who got under 2000 but still had negative rating change. Doesn't it discourage div. 2 coders not to participate in combined rounds?

"We divide them into three sets $$$V_0$$$, $$$V_1$$$, $$$V_2$$$."

How?

what is contribution in profiles?

Better editorial to problem D

https://codeforces.me/blog/entry/78987?#comment-644649

problem D was beautiful.And the part which i liked about the contest is you have to come up with a solution after that coding part is really easy and short.

In problem 5 what does "in topological order" means and in which set a vertex with no incoming edge belong to ?

Can Someone please explain E in a simpler fashion?

Do check out our video editorials-

A: C+=

B: Codeforces Subsequences

C:Even Picture

D:AND,OR and Square Sum

Can someone help me understand the meaning of the line "At that point, all numbers should be submasks of each other." (question D). An implementation of the solution will also be appreciated. Thanks.

Your code here...
#include<bits/stdc++.h>
using namespace std;
 
int ADD(int a,int b,int c,int n)
{
    if(a>n||b>n)
    return c;
    if(a>b)
    return (a,a+b,c+1,n);
    if(b>a)
    return (a+b,b,c+1,n);
}
int main()
{
    int T,a,b,n,c;
    cin>>T;
    while(T--)
    {
        c=0;
        cin>>a>>b>>n;
        cout<<ADD(a,b,c,n)<<"\n";
    }
}

pls can anyone tell me whats wrong with my code?

Great editorial for problem F, Thanks!

I need help in understanding, why my E approach does not work. I kinda proved it should work under constraints (If it does what I want it to do).

Algorithm as follows : First you check for all nodes without incoming edges ($$$V_0$$$). Then you make a set of nodes that these nodes touch ($$$V_1$$$). Then make ($$$V_2$$$) out of those accordingly. ($$$V_0$$$) Will never be spoiled, because no edges enter them. But ($$$V_1$$$) might point to another ($$$V_1$$$), making it ($$$V_2$$$) maybe.

So I keep track of votes for being ($$$V_2$$$). votes = how many edges from ($$$V_1$$$) enter this node. Nodes with nonzero votes are the ones we remove. Now go from top to bottom, and if we meet some node that used to be ($$$V_1$$$) but got voted by someone else, I put it in ($$$V_2$$$) and undo its votes, since it does not count as good any more. Since I do this from top to bottom, I only take necessary nodes in greedy way.

The answer should give different combinations of binary trees that are less than 3 in depth, and all of them have number of bad nodes $$$\leq$$$ $$$\frac{4}{7}$$$, and each node can be associated with one such binary tree, so the answer must be also less than constraint.

After the cycle, we remove $$$V_0$$$ $$$V_1$$$ and $$$V_2$$$, also changing incoming nodes from $$$V_2$$$ since they touch the rest of the graph and continue till we have $$$V_0$$$ empty

Sumbission : 84272118

How is making a pattern a CP question?

I had a doubt in Problem E. I tried solving it like this: Form the graph and remove only those vertices which have both incoming and outgoing edges. As I remove a vertex, I also update the graph accordingly. I tried to analyze the number of vertices that I will be required to remove in the worst case. For that, we can consider the whole graph as a binary tree and what my approach is doing is that it is removing all the vertices at even levels (considering 1 based indexing of levels). In this case, the maximum vertices that will be removed will be n/2 which is less than 4n/7. However, I am getting the wrong answer on Test Case 7. Can somebody give me a counter-example or tell me if I am making a mistake somewhere. Thank you. Here is my submission link: https://codeforces.me/contest/1368/submission/84306393

Thumps up for high quality descriptive editorial. By the way, in number c "The sample picture was a red herring". I stepped into that trap.

That feel when you AC C with an ugly solution...

can any one explain the question part in D??? it says:

 If before the operation ai=x, aj=y, then after the operation ai=x AND y, aj=x OR y, where AND and OR are bitwise AND and OR respectively

Beautiful solution for E.

Anyone know any algorithms for minimizing k, or interesting bounds on k for different constraints on the graph? Does this problem have an existing name in the literature?

"The same solution can be simply rephrased as: go from left to right, and remove current vertex if it is at the end of a two-edge path"

I am writing an explanation vis-a-vis the correlation of the sets $$$V_0, V_1, V_2$$$ to the above algorithm,

Let, $$$V_2$$$ represent the set of all the removed vertices.

Now, the vertices that only have incoming edges from $$$V_2$$$ are the "roots" of a sub-graph that has been disconnected from the initial graph, let they be represented by the set $$$V_0$$$, the vertices in $$$V_0$$$ no longer have any incoming edges, therefore, they can't possibly be the endpoints of a path of length 2 or more, so according to the algorithm they don't have to be removed.

Similarly, all the "neighbours" of the vertices in $$$V_0$$$ need not be removed (they are the endpoints of paths of length 1), these "neighbours" form the set $$$V_1$$$.

P.S after reading this you can refer to the editorial for the upper-bound on the number of elements in set $$$V_2$$$, it's exactly $$$4n/7$$$.

An Interesting Problem:

In problem B Consider exactly k instead of at least k. I think it would be problem of finding number of factors <= 10 such that their sum is minimum. Prime value of k would be nightmare.

i'm a little confused about E, is it saying to just remove the node if it looks like this?

0 — 0 — 0

then remove middle to

0 — X — 0

cuz i think a lot of solutions failed that when trying to greedy like that

Hello. I need help in problem E. My submissions: this close more than 4/7 n vertices and this may leave tracks with a length of 2 or more . I found counter test where this submissions don't work. Is this possible in this task? Why my solutions work? This test 20 19

1 2

2 4

2 5

1 3

3 6

3 7

7 8

8 9

9 11

9 12

8 10

10 13

10 14

15 17

17 8

17 20

15 16

16 19

16 18

A simpler solution for E problem:

Let's invert all edges in the graph, then for each vertex in graph no more than two incoming edges. Also for each edge u -> v, u > v. We will iterate over the vertexes in ascending order and for each vertex we will check whether there is a path of length 2 from it through not deleted vertexes, if there is then we will delete this vertex.

Note that for each deleted vertex there is an edge to not deleted vertex, from which also exists edge to not deleted vertex. Since after we inverted the graph, each vertex contains no more than two incoming edges. Then each not deleted vertex contains a maximum two incoming edges from the deleted vertices, but at the same time for such vertex with incoming edges from deleted vertices there is an edge to not deleted vertex, which means that the number of deleted vertices <= 1/2(for 2 deleted vertices which have an edge to same not deleted vertex, exists 2 not deleted vertices)

In problem E: sample test case 1: if we close both 3 & 4 ,how will we reach 4 from 2 since 4 is closed so there should be no incoming edge on 4? Kindly explain sample test cases of Problem E ?

In E question : Can someone please explain how paths and tracks are different from each other and if suppose this is our graph:

1 2

1 3

2 4

does it mean that 1, 2 ,3, 4 are on the same line?

https://codeforces.me/contest/1368/submission/84323789 can anyone tell me why is TLE coming in testcase 2

Can anyone explain me the solution of Problem D elaborately. what's happening there ? I am unable to visualize it .

Why in E removing middle vertex in 2-edge path will not work?

In problem 5, Ski Accidents, What would the answer for this test case: 3 3
1 2
1 3
3 2
According to me, (4*3)/7 = 1, and by deleting any one node would satisfy conditions. That is, the answer should be 1 1, 1 2, or 1 3. But in most of the accepted solutions, it is showing 0 as the output answer. Am I right?
Even my accepted solution is also printing 0 as the answer.

I spent two hours trying to solve B, for exactly k subsequences, before i realized i miss read the problem. Anybody has an idea on how to solve this variation of the problem ?

My Doubt is for Problem C. Can Anyone Explain the Meaning of this line in Problem Statement of C:

"There are exactly n gray cells with all gray neighbours. The number of other gray cells can be arbitrary (but reasonable, so that they can all be listed)."

What i Understood with this line is :

if n=1 then a grid of four cells Can be the Answer(because it is satisfying all three conditions)

I Know i am wrong somewhere,Can Anybody Point out the Catch i am losing!

For the solution to D, it's written that x^y+xANDy=x+y. But when you set x = 3 and y = 5 for example, the equation becomes 6+1=8 which is incorrect. Can someone help me understand this claim? Thanks.

Though, I could clearly form an idea on C, I chose not to implement it. I hate those kind of problems.

Hi all, 1368D — AND, OR and square sum

Why?
2d(d+y−x), which is positive when d>0.

Thank you very much.

Auto comment: topic has been updated by Endagorion (previous revision, new revision, compare).

For the solution to F, I think $$$x + k + \dfrac{x + k}{k - 1} \leq n$$$ transforms into $$$x \leq n - k - \dfrac{n}{k}$$$, not $$$x \leq n - k - \dfrac{n}{k} + 1$$$?

Can anyone explain the side note for the editorial of problem D?

Side note: an easier (?) way to spot the same thing is to remember that f(x)=x2 is convex, thus moving two points on the parabola away from each other by the same amount increases the sum of values.

Where is the "Contest materials" in the contest page? There must be something wrong.

One optimization for problem B could be initializing every occurrence of the letters in "codeforces" to n^(0.1). The resulting numbers (Nc*No*Nd*..)will always be greater than or equal to n^(0.1) you can realise it better if you know AM(arithmetic mean)>Geometric mean principle.