Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

By pikmike, 10 months ago, translation, ,

Hello Codeforces!

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 Ne0n25 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!

APPLY HERE→

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
1432 successful hacks and 1595 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A xyz100 0:02
B Chereshnya_ 0:06
C Florin29 0:06
D IgorI 0:08
E Aria 0:30

• +131

 » 10 months ago, # | ← Rev. 3 →   0 Thanks for round! :)
 » 10 months ago, # | ← Rev. 2 →   -78 :(( a funny picture. but -64 downvoted. :(( sorry i deleted it
•  » » 10 months ago, # ^ |   -26 Two funny images, why so heavily downvoted?
•  » » » 10 months ago, # ^ |   -28 i don't know :(( Why??? i tried with funny comments. but -44 voted? :D what the f* ?
•  » » » 10 months ago, # ^ | ← Rev. 2 →   -21 i think that i will not write a another comment :(( So sad..
•  » » » 10 months ago, # ^ |   +22 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
•  » » » » 10 months ago, # ^ |   +3 oke <3
 » 10 months ago, # |   +21 funny picture always got upvote
•  » » 10 months ago, # ^ |   -15 it seems you must get upvote then
 » 10 months ago, # |   +7 Would anyone be interested in a round written solely by tourist?
•  » » 10 months ago, # ^ |   -7 I have never tried it so I am looking forward to it
•  » » 10 months ago, # ^ |   +87 Score distribution: 5000 — 5000 — 5000 — 5000 — 5000...
•  » » 10 months ago, # ^ |   +19 As far as I know, there already was one (I think it was one of the Hello / Good Bye rounds).
•  » » 10 months ago, # ^ |   +7 tourist was a writer of Hello 2018!
•  » » 10 months ago, # ^ |   0 Here is all of tourist's problemsetting: (https://codeforces.com/contests/writer/tourist). Some rounds are written solely or almost solely by him.
 » 10 months ago, # |   -21 Two rounds in two days, the later one must be a good round...
 » 10 months ago, # |   -22 Seems like Codeforces wants me to give this contest as a rated one
 » 10 months ago, # |   +4 Hope this round will be like last educational
 » 10 months ago, # | ← Rev. 2 →   -24 [deleted]
 » 10 months ago, # |   0 I want to know if I will lost some rating if i dont have time to join this round.....
•  » » 10 months ago, # ^ |   +3 Certainly not. You will not be considered as an official participant if you don't even make a single attempt.
 » 10 months ago, # |   0 What will be the difficulty of the problems? I have just started with cp.
•  » » 10 months ago, # ^ |   +9 yes
 » 10 months ago, # |   -17 Hopefully I can gain more rating!
 » 10 months ago, # | ← Rev. 2 →   +5 Wanna become blue today...
•  » » 10 months ago, # ^ |   0 Yeah, sure, buddy. :))
 » 10 months ago, # |   -73 I think its not so good contest
 » 10 months ago, # |   0 when can we upsolve the problems?
•  » » 10 months ago, # ^ |   +6 You can already start upsolving it :)
 » 10 months ago, # |   +27 For E my time complexity was O(q*digits*log(n)) which got TL-5. How to do it better?
•  » » 10 months ago, # ^ |   0 Use int instead of long long
•  » » 10 months ago, # ^ | ← Rev. 3 →   0 My submission 60129750 got 1497 ms (complexity is the same)
•  » » 10 months ago, # ^ | ← Rev. 6 →   -10 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
•  » » 10 months ago, # ^ |   +3 I think it's because of digit function in your code. I think it's $O(q*digits^2*log(n))$ in worst case.
•  » » » 10 months ago, # ^ |   0 Thanks!
•  » » 10 months ago, # ^ |   +3 I also had the same complexity https://codeforces.com/contest/1217/submission/60133014 got tle at tc5.. can anybody tell why?
•  » » » 10 months ago, # ^ |   0 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.
•  » » » » 10 months ago, # ^ |   0 i optimized it but still the same.. the time limit shouldn't be this strict
•  » » » » » 10 months ago, # ^ | ← Rev. 3 →   +5 You should pick one. scanf,printf or cin/cout with fastio.
•  » » » » » » 10 months ago, # ^ |   0 Oh F.. I didn't see that. Thanks a lot
•  » » 10 months ago, # ^ |   +3 I got 1.996s on pretests and didn't realize lol.
 » 10 months ago, # |   0 How to solve problem F ?
•  » » 10 months ago, # ^ |   +75 $last$ can only be $0$ or $1$, so we can make $2m$ operations and do them offline.
•  » » » 10 months ago, # ^ |   +13 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.
•  » » » » 10 months ago, # ^ | ← Rev. 4 →   +3 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).
•  » » » 10 months ago, # ^ |   0 But how? I don't really understand.
•  » » » » 10 months ago, # ^ |   +18 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.
•  » » » 10 months ago, # ^ |   0 can you please explain a little bit more?
•  » » » 10 months ago, # ^ |   0 I don't understand. Since $last$ could be 0 or 1 on each query, doesn't that mean that in total there are $2^m$ possible chains of operations?
•  » » » » 10 months ago, # ^ | ← Rev. 2 →   0 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 inclusion might change and 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 edge might change again.
•  » » 10 months ago, # ^ |   0 u can also solve with using dynamic connectivity
•  » » » 10 months ago, # ^ |   0 There's no such thing as online dynamic general graph connectivity as far as I know :<
•  » » » » 10 months ago, # ^ |   -10 Fuck, i forgot its online queries xd
•  » » » » 10 months ago, # ^ |   +14 There is one. It involves some really heavy magic with Link-Cut Trees.Some accepted submissions use that approach.
•  » » » » » 10 months ago, # ^ |   +3 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.
•  » » » » » » 10 months ago, # ^ |   +6 Even as a red I am mindblown by it too.
•  » » » » » 10 months ago, # ^ |   +28 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.
 » 10 months ago, # |   0 getting WA on test 2 in B, whats is the logic or tell me something wrong in my solution please.link of my solution
•  » » 10 months ago, # ^ |   0 if all d < h and has no d >= x — result -1next chose a=max(di-hi) and b=maxd, last step max(a,b), all steps before last (b)
•  » » » 10 months ago, # ^ |   0 haha lol, I comment d>= x here. but in my contest submission write d>x)
•  » » 10 months ago, # ^ | ← Rev. 2 →   +5 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.
 » 10 months ago, # |   0 How To Solve C..?
•  » » 10 months ago, # ^ |   0 How to solve C with out gettin TLE on test 12 ??????????
•  » » 10 months ago, # ^ |   +1 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.
•  » » » 10 months ago, # ^ | ← Rev. 2 →   0 i still don't understand about this one i is at most (i + 20), could you explain why the last good substring starting at i is at most (i + 20) ?
•  » » » » 10 months ago, # ^ |   +1 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.
•  » » 10 months ago, # ^ | ← Rev. 2 →   +4 my solution:precalc zeroes-array: how many zeroes before ith elementnext 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]01number of zeroes before before = 3, f=1 and 3 enough to add to result (1-1<=3)next step go to 000[10]1in 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++
•  » » » 10 months ago, # ^ |   0 Thanks a lot! Nice solution, really easy to code.
•  » » » » 10 months ago, # ^ |   0 Your implementation and description in comments more clearly, thanks!
•  » » » 10 months ago, # ^ |   +1 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.
•  » » » 10 months ago, # ^ |   0 How do you get the formula if (f — length <= number of zeroes) then result++ I mean logic behind it
•  » » » » 10 months ago, # ^ |   0 f — function result that we needed to achieve (for example for 111 = 7)length — already achieved length (for 111 = 3)good substring when f == lengthit 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
•  » » » » » 10 months ago, # ^ |   0 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.
 » 10 months ago, # |   +5 how to solve A? hahahahaha
•  » » 10 months ago, # ^ |   +6 The boundary cases are little convoluted in the problem A, I guess.
•  » » 10 months ago, # ^ |   0 See my O(1) solution — https://codeforces.com/contest/1217/submission/60107664
•  » » 10 months ago, # ^ | ← Rev. 3 →   -8 I got TLE
 » 10 months ago, # |   +5 How to solve D?
•  » » 10 months ago, # ^ | ← Rev. 2 →   +18 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.
•  » » 10 months ago, # ^ |   +136 If there is no cycle, answer is 1. Otherwise paint an edge $(u, v)$ white if $u < v$, else black.
•  » » » 10 months ago, # ^ |   +51 Wow. Just wow.
•  » » » » 10 months ago, # ^ |   +12 actually it is WooooooooooooooooooooooooooooooooooooooW !!!
•  » » 10 months ago, # ^ | ← Rev. 2 →   +20 If there is no cycle the answer is 1 Else you can use one color for the edges u->v where u < v and another for the edges u->v where u > v so the answer is 2 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.
•  » » 10 months ago, # ^ | ← Rev. 4 →   0 Incoming and outgoing edges colored differently ensures this. Question: Does Upper bound of 2 also hold for undirected given no multiple edges?
•  » » » 10 months ago, # ^ |   +5 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.
•  » » 10 months ago, # ^ |   +6 How to solve D if it is a undirected graph
 » 10 months ago, # |   +33 Anyone who used binary search for A?I am a bit nervous about my approach..
•  » » 10 months ago, # ^ | ← Rev. 2 →   +6 You can check my solution, where I used binary serch.
•  » » 10 months ago, # ^ |   +6 I also used binary search
•  » » 10 months ago, # ^ |   +7 I also solved using binary search.
•  » » 10 months ago, # ^ |   +2 me too,binary search is more intuitive than pure math equation to me
•  » » 10 months ago, # ^ |   0 No need for binary search, see my O(1) solution — https://codeforces.com/contest/1217/submission/60107664
•  » » » 10 months ago, # ^ |   +4 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.
•  » » » 10 months ago, # ^ | ← Rev. 2 →   -8 Problem A 60157777
•  » » » » 10 months ago, # ^ |   0 could you explain how you approach the problem?
•  » » » » » 10 months ago, # ^ |   0 (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 > inti 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
•  » » 10 months ago, # ^ | ← Rev. 3 →   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.
 » 10 months ago, # |   +11 Anyone has a solution for problem E with 10*(3 of segment queries) per query passed ?? Is it intended to pass or not ?
•  » » 10 months ago, # ^ |   +8 I did the same thing got tle
•  » » 10 months ago, # ^ |   +8 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 ??
•  » » » 10 months ago, # ^ |   0 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
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 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.
 » 10 months ago, # |   0 how to pass test 2 problem C
 » 10 months ago, # |   +29 what is the hack for B ?
•  » » 10 months ago, # ^ |   +5 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.
•  » » » 10 months ago, # ^ |   0 thnx
•  » » » 10 months ago, # ^ |   0 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.
•  » » 10 months ago, # ^ | ← Rev. 2 →   +4 1 1 1 1 1 hacked 6 people with the same test case, one candidate master :)-
 » 10 months ago, # |   0 how to solve E?
 » 10 months ago, # |   +6 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?
•  » » 10 months ago, # ^ |   -8 hell yah. it seemed like some easy formula and i didn't even think of binary search.
•  » » » 10 months ago, # ^ |   0 Yes, it has an easy formula. Somehow it took me 4 hours to figure it out though — https://codeforces.com/contest/1217/submission/60135365
•  » » 10 months ago, # ^ |   0 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
 » 10 months ago, # |   +3 I hope there is a simple solution for F. My solution is too complicated.
 » 10 months ago, # |   0 "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 ?
•  » » 10 months ago, # ^ |   +3 which means (u, v) is considered different from (v,u).
•  » » 10 months ago, # ^ |   0 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.
•  » » 10 months ago, # ^ |   +3 Thank you! I mistook the meaning of "ordered" as "sorted"..
 » 10 months ago, # | ← Rev. 3 →   0 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?
 » 10 months ago, # |   +10 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?
•  » » 10 months ago, # ^ | ← Rev. 2 →   +8 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.
•  » » » 10 months ago, # ^ |   0 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.
•  » » 10 months ago, # ^ |   0 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
•  » » 10 months ago, # ^ |   0 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.
 » 10 months ago, # |   +4 hack successful test for problem B?
 » 10 months ago, # |   0 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...
 » 10 months ago, # |   +3 I did problem C in O(N*logN*logN). Any better solution?
•  » » 10 months ago, # ^ |   -14 My solution ~ O(N): https://codeforces.com/contest/1217/submission/60132911 if you want to tutorial, inbox for me.
•  » » 10 months ago, # ^ |   +13 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)$.
•  » » » 10 months ago, # ^ |   +5 Thanks! Did the same afterwards!
•  » » » 10 months ago, # ^ | ← Rev. 2 →   0 This is also what I did, but I assumed there was a simpler solution I was missing. Seems surprisingly challenging for Educational round C.
•  » » 10 months ago, # ^ |   -8 Problem C Solution :60158214
 » 10 months ago, # | ← Rev. 2 →   +10 1 1 1 1 1 This is such an obvious hack case for problem B, I wonder why it wasn't in the pretests??
•  » » 10 months ago, # ^ |   +11 Deliberate traps :{
•  » » 10 months ago, # ^ |   0 THank you! Now I can go to sleep)
 » 10 months ago, # |   +38 very bad pretests for B((
 » 10 months ago, # |   +17 indeed a great round at hackforces...
 » 10 months ago, # |   0 Poor testcases :(
 » 10 months ago, # |   0 Problem B: What is the output for this input. 1 3 999999911 3 1 11 1000000000 10 9Jury's answer is 499999951. How ?
•  » » 10 months ago, # ^ |   0 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?
 » 10 months ago, # |   0 What is wrong with my submission for problem A? Link to Submission
•  » » 10 months ago, # ^ | ← Rev. 3 →   -11 Problem A 60157777
 » 10 months ago, # |   +41 Looks like CF managed to automate Problem Setting
 » 10 months ago, # |   +24 The most wrong answer contest I have ever seen hahahahaha.
 » 10 months ago, # |   0 How to Solve D??
•  » » 10 months ago, # ^ | ← Rev. 2 →   +30 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.
 » 10 months ago, # |   0 When will the editorial be out?
 » 10 months ago, # | ← Rev. 2 →   0 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?)
•  » » 10 months ago, # ^ | ← Rev. 7 →   +6 If exp + strength <= Intelligence , then there's no solution, answer is 0. If exp + Intelligence < strength , then all combinations will work, the answer is exp + 1.If exp + Intelligence = strength , all combinations except (strength, intelligence + exp) wil work , answer is exp.now for the last case, the minimum exp that can be added to strength without disturbing the inequality strength > intelligence is the solution to:Let x be the minimum exp required.(strength + x) — (intelligence + (exp — x)) = 1x = ceil((1 — strength + intelligence + exp) / 2)the answer is exp — x + 1
•  » » » 10 months ago, # ^ |   0 Thanks mate!
•  » » » 10 months ago, # ^ |   0 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
 » 10 months ago, # |   0 https://codeforces.com/contest/1217/submission/60110076Please Hack this, this is surely not O(N)/O(NlogN) .
 » 10 months ago, # |   -24 Honestly, Educational rounds are not as interesting as they once were.
•  » » 10 months ago, # ^ | ← Rev. 3 →   +52 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.
 » 10 months ago, # |   +3 Problem A was harder than Problem B :(
•  » » 10 months ago, # ^ | ← Rev. 2 →   -8 Similar exercise format as problem B appeared a lot in previous contest.
 » 10 months ago, # |   0 Please give me a test case on which my solution fails:)
•  » » 10 months ago, # ^ |   +1 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)
•  » » 10 months ago, # ^ |   0 try 10 0 4
•  » » » 10 months ago, # ^ |   0 But in given constraints only third number can zero and first and second are always positive.
•  » » » » 10 months ago, # ^ |   0 Ok then try 10 1 4 Still the same problem
•  » » 10 months ago, # ^ |   0 try 100 10 2 Answer is 3 but your output will be 46
 » 10 months ago, # |   +8 When I first saw this 1000 liner code, I thought, is this the end of the universe?
•  » » 10 months ago, # ^ |   +12 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.
•  » » » 10 months ago, # ^ |   +13 MikeMirzayanov, PikMike 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
•  » » » » 10 months ago, # ^ |   0 The order of some of the statements or expressions has also been intentionally swapped.
•  » » » » » 10 months ago, # ^ |   +40 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.
•  » » » » » » 10 months ago, # ^ |   +3 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.
 » 10 months ago, # |   0 Can someone explain me how to solve C please?I dont understand the idea of this problem.
•  » » 10 months ago, # ^ | ← Rev. 3 →   +35 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 1z: 0 1 2 3 0 0 1What 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
•  » » » 10 months ago, # ^ | ← Rev. 2 →   0 Thank you very much, this really helped me a lot!
•  » » » 10 months ago, # ^ |   0 Thanks for explaining in so much detail.
 » 10 months ago, # |   +11 How would you solve D if the edges were undirected?
•  » » 10 months ago, # ^ | ← Rev. 2 →   +5 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.
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 UPD: Nevermind :(
•  » » » 10 months ago, # ^ |   +27 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.
•  » » » » 10 months ago, # ^ |   0 Holy shit, you are right, sorry.
•  » » » » 10 months ago, # ^ |   -8 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.
•  » » » » » 10 months ago, # ^ |   +19 the question was about an undirected graph...
•  » » » » » » 10 months ago, # ^ |   0 Yes, sorry, I missed the context...
 » 10 months ago, # |   0 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.
 » 10 months ago, # |   +24 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?
•  » » 10 months ago, # ^ | ← Rev. 2 →   +7 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.
•  » » » 10 months ago, # ^ |   0 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?
•  » » » » 10 months ago, # ^ |   0 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.
•  » » » 10 months ago, # ^ |   0 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...
 » 10 months ago, # | ← Rev. 2 →   -8 Delted
 » 10 months ago, # |   +9 I think there's a small error in putting "Final Standings" after the hacking phase, but before system tests.
 » 10 months ago, # |   0 B pre-test should be made stronger
 » 10 months ago, # |   -17 I copied from As_105 before submission from that handle without As_105's involvement. Please,give ratings to that handle.
 » 10 months ago, # |   +5 Why my solution 60134423 passed pretest in 1954ms. But after system test it gets TLE on pretest8 ?
•  » » 10 months ago, # ^ |   +6 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.
•  » » » 10 months ago, # ^ |   0 Now the same code 60158338 passes upto test case 83.
 » 10 months ago, # | ← Rev. 2 →   +3 B have 365 cases at system test lol~
 » 10 months ago, # |   0 Interesting binary search solution of problem A: 60157777
•  » » 10 months ago, # ^ |   +8 This is not binary search, it is O(1). He calculates min and max values for s, named them left and right.
 » 10 months ago, # |   +8 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.
 » 10 months ago, # | ← Rev. 4 →   +10 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
•  » » 10 months ago, # ^ |   +8 why do you use public repo during contests?
•  » » » 10 months ago, # ^ | ← Rev. 2 →   0 it is explained in the message
•  » » » » 10 months ago, # ^ |   0 Sorry, misunderstanding! :) Good luck, hope Mike helps you
•  » » » » » 10 months ago, # ^ |   0 thanks
•  » » 10 months ago, # ^ |   0 bad luck for you.
•  » » 10 months ago, # ^ |   +13 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.
•  » » » 10 months ago, # ^ |   0 yeah can't deny that :), anyway these things happen. I have participated in 44 contests and it is the first time
 » 10 months ago, # |   0 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?
•  » » 10 months ago, # ^ |   +10 I think most of tests added as success hacking attempts (unique I think). You can check, I think most of test have similiar idea.
•  » » 10 months ago, # ^ |   0 Many random problems have lots of testcases
 » 10 months ago, # |   0 Still waiting for the Editorial :||||||
 » 10 months ago, # |   +1 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)
•  » » 10 months ago, # ^ |   0 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).
 » 10 months ago, # |   0 Please provide the editorial for this contest.
 » 10 months ago, # | ← Rev. 2 →   0 Any ideas for WA on test case 5 for E?
 » 10 months ago, # |   0 can someone tell me why I am getting rte on test 69 on problem B?