Автор Vovuh, история, 9 месяцев назад, ,

Привет, Codeforces!

13 января в 16:05 по Москве начнётся Educational Codeforces Round 36.

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Этот раунд (уже по традиции) будет рейтинговым для Div. 2. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. После окончания раунда будет период времени длительностью в один день, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной готовили Михаил PikMike Пикляев, Иван BledDest Андросов и Сергей sslotin Слотин.

Удачи в раунде! Успешных решений!

У меня также есть сообщение от наших партнёров, Harbour.Space University:

As we get ready to dive into the second week of the year, we want to update you all on the upcoming Hello India x Russia Programming Bootcamp! So far 25 teams have registered, with more signing up daily.

As a reminder, the boot camp will take place from March 22nd to March 30th, 2018, at the Amrita School of Engineering campus, India. The Coordinator of the Programming Committee, and head coach will be two time ACM-ICPC world vice-champion Gleb GlebsHP Evstropov.

For those of you who need financial support for the boot camp, please fill up the register form, then we will contact you and prepare an official sponsorship request letter for you to present to your University, University’s IT partners or your potential employer.

Поздравляем победителей:

Rank Competitor Problems Solved Penalty
2 uwi 7 275
3 KrK 7 277
4 LHiC 7 284
5 latte0119 7 331

Поздравляем лучших взломщиков:

Rank Competitor Hack Count
1 halyavin 725:-45
2 zscoder 34:-10
3 M3hran 28:-3
4 OlegZubkov 28:-3
5 neelbhallabos 21

Было сделано 2023 успешных и 1300 неудачных взломов.

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

Problem Competitor Penalty
A Dalgerok 0:00
B Rafbill 0:03
C yashar_sb_sb 0:11
D eddy1021 0:25
E bmerry 0:11
F SmsS4 0:15
G MrDindows 0:19

UPD Разбор

•
• +298
•

 » 9 месяцев назад, # |   0 This round will be (traditionally now) rated for Div. 2Does this Mean that all "Educational Rounds" will be rated for Div.2?
•  » » 9 месяцев назад, # ^ |   +2 It is unknown now but we hope so =)
•  » » 9 месяцев назад, # ^ |   -6 Last 4 rounds are so, so maybe!
•  » » 9 месяцев назад, # ^ |   +9 From now "Educational Rounds" will be rated for Div.2But maybe some rounds will be unrated for Div.2
•  » » 9 месяцев назад, # ^ |   0 It is will be rating
 » 9 месяцев назад, # |   -55 i wish everyone ratings equal to my contribution :)
•  » » 9 месяцев назад, # ^ |   0 Me contribution is well er. u not know da wae.
•  » » » 9 месяцев назад, # ^ |   0 No. Stop it. Get some help.
•  » » 9 месяцев назад, # ^ |   +9 I dont wish ratings like my contribution :-) Good luck and peace!
•  » » » 9 месяцев назад, # ^ |   -12 luck and peace are for the weak
•  » » » » 9 месяцев назад, # ^ |   +9 maybe, you are right. However, I can't see that you are red, therefore you also need luck and peace)))
•  » » » » » 9 месяцев назад, # ^ |   -48 shut up green noob im blue im superior
•  » » » » » » 9 месяцев назад, # ^ |   +52 racism
•  » » » » » » 9 месяцев назад, # ^ |   0 its not about what color do u belong, and who is superior to whom ,its about how much you r trying ,and he is trying his best and has given more contests than u.
•  » » » » » » » 9 месяцев назад, # ^ |   -16 this is smurf account fag , i have +20 contests on other account
•  » » » » » » » » 9 месяцев назад, # ^ |   +4 So what...I don't know what you are proud of.Respect others effort plz
•  » » » » » » » » » 9 месяцев назад, # ^ |   -8 why would i need to respect other effort, ching chong ? Im not their teacher or something
 » 9 месяцев назад, # |   0 Does this educational focus on classical problems like a good portion of the previous ones, or should I be expecting a regular round?
 » 9 месяцев назад, # |   +15
•  » » 9 месяцев назад, # ^ |   -65 69 hahahahahaha get it its 69!!!!!!!!!! HAHAHAHAHAHAHA :))))))))))))))))))))))))))))))))))))))))))))))))))))))) 6 9 6 9 6 9 soooo funynnnyyyy :)))))))))))))))))))))))))))))))))))))))))
•  » » 9 месяцев назад, # ^ |   +6 Timelimit for all questions is very tight!
 » 9 месяцев назад, # |   -15 "Thanks Mike" is compulsory!!!!!!!
 » 9 месяцев назад, # | ← Rev. 2 →   -20 where are polygons???
•  » » 9 месяцев назад, # ^ |   +4
•  » » 9 месяцев назад, # ^ |   0
 » 9 месяцев назад, # |   0 почему индийцы и китайцы переводят этот комментарий, я не знаю
•  » » 9 месяцев назад, # ^ |   +1 не только они
 » 9 месяцев назад, # |   0 Good luck to everyone :)
 » 9 месяцев назад, # |   +1 GL & HF!
 » 9 месяцев назад, # |   0 pikmike's and vovuh's rating graphs are very inspiring.
 » 9 месяцев назад, # |   +3 Напомните, пожалуйста: тест, взломавший некоторое решение, будет ли пробоваться на всех остальных решениях системой после окончания фазы взломов?
•  » » 9 месяцев назад, # ^ |   +3 На образовательных раундах мы почти всегда добавляем все тесты из взломов, которые кого-то взломали. Исключение — если таких тестов совсем уж много, но это случается крайне редко.
 » 9 месяцев назад, # | ← Rev. 2 →   0 Will you (as a prize) tach the 1st place's spagett? or let them tach yours
 » 9 месяцев назад, # |   +27 since when GlebsHP is two time world champion?
 » 9 месяцев назад, # |   0 Iasy round. I wil up my rating. Gud lak to me!
 » 9 месяцев назад, # |   0 shit, solved D but B and C too hard for me(((
•  » » 9 месяцев назад, # ^ |   0 Well done, I solved B and C but couldn't solve D — need to study more graphs
•  » » 9 месяцев назад, # ^ |   +3 How did you solve C?
•  » » » 9 месяцев назад, # ^ |   0 Just use greedy method to construct your ans.
 » 9 месяцев назад, # |   +26 Timelimit for E is very tight!
 » 9 месяцев назад, # | ← Rev. 3 →   +1 After the contest ends:Where is that test #6?UPD: It is Educational Round so how can we know test #6?
•  » » 9 месяцев назад, # ^ | ← Rev. 2 →   0 Consider the input 543 433. (If you mean the task C. I imagine a correct solution uses backtracking)
•  » » 9 месяцев назад, # ^ |   0 For C? Try this : 201 200
 » 9 месяцев назад, # |   0 Is the intended solution for E a Segment Tree? I am getting Runtime Error on test 18 with mine (Although I'm very close to the time limit too sooo).
•  » » 9 месяцев назад, # ^ |   0 Implicit segment tree can do work. But I couldn't find my bug.
•  » » » 9 месяцев назад, # ^ |   0 Is implicit segment tree a segment tree when you create nodes only when you need them? If so, I did that but couldn't fit it in.
•  » » » » 9 месяцев назад, # ^ |   0 use struct and pointer
•  » » » » » 9 месяцев назад, # ^ |   0 if you are creating new nodes in heap try to create it in stack instead Node d[15000009]; int curr; // ID of last node I created if (root->left == NULL) ++curr, root->left = d+curr; // try this if (root->left == NULL) root->left = new Node();// instead of this my first solution I created new nodes in heap and got TLE in test 18, and then after some optimization got MLE in test 32 :D now after creating new nodes in stack instead it finally gives AC.
•  » » 9 месяцев назад, # ^ |   0 my seg tree O(Q * log2(N)) solution got TLE, time limit is very tight
•  » » » 9 месяцев назад, # ^ |   0 Where do you get the second log2 from? Is it an approximation for your lazy?
•  » » » » 9 месяцев назад, # ^ |   0 you can see it, 34143231
•  » » » 9 месяцев назад, # ^ |   0 I did the pragma thing mentioned in some other comment and my tle solution passed!
•  » » 9 месяцев назад, # ^ |   0 I did segtree with coordinate compressing, got TL16
•  » » 9 месяцев назад, # ^ |   +14 I solved it using just a set (of segments), each time, I erase the segments which are totally inside the new one and cut the ones that intersect and are not totally inside (at most two).
•  » » » 9 месяцев назад, # ^ |   0 what's the complexity? Especially the part of " I erase the segments which are totally inside the new one" ?
•  » » » » 9 месяцев назад, # ^ |   0 Each query increases the number of segments at most by two, so there are only O(Q) segments. Since each segment can get erased at most once, the total complexity of "erase the segments which are totally inside the new one" over all the queries is O(Q log(Q)), final complexity is also O(Q log(Q)). I'm a bit dizzy today so I might be doing something wrong.
•  » » » » » 9 месяцев назад, # ^ |   0 Nice, thanks.
•  » » » 9 месяцев назад, # ^ |   0 if you don't mind can you please explain how to implement this?
•  » » » » 9 месяцев назад, # ^ |   +1 http://codeforces.com/contest/915/submission/34146439take a look at my submission, shouldn't be hard to understand. It's easy because at any point there are no overlapping segments
 » 9 месяцев назад, # |   0 Idea for D ?
•  » » 9 месяцев назад, # ^ | ← Rev. 3 →   +9 Is mine correct, please someone check:Find any cycle. For each edges in this cycle, delete it and check is condition is true or not.(I didn't write it during contest so I'm not sure it works or not)
•  » » » 9 месяцев назад, # ^ |   0 I tried this and got TLE multiple times
•  » » » » 9 месяцев назад, # ^ |   0 Seems TL is tight, just add pragmas and optimizations to your code and send it again. I'm not sure either.
•  » » » » » 9 месяцев назад, # ^ |   0 Can you show me your pragmas?
•  » » » » » » 9 месяцев назад, # ^ | ← Rev. 2 →   +1 #pragma comment(linker, "/stack:200000000") #pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #define _CRT_SECURE_NO_WARNINGS 
•  » » » » » » » 9 месяцев назад, # ^ |   0 thx
•  » » » » » » » 9 месяцев назад, # ^ | ← Rev. 2 →   +6 For those who know, this might sound dumb so pls bear with it -: What are pragmas? What do above #pragmas statements do?
•  » » » » » » » » 9 месяцев назад, # ^ |   +5 I don't know too
•  » » » » » » » » 9 месяцев назад, # ^ |   +9 xD I don't know most of them also :PBut this guy turns on "Ofast" optimization which makes your loops faster and does some of them without traversing entire loop like: for(long long i = 1; i <= (long long)1e15; i++) res++;. Try this with this line and it will find answer immediately. #pragma GCC optimize("Ofast") 
•  » » » » » » » » 6 недель назад, # ^ | ← Rev. 2 →   0 I don't meaning of each and every pragmas but I've prepared a snippet of it. For more details GCC pragmas docmentation
•  » » » » 9 месяцев назад, # ^ |   0 I sent your code with pragmas and it got TLE again, TL complexity of algorithm seems correct, but.. I don't know
•  » » » » 9 месяцев назад, # ^ | ← Rev. 2 →   0 I tried same idea and passed, but I forgot to erase elements from stack (So I got hacked :'( ). But it should work. Code
•  » » » 9 месяцев назад, # ^ |   0 Won't the complexity be O(m2) then ?
•  » » » » 9 месяцев назад, # ^ |   +3 No, there are N edges in one cycle at most.
•  » » » » » 9 месяцев назад, # ^ |   +3 Ouch !!! Should have seen this. Thanx.
•  » » » » 9 месяцев назад, # ^ |   +4 No, because maximal cycle have n edges
•  » » 9 месяцев назад, # ^ |   +1 I think we'd have to find the strongly connected components and check if there is more than 1 component with >1 vertices in it.
•  » » » 9 месяцев назад, # ^ |   0 There can be only one scc but a clique.
•  » » » 9 месяцев назад, # ^ |   0 This doesn't work with sample tests.
•  » » » » 9 месяцев назад, # ^ |   0 Yes another check needs to be done within the scc. Maybe you can check if all the vertices inside the scc have only a single common edge or not.
•  » » » 9 месяцев назад, # ^ | ← Rev. 2 →   0 I did that. There are two cases: 1) if there is a pair a->b and b->a then we need to remove one of them, so just check both cases. Otherwise 2) there must be just one SCC with >1 vertices, and if we consider a graph with just the SCC nodes, each node must have exactly one in-edge and one out-edge (so it's just a big cycle). This passed pretests but I'm not sure if it's correct. Also, it works in O(N+M) :D
•  » » » » 9 месяцев назад, # ^ |   0 You can have one cycle with one additional edge but still you can remove cycle with only one edge.
•  » » » » » 9 месяцев назад, # ^ |   0 Only if the additional edge will be between two adjacent nodes in the cycle, and that will fall under case 1).
•  » » » » » » 9 месяцев назад, # ^ |   +5 Just edge with same direction as cycle. Jump over 4 vertices.
•  » » » » » » » 9 месяцев назад, # ^ |   0 Yup you're right, somehow I missed that ;-;
•  » » 9 месяцев назад, # ^ | ← Rev. 3 →   0 For each cycle that you find, increase the number of cycles for each edge in it. Chech if there are any cycles and if yes, check if there is one edge which exists in every cycle.Edit: As it was already mentioned — each cycle has maximum n edges, so the complexity should be something like O(nm).
•  » » » 9 месяцев назад, # ^ |   0 Your code(and mine) outputs wrong answer on test 4 6 1 2 2 4 2 3 3 1 4 3 3 2The expected answer is NOThe problem seems to be that one back edge can produce more than one cycle, I think
•  » » 9 месяцев назад, # ^ | ← Rev. 2 →   0 I passed the pretests by checking for every edge if the graph without this edge has a cycle. O(nm). Edit: I'm wrong
•  » » 9 месяцев назад, # ^ |   0 I run a dfs on the graph. If there are <= 1 back edges, the answer is yes.Otherwise, I try erasing each tree edge. Is this correct? XD obviously I cannot remove all the cycles by removing a back edge if there are more than one back edge... But cross and forward edges shouldn't matter, right?
 » 9 месяцев назад, # |   0 Was O(n*m) intended complexity for D?
 » 9 месяцев назад, # |   +3 Was O(n*m) intended complexity for D?
•  » » 9 месяцев назад, # ^ |   0 I think yes. My solution is O(nm) too.
 » 9 месяцев назад, # |   0 what can be the test case 6 for C?
•  » » 9 месяцев назад, # ^ |   0 3332 3000
•  » » 9 месяцев назад, # ^ |   0 Maybe something like that : 123456 165422Excepted answer : 165342
•  » » 9 месяцев назад, # ^ | ← Rev. 2 →   0 a = 22221b = 22220ans = 22212
•  » » 9 месяцев назад, # ^ |   0 i think maybe something like this24954951
 » 9 месяцев назад, # |   +3 for E, time limit is very tight, my Q * log2(N) solution got TLE, i regret it
•  » » 9 месяцев назад, # ^ |   0 Same here :) Is there any faster way than lazy propagation?
•  » » » 9 месяцев назад, # ^ |   0 maybe there is, you can see any solutions
•  » » » 9 месяцев назад, # ^ |   0
 » 9 месяцев назад, # |   0 Do hacks get included in the system tests for Educational rounds as well?
•  » » 9 месяцев назад, # ^ |   0 Yes they do the final systests contains all the hacks
•  » » » 9 месяцев назад, # ^ |   0 So by hacking you can increase your rank? and get a better rating change?
•  » » » » 9 месяцев назад, # ^ |   0 No, not in edu round
•  » » » » » 9 месяцев назад, # ^ |   +7 If your hack is something the real sys test won't catch (and only would thanks to your hack), then yes hehe.
 » 9 месяцев назад, # | ← Rev. 2 →   +6 Why the problem C contains only 10 tests and problem D contains only 12 tests? C contain some corner cases and D is YES/NO problem. I thought in ERs the writer should add full testset and challenges are intended only to find some corner cases of concrete solutions? UPD: The problem B contains only 10 tests!!! It's awful. My solution contains 6 cases, but actually there are 8 cases in that problem.
•  » » 9 месяцев назад, # ^ | ← Rev. 2 →   +4 It is Educational Round so they should allow hacks.If he did that there will be no hacks at all.
•  » » » 9 месяцев назад, # ^ |   +3 Of course I missed last 21 ERs, but I think that the goal of them was not to have some hacks but to fully test solutions during round for educational purposes. The hacks was needed to be sure that corner tests was made for each given solution to fail all wrong ones.
•  » » » » 9 месяцев назад, # ^ |   +14 If you had very big and effective test set, no one will be able to hack. In Educational rounds hacking is so strong (You can hack without any risk). So the writer can choose any test and that will be OK.BTW problem C is almost unhackable
•  » » » » » 9 месяцев назад, # ^ |   +8 My point is that the purpose of ERs is to teach participants. If the problem contains full testset, the participant will see the fail of solution during contest and try to fix it in BRAIN-IN-CONTEST-MODE. It is much more useful, because some participants will not even check fail of their solutions AFTER the contest and will be disappointed, while they can get good expertise by fixing the solution during short time during contest. Also during contest participants can't see test on which their solutions failed. It's very useful skill to find a bug in solution without knowing the test.
•  » » » » » » 9 месяцев назад, # ^ |   +35 Hey! Thank you for comment. Take in account, that we can't judge many tests during ICPC-like rounds. We have thousands of participants and to prevent long judging queue we can't have more than 6-20 tests on easy problems. One more point, right now we regularly host 2 such rounds per month and we do not have resources to construct perfect testsets. Good news that because of hacks the final quality of testsets is usually about perfect. Strong contest tests will demotivate participants to hack and probably it can reduce the final quality of tests.
•  » » » » » » » 9 месяцев назад, # ^ |   +5 I think having full testset is better than having lot of hacks. More than 600 solutions for todays B is already hacked (I guess it will be more than 1000 after full system test) and I think it's bad. I agree with BledDest several tests in one will be good solution to test fast a lot of solutions on a large testset.
•  » » » » » » » » 9 месяцев назад, # ^ |   0 In my opinion, the biggest problem with the B pretests is all the pretests are "particular" cases: either l=1 or r=n or the current tab was at the same distance from l and r.
•  » » » » » » » 9 месяцев назад, # ^ |   0 You can use multitests
•  » » 9 месяцев назад, # ^ |   -8 because problem authorus think like "whatever, we got 24 h of hacking time, couple of yellow/red guys will definitely make some hacks so we will just add their hacks as systests and during round we'll only do standard 10-15 pretests, but now we will call it just tests. Why we do this? because we are lazy trashs"
•  » » 9 месяцев назад, # ^ |   +13 The main reason why we have small testsets is to speed up testing. The queue on the first rated ER was really awful, so we had to do something about it.Maybe a better solution would be adding multitests to each problem. Perhaps we should give it a try when preparing next round.
•  » » » 9 месяцев назад, # ^ | ← Rev. 2 →   +5 I also think that multitest is a good solution. Hope I will participate in the next ER and see multitests :)
 » 9 месяцев назад, # |   +13 Who else too lazy to work on the detail for the solution using coordinate compressing and segment tree, wrote dynamic segment tree instead and got TLE on E?
•  » » 9 месяцев назад, # ^ |   +5 It is disappointing that in E dynamic segment tree get's tle. I wanted to implement this structure and thought that this task might be perfect for it...
•  » » 9 месяцев назад, # ^ |   0 xuanquang1999 if you are creating new nodes in heap try to create it in stack instead Node d[15000000]; int curr; // ID of last node I created if (root->left == NULL) ++curr, root->left = d+curr; if (root->right == NULL) ++curr, root->right = d+curr; my first solution I created new nodes in heap and got TLE in test 18, and then after some optimization got MLE in test 32 :D now after creating new nodes in stack instead it finally gives AC.
•  » » » 9 месяцев назад, # ^ |   0 Thanks for your tip. I will try it.
 » 9 месяцев назад, # |   +1 Logic for C?
•  » » 9 месяцев назад, # ^ |   0 Build the answer from the first to last digit by trying each digit from 9 to 0. Checking if a digit work can be done by trying to put all the unused digit to the right of the answer (from smallest to largest) and check whether the number you get does not exceed b.
•  » » 9 месяцев назад, # ^ | ← Rev. 2 →   0 Look at the leading digit of b. Call it N. If a has N, then try to form a number from a that starts with N and is less than b without it's leading digit. (you can use recursion) 1a. If you can't form a valid number (formed number>b), continue to next step. If a does not have N, find the largest digit of a less than N (call it M). Place that digit next, and after that, place the digits of a, sorted, as it will always be less than b. If M does not exist (which isn't possible at start but if you do it recursively it will be possible), then return some value indicating this route is impossible. It is O(N*logN) because there is a max of 1 recursive call per call, and by using binarySearch you can find the elements of a in logN time.Edit: On second thought, I think this version is harder to implement than most, so you may want to try using someone else's.
 » 9 месяцев назад, # |   0 After the end of the contest you will have one day to hack any solution you want. You will have access to copy any solution and test it locally. Where is open hacking?
 » 9 месяцев назад, # | ← Rev. 2 →   0 I am new on codeforces. I have much question about this bootcamp. I am from bangladesh and I am a school student, Read in 0 Level. I want to participate on this bootcamp.but I didn't understand how? is there any school student's allowed?if allowed then I want to go. But I haven't money to pay for this my family isn't have enough money. and most of I haven't any passport and paypal or anything bank account.But I want to participate on this. But How? please Help me? Vovuh PikMike
•  » » 9 месяцев назад, # ^ |   0 Hello, soohotiamPlease check your private messages.
•  » » » 9 месяцев назад, # ^ |   0 Hmm.Thank You :)
•  » » » 9 месяцев назад, # ^ |   0 I Have The Same Question.
•  » » » » 9 месяцев назад, # ^ |   0 Hello, HBK_WasiPlease check your private messages too.
•  » » » » » 9 месяцев назад, # ^ |   0 I have the same question and I am from same state.
•  » » » » » 9 месяцев назад, # ^ |   0 hw[user:Harbour.Space ] I have the same question
•  » » » » » » 9 месяцев назад, # ^ |   0 Hello, Nayeem_x009Please check your private messages too.
 » 9 месяцев назад, # |   0 After the end of the contest you will have one day to hack any solution you want. You will have access to copy any solution and test it locally. Where is open hacking?
 » 9 месяцев назад, # |   0 Will an unsuccessful hack decrease my points?
•  » » 9 месяцев назад, # ^ |   0 Nope
 » 9 месяцев назад, # |   +3 Check this for C:9111222 9222000
•  » » 9 месяцев назад, # ^ |   +6 9221211
 » 9 месяцев назад, # |   +1 How to solve C?
•  » » 9 месяцев назад, # ^ |   0 Something like that: 34143849
 » 9 месяцев назад, # |   0 is there any dp solution of C?
•  » » 9 месяцев назад, # ^ |   +3 simple (dp + bitmask)
•  » » » 9 месяцев назад, # ^ |   0 i tried but could not implement.can you share your idea?what are the state of dp?
•  » » » » 9 месяцев назад, # ^ | ← Rev. 3 →   +5 dp[msk][lss]msk tells which digits of a you have already used, lss is a bit which tells if the new number is already less than b. You go from the most significant digit to the least, (you can get the position of the digit from msk, so there's no need to include it in memory).Note that there's only really two options to try, put the exact same digit of b (and you solve the rest with the same approach) or put the maximum of the available digits which are less than the correspondent digit of b, in that case, the rest of the number is just the sorted (decreasingly) remaining available digits of a (so no need to recurse in this case). This would work without dp
•  » » » » » 9 месяцев назад, # ^ |   0 thank you for your comment.now i got ac.only bug was in my code, i initialized res equal to 0,now i initialize it with LLONG_MIN.Can you say that what is the problem when i initialize res equal to 0(it gives wrong output in sample test 1). http://codeforces.com/contest/915/submission/34157330
•  » » » » » » 9 месяцев назад, # ^ | ← Rev. 2 →   +3 By having res = 0, you are making some impossible answers possible. for example: res = 0 res = max(res, go(xyz)) // i.e. max(0, LLONG_MIN) when your go() itself returns impossible, then how can res have any other value than impossible (i.e. LLONG_MIN)if you still want to use res = 0. You can do that. You can check if go() returned any possible answers or not and then only calculate max(res, go()).
•  » » » » » » » 9 месяцев назад, # ^ |   0 thanks.now i got it.
•  » » » » » 9 месяцев назад, # ^ |   0 I tried solving C using digit dp , it worked but using memoization gave WA and otherwise was too slow and gave TLE . I used state as dp[index][r] where r is 0/1 which tells if formed number is smaller/greater than b , I suppose the dp state I considered was incomplete there needs to be one more parameter what could it possibly be?
•  » » » » » » 9 месяцев назад, # ^ |   0 That's usually easy to do. Look for things you use in your function which are not determined by the state. In this case I guess you had something outside the state that told you which digits you have used.
 » 9 месяцев назад, # |   0 Nice problemset, though I couldn't make it through D. Have to study directed graphs better :D
 » 9 месяцев назад, # |   0 the problem statement for B says that "if the cursor is currently at the tab i, then she can move it to the tab max(i-1,a) or to the tab min(i+1, b))" where a an b are just the values of the input (l and r) correct? for me this implies that if i is outside of [a,b] i can always get there in one step? if i < a then max(i-1, a) will be a and if i > b then min(i+1, b) is b therefore in testcase 9 (100 1 100 100) it would take me one step to get to tab 100 and another step to delete all tabs therefore it would only require 2 steps and not 100!
•  » » 9 месяцев назад, # ^ |   0 Let's say L=3 R=7 and POS=10.You can't move to L=3 in 1 move because max(POS-1,L) = POS-1
•  » » 9 месяцев назад, # ^ |   0 No.As stated, In the aforementioned expressions a and b denote the minimum and maximum index of an unclosed tab, respectively.Therefore, if you move left right on the 1st step, you will still stand at tab 1, since a = 1 (as tab 1 is the unclosed tab with minimum index). As a result, your next delete command will only delete that tab.
•  » » » 9 месяцев назад, # ^ |   0 ok well i believe i just misunderstood the task... i believe i read a and b as l and r...
 » 9 месяцев назад, # |   0 Does hacking give any points or score?
•  » » 9 месяцев назад, # ^ | ← Rev. 2 →   0 Not in Educational Rounds!
•  » » » 9 месяцев назад, # ^ |   +4 So is it just hacking for fun in edu rounds?
 » 9 месяцев назад, # |   0 My O(N*sqrt(N)) solution on G got TLE. I'm wondering whether I should optimize it or there exist a O(N) or O(N*log(N)) solution for that.
•  » » 9 месяцев назад, # ^ |   0 Take a look at the accepted submissions and you'll find there exists O(nlogn) solution using inclusive-exclusive theorem for Problem G.
 » 9 месяцев назад, # |   0 How soon will the rating changes come out?Can I get points by hacking others?Any dalao?
 » 9 месяцев назад, # |   0 Does codeforces gives extra points for hacking own solution???
 » 9 месяцев назад, # |   0 Is anybody else having trouble with hacking somebody else's solution?I click on "hack it" on a solution, but the window to insert my input won't show. There is only the button "Hack" when I click "hack it".
•  » » 9 месяцев назад, # ^ |   +6 The same problem with google chrome, no problem with firefox though :\
•  » » 9 месяцев назад, # ^ |   +8 Happens to me in chrome, but is fixed everytime if I do ctrl+F5 in that page. I don't know if that works for everyone
 » 9 месяцев назад, # | ← Rev. 2 →   +1 Off topic.. I thought Christmas Magic is over. But how come this user's (kissu_pari_na) profile is still showing that he's a CM? Is it a bug?
•  » » 9 месяцев назад, # ^ |   0 Not sure.. But it's still unchanged!
•  » » 9 месяцев назад, # ^ |   0 Now it's normal :) Dynamic_Ovi
 » 9 месяцев назад, # |   +28 You know it's not your lucky day when you go to the mall to focus on the contest in a quiet cafe and it turns out that they have some noisy ass celebration at the same time
 » 9 месяцев назад, # |   0 what is wrong with problem B :|
•  » » 9 месяцев назад, # ^ |   +1 See this test case:6 1 4 5Your answer is 9 but it should be 6
•  » » » 9 месяцев назад, # ^ |   0 holy shit man
 » 9 месяцев назад, # |   +3 Can someone please explain how to solve problem F and if it can be solved using centroid decomposition?
•  » » 9 месяцев назад, # ^ |   +5 Idk but sorting+Union-find also gets the job done.Here, check my solution:http://codeforces.com/contest/915/submission/34157745
•  » » » 9 месяцев назад, # ^ |   +5 Can you explain your solution ?
•  » » 9 месяцев назад, # ^ |   +13 Solution with centroid decomposition is too slow.
•  » » » 9 месяцев назад, # ^ |   0 Thank you
•  » » 9 месяцев назад, # ^ |   +5 Actually when I read the problem first thought came to my mind was Centroid Decomposition, but on reading constraints 106 and not 105 , it can be really risky, I thought more, and decided to go for DSU + Sorting solution, faster non-asymptotically.
•  » » » 9 месяцев назад, # ^ |   0 Ok, I understand now.
 » 9 месяцев назад, # |   0 Can one explain Problem E(Approach)?
 » 9 месяцев назад, # |   0 The rating predictions of the predictor seem to be very wrong,don't they? It says that someone who won a div2 round will become yellow,straightaway.
 » 9 месяцев назад, # |   0 Any corner case for B ? lot's of solution of B is getting hacked!!
 » 9 месяцев назад, # |   +3 Any corner case for B ? lot's of solution of B is getting hacked!!
•  » » 9 месяцев назад, # ^ |   0 100 100 1 1
•  » » » 9 месяцев назад, # ^ |   0 it should be 100 not 96
 » 9 месяцев назад, # | ← Rev. 2 →   0 Questions regarding Problem B. How should solution be interpreted for testcase: 7 3 3 3? Should Luba do any movement? From problem statement it is not clear what happens after closing windows for example from [3,7].My solution has been hacked, but I found only that difference of my solution with others (likely successful).
•  » » 9 месяцев назад, # ^ |   0 As I'm thinking, we will only need 2 actions: delete the tabs to the left, then delete the tabs to the right. We're at tab 3 already, so we don't need to make any movements.
•  » » » 9 месяцев назад, # ^ |   0 It looks like there should be some movement if I am not wrong. I compared top-ranked person's solution: int n, pos, l, r; cin >> n >> pos >> l >> r; if (l == 1 && r == n) { cout << 0; return 0; } if (l == 1 ) { cout << 1+abs(pos-r); return 0; } if (r == n) { cout << 1 + abs(pos - l); return 0; } cout << min(2 + abs(pos - l) + abs(r - l), 2 + abs(pos - r) + abs(r - l)); return 0; With my solution: int n, pos, l, r; cin >> n >> pos >> l >> r; if (l == 1 && r == n) { cout << 0; } else if (l == 1) { cout << 1 + abs(r - pos); } else if (r == n) { cout << 1 + abs(l - pos); } else if (l == r) { cout << 2; } else { cout << 2 + min(abs(r - pos) + (r-l), abs(l - pos) + (r-l)); } return 0; And only difference in logic is for such type of use-cases like 7 3 3 3. However, I believe it is not clear situation.
•  » » » » 9 месяцев назад, # ^ | ← Rev. 2 →   0 Hacked!Test case: 9 6 3 3 — answer: 5.When l == r, you can only assume the answer is 2 when the initial position is on tab l/r.
•  » » » » » 9 месяцев назад, # ^ |   0 Thank you! Stupid mistake :(
 » 9 месяцев назад, # |   +1 Any critical case for C?
 » 9 месяцев назад, # |   +2 How to solve Problem D: Almost Acyclic Graph?
 » 9 месяцев назад, # | ← Rev. 5 →   +21 Why do you hack others if you can hack yourself? (2 line)
 » 9 месяцев назад, # |   +13 halyavin is certainly crazy madman
•  » » 9 месяцев назад, # ^ |   +11 I don't he is doing it manually, looks like halyavin has automated the whole process!
 » 9 месяцев назад, # |   +66 @halyavin Thanks for the early system testing
 » 9 месяцев назад, # |   +4 How to solve E, F?
 » 9 месяцев назад, # |   -6 The feeling that Educational contests is more difficult than Div 2(((
 » 9 месяцев назад, # |   0 What was the idea behind D? Was there some fast way to check for a cycle, or something else?
•  » » 9 месяцев назад, # ^ | ← Rev. 6 →   +3 SOLUTION OF D: I search one cycle and check remove each edge of cycle. I do this because the maximum edge in the circle is N, then it is necessary N dfs at most. O( N * (100000). )Submission:34164803
•  » » » 9 месяцев назад, # ^ |   0 Good Solution!
•  » » » 9 месяцев назад, # ^ |   +3 I think add this line will be beteer. You just need to add one roop's edges.  int ciclo = 0; for(int i = 1; i <= n; i++){ if(!cor[i]) ciclo = ciclo or dfs(i); if (ciclo==1) break; //add this line? } 
•  » » » » 9 месяцев назад, # ^ |   0 You are right xD. Probably i get TLE on some new test.
 » 9 месяцев назад, # | ← Rev. 3 →   +3 Although the quality of problems in this round is quite good, I'd like to say that the time limit of E and G are a bit tight(at least for me).My complexity for E is O(q log q) (segment tree) and complexity for G is O(k(log k+log n)) (inclusion-exclusion principle).Yet I failed on pretest in both problems, even though I tried to add code like #pragma GCC optimize("Ofast") Actually, in my opinion, the time complexity of my solution is the same as that of the intended solution in either E or G.After the contest, I shortened my code of G(unfolded one function). Then I passed the pretests, finding even this time I almost got TLE(3494ms): 34163831How did all these happen? Feeling Curious.[sorry for my poor English]UPD:My approach in E and G not only have the same complexity as the author's solutions,THEY ARE EXACTLY THE SAME!
•  » » 9 месяцев назад, # ^ |   0 My solutions have the same complexity and I have no problem with TLE: ~800ms on E and ~1200ms on G. I've done no optimizations in both problems.I also think that the TLE for E is a little bit tight but maybe authors tried to fail solutions with dynamic segment tree.
 » 9 месяцев назад, # | ← Rev. 2 →   0 I have looked at some solutions for G and all that I have found use inclusion-exclusion or something of that sort. What I did was much shorter and in my mind, simpler.Here is my submission: http://codeforces.com/contest/915/submission/34164542Let's say an array has degree i if its largest value is i. What I did was let dp[i] be the number of coprime arrays with degree i. So, for example, dp[2] = 2n - 2. The key observation is that every coprime array of degree i corresponds to an array of degree i·m with a gcd of m. So, to find the array dp you can initialize it to dp[i] = in - (i - 1)n and then go in increasing order of indices, subtracting dp[i] from dp[j] for all 1 ≤ j ≤ k that are multiples of i.bi is now just the prefix sum dp[1] + dp[2] + ··· + dp[i]. All you have to do now is keep a running sum.Please leave a comment if you did something like this as well.
•  » » 9 месяцев назад, # ^ |   0 Cool and simple solution!My solution (and I guess most of other solutions) use Möbius inversion formula
•  » » 9 месяцев назад, # ^ |   0 I did exactly this though my solution somehow runs quite close to TL.
 » 9 месяцев назад, # | ← Rev. 2 →   0 In problem C how to approach the case where len(b)<= len(a) // considering both of them are in string form The other case is quite simple. But I am having a hard figuring out the logic for this case. UPD: I now understand after trying some test cases by hand.
•  » » 9 месяцев назад, # ^ |   0 Is it even possible for len(b) to be less than len(a) ? The problem statement doesn't add this constraint but I don't think a solution is guaranteed if len(b) is less than len(a), since leading zeros are not allowed, a will always be larger in this case.
•  » » » 9 месяцев назад, # ^ |   0 What about this case : 4000 599
•  » » » » 9 месяцев назад, # ^ | ← Rev. 2 →   0 the problem statement guarantees an answer, so it can't give you in an input where length of B is less than length of A because all permutations of A will lead to a number greater than B (and you can't play on leading zeros because they are not allowed), and if the length of B = length of A there must be at least one permutation of A which gives you a number <= B
 » 9 месяцев назад, # | ← Rev. 3 →   0 I have submitted the same code twice: 34164987 and 34165069. The first one passed 16th test and got Accepted with 888ms, the second one got TLE right at test 16. Can anybody explain to me why? Thanks! (I know the variability of the judging machines maybe the cause, but the difference should be smaller than 30ms, shouldn't it? ). (UPD: OK, it turns out because of different compilers, and C++14 speciafically optimize the speed of cin cout while C++11 can't do that!)
 » 9 месяцев назад, # | ← Rev. 2 →   +41 In case you missed the hack festival: Update: 725 and counting!
•  » » 9 месяцев назад, # ^ |   +3 hmm hacked mine .
 » 9 месяцев назад, # |   +3 "and head coach will be two time ACM-ICPC world champion Gleb GlebsHP Evstropov."Может быть вице-чемпион?)
 » 9 месяцев назад, # |   -17 What about this case in Problem C1230 123answer should be 0123 but many solutions which are giving answer 1230(wrong answer) ,still accepted. (weak test cases in problem C)
•  » » 9 месяцев назад, # ^ |   +4 0123 is clearly not a valid answer. As in the problem description No number in input and/or output can start with the digit 0. And also the problem promises that It is guaranteed that answer exists., so 1230 123 is definitely not a valid input.
•  » » » 9 месяцев назад, # ^ |   -8 You can't discard leading zeroes First Line in Note on Problem C. It Means output can start with leading zeros
•  » » » » 9 месяцев назад, # ^ |   0 "The answer can't have any leading zeroes."This is quote from output format from the problem statement. Read carefully.
•  » » 9 месяцев назад, # ^ | ← Rev. 3 →   0 judge validator showed me that this is invalid input.hack attempt tool : hacking attempt tool verdictin test case4: main test case 4why???my test case was: 102 100validator said that is test case is invalid.
•  » » » 9 месяцев назад, # ^ |   0 There is not answer for your test case. The minimum permutation of a is greater than b.
•  » » » » 9 месяцев назад, # ^ | ← Rev. 3 →   0 thank you , got it . from validator verdict i thought a can't greater than b that's why.
 » 9 месяцев назад, # |   0 What exactly is the "Division" in the registration form? It contains three options: A, B, and C.
•  » » 9 месяцев назад, # ^ |   +2 Division A Designed to prepare students to participate and win medals in the next ACM-ICPC World Finals.A large number of teams that participated in Moscow workshops later became ACM-ICPC Finalists and even won medals — to be specific, 8 out of 12 prize-winners of the ACM-ICPC World Finals 2017 participated in Moscow Workshops ACM ICPC!Division B Designed to help teams prepare for the next season of ACM-ICPC regionals an international competitions. Appropriate as an introduction for teams and students just getting their foot in the door of the world of ACM-ICPC and competitive programming competitions in general.Division C Designed for newcomers to the world of ACM-ICPC competitive programming. For those with a handle on the basics but want to compete in future competitions and possible regionals, this division is the perfect starting point.
 » 9 месяцев назад, # |   0 Does this round have an editorial?
•  » » 9 месяцев назад, # ^ |   0 Should be published once the hacking phase is over.
 » 9 месяцев назад, # |   0 When will the rating change be applied ?
•  » » 9 месяцев назад, # ^ |   0 Open hacking phase is running. After that system tests will run with hacks. Only after that will ratings be calculated.
•  » » » 9 месяцев назад, # ^ |   0 And how long is the hacking phase ?
•  » » » » 9 месяцев назад, # ^ |   0 Ends 24 hrs after contest end.
 » 9 месяцев назад, # |   +51 I think we don't even need a system tests) halyavin already done that with 700+ hacks)
•  » » 9 месяцев назад, # ^ |   +3
 » 9 месяцев назад, # |   +32 When does system testing start?
•  » » 9 месяцев назад, # ^ |   0 So many hacks make it hard to start?So sad...Hope I can change my colour.
•  » » 9 месяцев назад, # ^ | ← Rev. 2 →   +9 System testing has started....and looks like it will take forever to finish.
•  » » » 9 месяцев назад, # ^ |   +3 It would take around 2-3 hours for system testing to finish.
•  » » » » 9 месяцев назад, # ^ |   +5 jesus christ !
•  » » » 9 месяцев назад, # ^ |   +4 Probably because in educational round system tests happens for every user which includes users who didn't participate in the round but submitted a solution for practice. So i guess it's time consuming.
 » 9 месяцев назад, # |   +3 I submitted 3 solutions for B out of which last 2 were hacked and first got AC but in standings page it is not showing the AC. Can someone please check?
•  » » 9 месяцев назад, # ^ |   0 In regular contests (not educational) only the last submssion that passes pretest is considered
•  » » » 9 месяцев назад, # ^ |   0 So mine should be considered as correct as it is educational, isn't it?
•  » » » » 9 месяцев назад, # ^ |   0 I am not sure, maybe there is no official answer yet. In the announcement of educational rounds and in this very blog we are commenting it is only said that it is held on extented ACM ICPC rules — maybe there is a formal description of such rules that I dont know about, but it is a good question.
•  » » 9 месяцев назад, # ^ |   +10 I'll look in it tomorrow.
•  » » » 9 месяцев назад, # ^ |   0 Any updates Mike?
 » 9 месяцев назад, # |   +11 When does rating appears ?
•  » » 9 месяцев назад, # ^ |   +3
 » 9 месяцев назад, # |   0 I would like to make an appeal on my charge of rewriting. I did not copy other codes. I typed my code without any help, four times I made a mistake until I solved ut. I have nothing to do with paulica. While I was trying to hack others I saw a lot of similar codes, I claim this is just a coincidence and that it was possible for everyone to happen. I had no way to get to his code.
 » 9 месяцев назад, # |   0 can we know the time duration in which these users solved the problems???
 » 9 месяцев назад, # |   +8 Good educational round. Very interesting problems.
 » 6 недель назад, # |   0 I dont wish ratings like my contribution :-) Good luck and peace!