Привет, Codeforces!
В 05.09.2019 17:35 (Московское время) состоится Educational Codeforces Round 72 (рейтинговый для Див. 2).
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 6 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Роман Roms Глазов, Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
Удачи в раунде! Успешных решений!
Так же от наших друзей и партнёров из Harbour.Space есть сообщение для вас:
Привет, Codeforces,
Университет Harbour.Space совместно с UTCC (Бангкок, Таиланд) предлагает уникальные стипендии для обучения по магистерским программам.
Наша цель устранить какие-либо финансовые барьеры для талантливых студентов: стипендии покрывают 100% оплаты за обучение, а также расходы на проживание, и, кроме того, они предоставляют студенту ценный опыт как обучения, так и работы в Harbour.Space University.
Мы ищем людей, которые собираются изменить мир. Если вы или кто-то из ваших знакомых интересуется технологиями, предпринимательством или дизайном, то мы будем рады получить вашу заявку!
Поздравляем победителей:
| Место | Участник | Задач решено | Штраф |
|---|---|---|---|
| 1 | Tropical_maid | 6 | 212 |
| 2 | Return.Hao | 6 | 246 |
| 3 | xyz100 | 6 | 272 |
| 4 | YangDavid | 6 | 280 |
| 5 | Lawali | 6 | 300 |
Поздравляем лучших взломщиков:
| Место | Участник | Число взломов |
|---|---|---|
| 1 | VegetableP | 116:-14 |
| 2 | Princ_iple | 49:-1 |
| 3 | racsosabe | 42:-1 |
| 4 | shurongwang | 36 |
| 5 | Megatron_99 | 29:-1 |
И, наконец, поздравляем людей, отправивших первое полное решение по задаче:
| Задача | Участник | Штраф |
|---|---|---|
| A | xyz100 | 0:02 |
| B | mutant | 0:06 |
| C | Laiu | 0:06 |
| D | IgorI | 0:08 |
| E | mzen | 0:30 |
| F | Hasan0540 | 0:51 |
UPD: Разбор опубликован
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.me/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. :))
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.me/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 or cin/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 each query, 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 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.
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 i is at most (i + 20), could you explain why the last good substring starting at 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
how to solve A? hahahahaha
The boundary cases are little convoluted in the problem A, I guess.
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 \lt 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.me/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 E with 10*(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.
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.me/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"..
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?
I did problem C in O(N*logN*logN). Any better solution?
My solution ~ O(N): https://codeforces.me/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.
Самый сложный A за последние раунды.
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?
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 \lt to$$$ into color $$$1$$$ and all edges with $$$from \gt 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.
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 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)) = 1
x = ceil((1 — strength + intelligence + exp) / 2)
the answer is exp — x + 1
Thanks 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.me/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 :(
Очень слабые претесты на задачу В. Неужели нельзя было посильнее сделать?
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 likeif(op == 2) op = 2The 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 = Nas 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 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? becauses[i] == 1and 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 + 1and if the next bit is 0, thenX = 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 havez[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 sizez[i] + j - i + 1such thatz[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!
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...
Лол, 1200 взломов по B.
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
My solution for problem E 60134423 passed pretest 8 in 1954ms. But it shows time limit exceeded at testcase 8 after system testing. Can anyone tell me why this happen?
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 (рейтинговый для Див. 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).
Any ideas for WA on test case 5 for E?