Hello Codeforces!

On Sep/05/2019 17:35 (Moscow time) Educational Codeforces Round 72 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be **rated for the participants with rating lower than 2100**. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given **6 problems** and **2 hours** to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

*Hello Codeforces,*

*Harbour.Space University and UTCC are collaborating to offer graduate students from anywhere in the world a once in a lifetime opportunity: fully funded scholarships for our Masters programs in Bangkok.*

*These scholarships are designed to completely eliminate the barrier between exceptional talents and sophisticated education: they cover the entire tuition fee as well as the cost of living expenses, and furthermore, they provide the student the valuable experience of both studying and working at Harbour.Space University.*

*We’re looking for the people who are going to change the world.*

**If you or someone you know are interested in technology, entrepreneurship, or design, and believe you have what it takes, we want to hear from you!**

Congratulations to the winners:

Rank | Competitor | Problems Solved | Penalty |
---|---|---|---|

1 | Tropical_maid | 6 | 212 |

2 | Return.Hao | 6 | 246 |

3 | xyz100 | 6 | 272 |

4 | YangDavid | 6 | 280 |

5 | Lawali | 6 | 300 |

Congratulations to the best hackers:

Rank | Competitor | Hack Count |
---|---|---|

1 | VegetableP | 116:-14 |

2 | Princ_iple | 49:-1 |

3 | racsosabe | 42:-1 |

4 | shurongwang | 36 |

5 | Megatron_99 | 29:-1 |

And finally people who were the first to solve each problem:

Problem | Competitor | Penalty |
---|---|---|

A | xyz100 | 0:02 |

B | _tryhard | 0:06 |

C | Laiu | 0:06 |

D | IgorI | 0:08 |

E | Yuu | 0:30 |

F | Hasan0540 | 0:51 |

**UPD:** The editorial is out

Thanks for round! :)

:(( a funny picture. but -64 downvoted. :(( sorry i deleted it

Two funny images, why so heavily downvoted?

i don't know :(( Why??? i tried with funny comments. but -44 voted? :D what the f* ?

i think that i will not write a another comment :(( So sad..

because this is codeforces not memes center.. jokes here needs right timing so posting some joke before the round starts is not a good idea unless you're legendary grand master even if you write "potato" you'll get upvoted

oke <3

funny picture always got upvote

it seems you must get upvote then

Would anyone be interested in a round written solely by tourist?

I have never tried it so I am looking forward to it

Score distribution:

5000 — 5000 — 5000 — 5000 — 5000...As far as I know, there already was one (I think it was one of the Hello / Good Bye rounds).

tourist was a writer of Hello 2018!

Here is all of tourist's problemsetting: (https://codeforces.com/contests/writer/tourist). Some rounds are written solely or almost solely by him.

Two rounds in two days, the later one must be a good round...

Seems like Codeforces wants me to give this contest as a rated one

Hope this round will be like last educational

[deleted]

I want to know if I will lost some rating if i dont have time to join this round.....

Certainly not. You will not be considered as an official participant if you don't even make a single attempt.

What will be the difficulty of the problems? I have just started with cp.

yes

Hopefully I can gain more rating!

Wanna become blue today...

Yeah, sure, buddy. :))

I think its not so good contest

when can we upsolve the problems?

You can already start upsolving it :)

For E my time complexity was O(q*digits*log(n)) which got TL-5. How to do it better?

Use int instead of long long

My submission 60129750 got 1497 ms (complexity is the same)

the shortest form of this problem: give you number Heads, list of blows and answer the fastest way to kill it (Heads<=0). There are 2 cases here: Result=1 and Result>1. When Result=1, you just simply pick the blow with the biggest damage value. When Result>1 (2,3...), you will notice that the moment the dragon die is before the the last rivival (Heads increase again) and number Heads become not positive so the last revival will not happen, If you have Result number time of blows, obviously, first Result-1 time you will change Heads by sum of (-damage+rivive), but for last you just change Heads number by minus damage value. So with case Result>1, you just simply pick the blow with the smallest (-damage+revive) for first Result-1 blows, and the last blow you just need to pick the blow with the biggest damage to end the fight. Hope you get it. I also struggled a lots to find out this logic, simple but hard to make it right in the center quickly. EDIT: So sorry, I made a mistake. I saw something about problem B so... Forgive me

I think it's because of digit function in your code. I think it's $$$O(q*digits^2*log(n))$$$ in worst case.

Thanks!

I also had the same complexity https://codeforces.com/contest/1217/submission/60133014 got tle at tc5.. can anybody tell why?

I think it might be due to that combining nodes function(ret in your code). I had same merging function but also extra digit factor in complexity so it got well deserved TL.

i optimized it but still the same.. the time limit shouldn't be this strict

You should pick one. scanf,printf

orcin/cout with fastio.Oh F.. I didn't see that. Thanks a lot

I got 1.996s on pretests and didn't realize lol.

How to solve problem F ?

$$$last$$$ can only be $$$0$$$ or $$$1$$$, so we can make $$$2m$$$ operations and do them

offline.Is there a solution which can handle these types of queries with divide-and-conquer dynamic connectivity method?

I know it's a strange thing to ask since I am one of the authors of the contest, but nevertheless.

Assume there are $$$n$$$ vertices, $$$m$$$ edges in graph $$$G$$$, and we need to process $$$q$$$ operations.

Let's denote all the endpoints in these $$$q$$$ operations as

important vertices.Keep all the edges not mentioned in these $$$q$$$ operations in $$$G$$$, and run a linear DFS to find all the connected components.

Remove all the components that contain no important vertices, since they are useless for these queries at all.

Compress each component to a single vertex, and remark all the operations. Let's denote the compressed graph as $$$G'$$$.

Process the first q/2 operations using $$$G'$$$ recursively.

Now we know all the answer of the first q/2 queries, so we can know what the real modifications are. Do these modifications to get a new graph G''.

Process the last q/2 operations using G'' recursively.

Time complexity is T(q)=2T(q/2)+O(q)=O(q log q).

But how? I don't really understand.

I think I actually got it, how to use the segment tree trick with DCP in this problem.

For each edge, there are multiple segments where it may or may not be present (its status may change when we make a query of first type with $$$x, y$$$ or $$$x - 1, y - 1$$$). Let's add these segments in the segment tree just the way we did it in original dynamic connectivity problem, we will have no more than $$$q \log q$$$ additions into the segment tree.

Then, while we are running DFS in the segment tree, we firstly go into the left subtree, solve the problem recursively. And after we processed all queries from the left subtree,

we now know everything about all edges we could add in our right son— this is the key point that allows us to use this approach.Originally, when HellKitsune taught me the divide-and-conquer technique to the dynamic connectivity problem, I was a bit disapponted that the sqrt-decomposition trick is kinda useless in this problem — it is harder to code, it runs slower. So I wanted to create a problem that would show that sqrt-decomposition could still be better than divide-and-conquer in some cases of DCP. It turns out I failed.

But the sqrt-decomposition solution for this problem is much easier. Divide the queries into $$$K$$$ blocks. For each block, we know some edges that are always present no matter what, and each query asks us to use no more than $$$\frac{2q}{K}$$$ edges that may not present in the whole block.

can you please explain a little bit more?

I don't understand. Since $$$last$$$ could be 0 or 1 on

eachquery, doesn't that mean that in total there are $$$2^m$$$ possible chains of operations?Yes, we can have $$$2^{m}$$$ possible chains if we are trying to do it purely offline. But offline dynamic connectivity approaches can be modified in such way that we do not need to know all the queries beforehand. Instead of marking places when edge inclusion

changes, we can mark places where edge inclusionmight changeand when we will have all the information make these decisions in process whether to include edge or not do include edge for future stable segment until this edgemight changeagain.u can also solve with using dynamic connectivity

There's no such thing as online dynamic general graph connectivity as far as I know :<

Fuck, i forgot its online queries xd

There is one. It involves some really heavy magic with Link-Cut Trees.

Some accepted submissions use that approach.

Ok, looked it up. I bow to thee BledBest, I can die at peace, even as a unicorn I'm still totally mindblown by such

magic.Even as a red I am mindblown by it too.

It is called HDT algorithm. It was named after it's inventors Jacob Holm, Kristian de Lichtenberg and Mikkel Thorup. Time complexity is amortized $$$O(log^2n)$$$ per update and $$$O(logn)$$$ per query. There is also an implementation using Euler Tour Trees instead of Link-Cut Trees.

The best known algorithm for online dynamic connectivity problem runs in amortized $$$O(\frac{log^2n}{loglogn})$$$ per update and $$$O(\frac{logn}{loglogn})$$$ per query using Thorup's randomized data structure.

getting WA on test 2 in B, whats is the logic or tell me something wrong in my solution please.

link of my solution

if all d < h and has no d >= x — result -1

next chose a=max(di-hi) and b=maxd, last step max(a,b), all steps before last (b)

haha lol, I comment d>= x here. but in my contest submission write d>x)

the shortest form of this problem: give you number Heads, list of blows and answer the fastest way to kill it (Heads<=0). There are 2 cases here: Result=1 and Result>1. When Result=1, you just simply pick the blow with the biggest damage value. When Result>1 (2,3...), you will notice that the moment the dragon die is before the the last revival (Heads increase again) and number Heads become not positive so the last revival will not happen, If you have Result number time of blows, obviously, first Result-1 time you will change Heads by sum of (-damage+rivive), but for last you just change Heads number by minus damage value. So with case Result>1, you just simply pick the blow with the smallest (-damage+revive) for first Result-1 blows, and the last blow you just need to pick the blow with the biggest damage to end the fight. Hope you get it. I also struggled a lots to find out this logic, simple but hard to make it right in the center quickly.

How To Solve C..?

How to solve C with out gettin TLE on test 12 ??????????

First of all, if at a given index, s[i] == '1', then the index of the last good substring starting at i is at most (i + 20), otherwise the value of the binary number is larger than the max length of the string. So, for every index, we precompute the next occurrence of '1' and check the next 20 characters. Repeat.

i still don't understand about this one

could you explain why the last good substring starting at i is at most (i + 20) ?i is at most (i + 20),Because a binary number with length 20 and no leading zeroes is at least $$$2^{19}$$$ which is greater than the maximum possible length of the string so it can never be valid.

my solution:

precalc zeroes-array: how many zeroes before ith element

next start from first (1) and count zeroes before (from precalc), if (f-length<=number of zeroes) result++. next shift left index to next 1-characker, if length > 20 (i think it is enough) you can break from cycle.

(for example 000101)

first step: 000[1]01

number of zeroes before before = 3, f=1 and 3 enough to add to result (1-1<=3)

next step go to 000[10]1

in this case your f=2, length=2, zeroes before=3 => result++

next step got to 00010[1] — same as first step (except zeroes before = 1, but also enought 1-1<1)

next step got to 000[101] — f=5, lenght=3, number of zeroes = 3 (5-3<=3) => result++

Thanks a lot! Nice solution, really easy to code.

Your implementation and description in comments more clearly, thanks!

Good explanation.

I upsolved in similar maner using regex, where zeroes-calc are made on the fly. Solution in Perl is quite slow, it passes in 3.6s — 60140161. Regex finds every position starting with '1' and then looks-ahead upto 18 bits.

How do you get the formula if (f — length <= number of zeroes) then result++ I mean logic behind it

f — function result that we needed to achieve (for example for 111 = 7)

length — already achieved length (for 111 = 3)

good substring when f == length

it is obviously that we need to add some (may be 0 zeroes) leading zeroes for case when f == l, and if for your suffix of substring which has no leading zeroes can be added some leading zeroes to case when f == l you can increment your result.

You can check first numbers

1 = 1 (f = 1, l = 1)

2 = 10 (f=2, l =2)

3 = 11 = 011 (f=2, l=2, need 1 leading zero)

4 = 100 = 0100 (f=4, l=3, need 1 leading zero)

Sorry for my english, hope you understand

Got it, Thanks for explaining this part in more detail, please write more analysis of interesting problem like this in future if you feel like.

how to solve A? hahahahaha

The boundary cases are little convoluted in the problem A, I guess.

See my O(1) solution — https://codeforces.com/contest/1217/submission/60107664

I got TLE

How to solve D?

Colour every back edge as black and the remaining edges as white. Since any cycle cannot contain all back edges, hence we cannot have a cycle containing all edges of the same colour.

If there is no cycle, answer is 1. Otherwise paint an edge $$$(u, v)$$$ white if $$$u < v$$$, else black.

Wow. Just wow.

actually it is WooooooooooooooooooooooooooooooooooooooW !!!

To find if there is a cycle in a directed graph, you can do a DFS marking differently vertex currently treated and vertex you finished treating. If you encounter a vertice still in treatment, it means it's an ancestor in the DFS and you have a cycle.

Incoming and outgoing edges colored differently ensures this. Question: Does Upper bound of 2 also hold for undirected given no multiple edges?

For undirected graphs, the edges of one color form a tree so atmost $$$n-1$$$ edges, but the graph can have $$$\frac{n(n-1)}{2}$$$ edges so it is clear the bound of 2 will not hold.

How to solve D if it is a undirected graph

Anyone who used binary search for A?

I am a bit nervous about my approach..

You can check my solution, where I used binary serch.

I also used binary search

I also solved using binary search.

me too,binary search is more intuitive than pure math equation to me

No need for binary search, see my O(1) solution — https://codeforces.com/contest/1217/submission/60107664

I did realize that O(1) solution exists, but for some reasons I thought that it would have more number of cases, hence more chances of some edge case failing.

Problem A 60157777

could you explain how you approach the problem?

(y+z) — maximum int (int+exp) that can be achieved

(y+z)-x — difference maxInt — minStr that can be achieved

((y+z)-x+2)/2 number of points that we can get from int, and add to str for cases when str <= int (each point from int to str make difference less on two points), if this value < 0 it means str always > int

i think its better to write right+1 (z+1), because there is (exp+1) options to distribute exp points (you can add from 0 to exp points to str) result = (exp+1)-left > how many options for distribution we have (for cases when str > 1)

if result <= 0 there is no options => print 0

not much work just find range [lb,ub] and ub-lb+1 is answer.a,b,c is input. x>=a and y>=b and x>y and x+y=a+b+c always which leads to x ranges from max(a,sum/2+1) to sum-b,now range difference are your total solution.

Anyone has a solution for problem

Ewith10*(3 of segment queries)per query passed ?? Is it intended to pass or not ?I did the same thing got tle

I am very very sad that my solution got accepted now (after the contest) just by using this implementation of segment tree.

So sad, that the implementation of the segment tree played a role in getting accepted for this problem. Was this intended ???? and why ??

my solution with few changes got accepted.. 1) changed long long to int 2) instead of cout/cin fio using scanf/printf 3) optimized ret function

I think you can do 1 query (but complexity remains the same). Just store two minimums for each digit. Constant will be much better than 3 * 10 separate queries.

how to pass test 2 problem C

what is the hack for B ?

i think alot of people checked for case where highest damage is more than number off heads but did not check when that it equal.

thnx

nope i got hacked on that one i checked first max difference <= heads return -1, i got hacked there , test cases were pretty weak.actually i didn't check max damage>=head count.most people solution is failing on that.

hacked 6 people with the same test case, one candidate master :)-

how to solve E?

I think I am not able to tell how fucking annoying it is to not get A right for an hour or more...and then miss C for like 5 minutes.

What was so hard with A, why did I need 10 submissions?

hell yah. it seemed like some easy formula and i didn't even think of binary search.

Yes, it has an easy formula. Somehow it took me 4 hours to figure it out though — https://codeforces.com/contest/1217/submission/60135365

hell yeah missed c due to that.it was pretty easy, but A took time.but realised its simple inequality just find what range it could lie.O(1) solution in just 4 lines of code. link

I hope there is a simple solution for F. My solution is too complicated.

"It is guaranteed that each ordered pair (u, v) appears in the list of edges at most once."

What is mean ordered pair in problem D ?

which means (u, v) is considered different from (v,u).

I think it means that u can have an edge in both directions, but u can't have multiple edges from node u to node v in the same direction.

Thank you! I mistook the meaning of "ordered" as "sorted"..

this code for https://codeforces.com/contest/1217/submission/60130188 Question C is giving correcct output for given test case but it fails on 1st test case on submission. anyone having any idea about this?

In $$$E$$$, what is the best way to know the smallest $$$2$$$ numbers between $$$L$$$ and $$$R$$$ such that they both have a non zero digit at a same position?

I didn't have enough time to submit, but my idea is to build a segment tree for each digit. I planned to fill them in the following fashion: if $$$k$$$-th digit of $$$a_i$$$ is not $$$0$$$, then we put $$$a_i$$$ on place $$$i$$$ in the $$$k$$$-th segment tree, else some huge constant. To get the answer, you could take two minimums on each tree and choose the one with minimum sum.

Should pass in time, pure $$$O(n \cdot logn)$$$, albeit with a considerable constant.

Thank you.

I think the complexity should be $$$O(n*log_{10}(max\,value)+m*log_{10}(max\,value)*log_2(n))$$$. Where the term before $$$+$$$ is for trees builds, and the other is for queries.

for each position, build a segment tree, for each segment, maintain the smallest and second smallest number which both has non-zero digit in that position

For some reason I was thinking during the contest about maintaining something like merge sort tree for every digit position instead of just a normal segment tree through which you can get 2 minimums, and simulate non-existing numbers by large constants. Thanks all.

hack successful test for problem B?

Homi, quando for pra me fuder me dê um beijo antes... Esse educacional aí foi só a massa, satanás tá querendo me ver no cinza, só pode...

I did problem C in O(N*logN*logN). Any better solution?

My solution ~ O(N): https://codeforces.com/contest/1217/submission/60132911 if you want to tutorial, inbox for me.

A good substring starting with '1' can be only '1' or '10' (the ones with length $$$x$$$ > 2 are at least $$$2^x$$$ and thus larger than $$$x$$$) — these can be checked with $$$O(N)$$$.

If a good substring starts with '0', there can be at most one good substring starting at given index (if it is of length $$$x$$$, and equals $$$x$$$, then already the next one will equal at least 2x > $$$x+1$$$). To find these for every given index, you can enumerate possible lengths (length can be from 2 to log2($$$2 \cdot 10^5$$$)), starting from the nearest following '1'. This is $$$O(NlogN)$$$.

Thanks! Did the same afterwards!

This is also what I did, but I assumed there was a simpler solution I was missing. Seems surprisingly challenging for Educational round C.

Problem C Solution :60158214

This is such an obvious hack case for problem B, I wonder why it wasn't in the pretests??

Deliberate traps :{

THank you! Now I can go to sleep)

very bad pretests for B((

indeed a great round at hackforces...

Poor testcases :(

Problem B: What is the output for this input. 1 3 999999911 3 1 11 1000000000 10 9

Jury's answer is 499999951. How ?

Hit em with (3, 1) 499999950 times, finally use the (11, 10...) to finish it. Are you suggesting there's a solution with fewer hits?

What is wrong with my submission for problem A? Link to Submission

Problem A 60157777

Looks like CF managed to automate Problem Setting

The most wrong answer contest I have ever seen hahahahaha.

How to Solve D??

If there is no cycles in our graph we can simply use $$$k=1$$$.

For all other cases we can be done with $$$k=2$$$. Suppose we have edges in form $$$(from, to)$$$, we can paint all edges with $$$from < to$$$ into color $$$1$$$ and all edges with $$$from > to$$$ into color $$$2$$$. If we arrange all vertices of our graph into a sequence, edges that go left are of one color and edges that go right are of another color. Any cycle must start and end in the same vertex, so after making a first step left or right we need to move backwards, but we can only do it with edges of another color.

When will the editorial be out?

Man, I got like 11 WAs on Problem A, and still couldn't solve it. I used this equation :- str + x > int + y && x + y == exp , then finding all possible values of x and y. Can someone provide a clear implementation for this, i think i messed up in calculating the number of solutions.(or are these equations missing something?)

If

exp + strength <= Intelligence, then there's no solution, answer is0.If

exp + Intelligence < strength, then all combinations will work, the answer isexp + 1.If

exp + Intelligence = strength, all combinations except(strength, intelligence + exp)wil work , answer isexp.now for the last case, the minimum

expthat can be added tostrengthwithout disturbing the inequalitystrength > intelligenceis the solution to:Let

xbe the minimumexprequired.(strength + x) — (intelligence + (exp — x)) = 1x = ceil((1 — strength + intelligence + exp) / 2)the answer is

exp — x + 1Thanks mate!

you could solve it pretty obviously.S,I,E is input. now we know that X>=S and Y>=I and X>Y,constraints X+Y=S+I+E=sum => Y=sum-X substituting value we get boundary of X i.e., X belongs [max(S,sum/2+1),sum-b] hence final answer is R-L+1. you could look at my code its just 4 lines. code

https://codeforces.com/contest/1217/submission/60110076

Please Hack this, this is surely not O(N)/O(NlogN) .

Honestly, Educational rounds are not as interesting as they once were.

Why not to say it from your real account, not fake one? Are you afraid of downvotes? Or afraid of us?

P.S.: I'm not arguing about the statement itself, just about people who can't honestly state their opinion.

Problem A was harder than Problem B :(

Similar exercise format as problem B appeared a lot in previous contest.

Please give me a test case on which my solution fails:)

You can easily extract the test case from the online judge. It says that the 73rd number differs, so, resubmit your solution, and print the 73rd query on the console. (Maybe at the start)

try 10 0 4

But in given constraints only third number can zero and first and second are always positive.

Ok then try 10 1 4 Still the same problem

try 100 10 2 Answer is 3 but your output will be 46

When I first saw this 1000 liner code, I thought, is this the end of the universe?

Isn't this code very similar to this code: 60123155? Even the strangest of variable names like ee, uuu, vvv, te, etc., in the main code or just before it are the same.

MikeMirzayanov, awoo can u please check. I believe intentional efforts have been made to avoid plagiarism, like performing

`n = N`

, when there was almost no use of doing it, and also statements like`if(op == 2) op = 2`

The order of some of the statements or expressions has also been intentionally swapped.

No, it's not. If you look more carefully at my previous submission 60108293, you will see that I have marked “template from https://loj.ac/submission/25943” as comment on the first line. Actually this problem is almost exactly the same as this one on LOJ, except some I/O format and the way of forcing online. So I copied a public submission on LOJ and changed it a little bit to pass this one. According to the rules about third-party code, it's ok to do so, and I believe Return.Hao just copied from the same template.

Reporting cheating is good, but I'd like to say you had better check more things out before you make your report.

I am extremely sorry for this. I checked the last submission only as they were the ones that would've contributed to the final results and found no attribution on them, and as I said in my previous comment, a few of the statements only differed in a very suspicious way like the case of doing

`n = N`

as I mentioned above. That's what made my doubts more concrete. That's why I thought it was a cheating case. Sorry once again.Can someone explain me how to solve C please?I dont understand the idea of this problem.

First let's preprocess the array z, such that:

`z[i] = number of zeroes to the left of i before the first 1.`

For instance:

`v: 0 0 0 1 1 0 1`

`z: 0 1 2 3 0 0 1`

What the problem wants is the number of substrings s[l..r] such that the binary number in s[l..r] is equal to its range size

`r - l + 1`

.Now let's say you're currently at index i and

`s[i] == '1'`

. You've already got your first answer, right? because`s[i] == 1`

and the range size is 1. Let's call our current value X and keep constructing new numbers using substrings that start in this index i and end at some index j (s[i..j]).Notice that

`j < min(n, i+20)`

. Because the maximum range size possible is 2*10^5 and you need less than 20 bits to construct that value.Now let's add the next bit (at j'th position) and calculate our new value X, if the next bit is 1,

`X = 2*X + 1`

and if the next bit is 0, then`X = 2*X`

.So for this substring to be good, we need it to have size X. Since we started at i and we're now at j, its size is currently

`j-i+1`

. But remember we have`z[i]`

zeroes to the left! That means that if we could add those zeroes to its left (which doesn't change the value X) and make a substring of size`z[i] + j - i + 1`

such that`z[i] + j - i + 1 >= X`

, then we found a new answer.Hope that was well explained! :D

Thank you very much, this really helped me a lot!

Thanks for explaining in so much detail.

How would you solve D if the edges were undirected?

If graph is undirected this problem is about finding arboricity of given graph. This goes to matroid theory and is actually graphic matroid partitioning problem.

UPD:If someone is interested in practical introduction to this stuff, you may check out this tutorial.UPD: Nevermind :(

Back edges can form a cycle. Example: 5 nodes, dfs tree is 1-2-3-4-5, and there are also edges 1-3, 3-5 and 5-1.

Holy shit, you are right, sorry.

It depends on what are "back edges". For me, if there is next list of edges: (1,2), (2,3), (3,4), (4,5), (1,3), (3,5), (5,1) and dfs tree is 1-2-3-4-5, then (1,3) and (3,5) are forward edges and (5,1) is back edge. So, coloring only (5,1) is ok.

the question was about an undirected graph...

Yes, sorry, I missed the context...

can we hack our own solution, if its already been hacked by somebody, rip rating, didnt realise the stupid test case, 1 4 5 6 6 6 6 6 6 6 6 this was obvious test case, why was it not included in test case list, most of people got hacked on this.

What is intended complexity for E? I did mlogn*10 and it is getting TLE. My implementation of seg tree is pretty not efficient, but why would you give so strict time limit? What is wrong in setting this for 4s?

I've never considered my implementation to be efficient at all. I mean my usual recursive segtree works in 400 ms, so 2 seconds doesn't seem strict. I also think there might have been worse complexity solutions passing if TL was higher.

Hm, im confused now. Is intended solution building 10 seg trees for each digit, and then for each query we need to visit all of them so complexity of one query is 10logn?

Yes, it is. I think the part I didn't take into consideration is that I update all the 9 trees during the same query, so I'm jumping at lot less around the memory, what makes the runtime much lower.

I haven't managed to get within TL with inefficient segment tree implementation. The "efficient and easy" implementation did the trick, but still only 1.5 s...

Delted

I think there's a small error in putting "Final Standings" after the hacking phase, but before system tests.

B pre-test should be made stronger

I copied from As_105 before submission from that handle without As_105's involvement. Please,give ratings to that handle.

Why my solution 60134423 passed pretest in 1954ms. But after system test it gets TLE on pretest8 ?

The runtime is never exact, I guess it can vary quite a bit (maybe ~100ms), even if running on the same test and on the same server.

Now the same code 60158338 passes upto test case 83.

B have 365 cases at system test lol~

Interesting binary search solution of problem A: 60157777

This is not binary search, it is O(1). He calculates min and max values for s, named them left and right.

I got AC on D with following greedy solution:

Take any edge, if it has unicolored path from one of its ends, to other, take another color.

Is it possible to hack it? I guess that it is possible, but there are no such tests in system testing.

Hello Codeforces,

After yesterday's contest(Educational Codeforces Round 72 (Rated for Div. 2)) I have received 3 system messages. For the problems A, B and C. And these are all the problems I have solved during the contest.

Messages say that my solutions are extremely similar to this guy's coderharshit. Actually I have checked and they are identical.

For quite some time now I have been using this github repo to store my solutions.

I always push my code after the contest, actually I usually forget and do it much later.

Yesterday I just didn't think of people would dig google/github to find solutions during the contest and find my code. And I pushed the solutions during the contest. You can see the time of the commit in github.

So this person, apparently a determined soul to find other people's solutions found my solutions and blatantly submitted all of them. Don't know what to think of these people :) .

In the system messages, I was asked to write a comment here if I have evidence that I have published the code publicly and they accessed it, so writing this now.

fyi, MikeMirzayanov

Best, Burak

why do you use public repo during contests?

it is explained in the message

Sorry, misunderstanding! :) Good luck, hope Mike helps you

thanks

bad luck for you.

It is entirely your responsibility to ensure that the code you submit stays private during the contest.

"I just didn't think of people would dig google" is not a proper justification.

There were plenty of cases before of people coding on ideone, forgetting to set it on private, and getting penalized.

yeah can't deny that :), anyway these things happen. I have participated in 44 contests and it is the first time

I want to say... What is the pretest of problem B made of?

It has $$$364$$$ tests. Is there an official problem with more number of testcases?

I think most of tests added as success hacking attempts (unique I think). You can check, I think most of test have similiar idea.

Many random problems have lots of testcases

Still waiting for the Editorial :||||||

boy, this contest was really tough for me, I was completely discouraged by even first task. however, it's so exciting always (2 times for me heh)

I think it must have been tough on almost everybody. I only solved one problem (as against my normal of 3 or 4) yet maintained my rating of 1539 (0 change in rating).

Please provide the editorial for this contest.

Any ideas for WA on test case 5 for E?

can someone tell me why I am getting rte on test 69 on problem B?