Hello Codeforces!
On January 13, 16:05 MSK Educational Codeforces Round 36 will start.
Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.
This round will be (traditionally now) rated for Div. 2. It will be held on extented ACM ICPC rules. 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.
You will be given 7 problems and 2 hours to solve them.
The problems were prepared by Mikhail awoo Piklyaev, Ivan BledDest Androsov, Sergey sslotin Slotin and me.
Good luck to all participants!
I also have a message from our partners, 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.
You can find more information and registration, click here
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.
Congratulations to the winners:
Rank | Competitor | Problems Solved | Penalty |
---|---|---|---|
1 | JustasK | 7 | 265 |
2 | uwi | 7 | 275 |
3 | KrK | 7 | 277 |
4 | LHiC | 7 | 284 |
5 | latte0119 | 7 | 331 |
Congratulations to the best hackers:
Rank | Competitor | Hack Count |
---|---|---|
1 | halyavin | 725:-45 |
2 | zscoder | 34:-10 |
3 | M3hran | 28:-3 |
4 | OlegZubkov | 28:-3 |
5 | neelbhallabos | 21 |
2023 successful hacks and 1300 unsuccessful hacks were made in total!
And finally people who were the first to solve each problem:
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 | ThePilgrim | 0:15 |
G | MrDindows | 0:19 |
UPD Editorial
This round will be (traditionally now) rated for Div. 2
Does this Mean that all "Educational Rounds" will be rated for Div.2?
It is unknown now but we hope so =)
Last 4 rounds are so, so maybe!
From now "Educational Rounds" will be rated for Div.2
But maybe some rounds will be unrated for Div.2
i wish everyone ratings equal to my contribution :)
Me contribution is well er. u not know da wae.
No. Stop it. Get some help.
I don`t wish ratings like my contribution :-) Good luck and peace!
luck and peace are for the weak
maybe, you are right. However, I can't see that you are red, therefore you also need luck and peace)))
shut up green noob im blue im superior
racism
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.
this is smurf account fag , i have +20 contests on other account
So what...I don't know what you are proud of.Respect others effort plz
Does this educational focus on classical problems like a good portion of the previous ones, or should I be expecting a regular round?
Timelimit for all questions is very tight!
"Thanks Mike" is compulsory!!!!!!!
where are polygons???
Polygon
polygon
Good luck to everyone :)
GL & HF!
pikmike's and vovuh's rating graphs are very inspiring.
Will you (as a prize) tach the 1st place's spagett? or let them tach yours
since when GlebsHP is two time world champion?
shit, solved D but B and C too hard for me(((
How did you solve C?
Just use greedy method to construct your ans.
Timelimit for E is very tight!
After the contest ends:
Where is that test #6?
UPD: It is Educational Round so how can we know test #6?
Consider the input 543 433. (If you mean the task C. I imagine a correct solution uses backtracking)
For C? Try this : 201 200
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).
Implicit segment tree can do work. But I couldn't find my bug.
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.
use struct and pointer
if you are creating new nodes in heap try to create it in stack instead
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.
my seg tree O(Q * log2(N)) solution got TLE, time limit is very tight
Where do you get the second log2 from? Is it an approximation for your lazy?
you can see it, 34143231
I did the pragma thing mentioned in some other comment and my tle solution passed!
I did segtree with coordinate compressing, got TL16
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).
what's the complexity? Especially the part of " I erase the segments which are totally inside the new one" ?
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.
Nice, thanks.
if you don't mind can you please explain how to implement this?
http://codeforces.net/contest/915/submission/34146439
take a look at my submission, shouldn't be hard to understand. It's easy because at any point there are no overlapping segments
Idea for D ?
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)
I tried this and got TLE multiple times
Seems TL is tight, just add pragmas and optimizations to your code and send it again. I'm not sure either.
Can you show me your pragmas?
thx
For those who know, this might sound dumb so pls bear with it -: What are pragmas? What do above #pragmas statements do?
I don't know too
xD I don't know most of them also :P
But 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.I sent your code with pragmas and it got TLE again, TL complexity of algorithm seems correct, but.. I don't know
I tried same idea and passed, but I forgot to erase elements from stack (So I got hacked :'( ). But it should work.
Code
Won't the complexity be O(m2) then ?
No, there are N edges in one cycle at most.
Ouch !!! Should have seen this. Thanx.
No, because maximal cycle have n edges
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.
There can be only one scc but a clique.
This doesn't work with sample tests.
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.
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
You can have one cycle with one additional edge but still you can remove cycle with only one edge.
Only if the additional edge will be between two adjacent nodes in the cycle, and that will fall under case 1).
Just edge with same direction as cycle. Jump over 4 vertices.
Yup you're right, somehow I missed that ;-;
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).
Your code(and mine) outputs wrong answer on test 4 6 1 2 2 4 2 3 3 1 4 3 3 2
The expected answer is NO
The problem seems to be that one back edge can produce more than one cycle, I think
I passed the pretests by checking for every edge if the graph without this edge has a cycle. O(nm). Edit: I'm wrong
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?
Was O(n*m) intended complexity for D?
I think yes. My solution is O(nm) too.
what can be the test case 6 for C?
Maybe something like that : 123456 165422
Excepted answer : 165342
a = 22221
b = 22220
ans = 22212
i think maybe something like this
2495
4951
for E, time limit is very tight, my Q * log2(N) solution got TLE, i regret it
Same here :) Is there any faster way than lazy propagation?
maybe there is, you can see any solutions
my comment above
Do hacks get included in the system tests for Educational rounds as well?
Yes they do the final systests contains all the hacks
So by hacking you can increase your rank? and get a better rating change?
No, not in edu round
If your hack is something the real sys test won't catch (and only would thanks to your hack), then yes hehe.
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.
It is Educational Round so they should allow hacks.
If he did that there will be no hacks at all.
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.
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
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.
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.
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.
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.
You can use multitests
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.
I also think that multitest is a good solution. Hope I will participate in the next ER and see multitests :)
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?
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...
xuanquang1999 if you are creating new nodes in heap try to create it in stack instead
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.
Thanks for your tip. I will try it.
Logic for C?
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.
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.
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 awoo
Hello, soohotiam
Please check your private messages.
Hmm.Thank You :)
Will an unsuccessful hack decrease my points?
Nope
Check this for C:
9111222 9222000
9221211
How to solve C?
Something like that: 34143849
is there any dp solution of C?
simple (dp + bitmask)
i tried but could not implement.can you share your idea?what are the state of dp?
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
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.net/contest/915/submission/34157330
By having
res = 0
, you are making some impossible answers possible.for example:
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 calculatemax(res, go())
.thanks.now i got it.
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?
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.
Nice problemset, though I couldn't make it through D. Have to study directed graphs better :D
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!
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
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.
ok well i believe i just misunderstood the task... i believe i read a and b as l and r...
Does hacking give any points or score?
Not in Educational Rounds!
So is it just hacking for fun in edu rounds?
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.
Take a look at the accepted submissions and you'll find there exists O(nlogn) solution using inclusive-exclusive theorem for Problem G.
How soon will the rating changes come out?Can I get points by hacking others?Any dalao?
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".
The same problem with google chrome, no problem with firefox though :\
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
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?
Not sure.. But it's still unchanged!
Now it's normal :) I_am_Heisenberg
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
what is wrong with problem B :|
See this test case:
6 1 4 5
Your answer is 9 but it should be 6
holy shit man
Can someone please explain how to solve problem F and if it can be solved using centroid decomposition?
Idk but sorting+Union-find also gets the job done.
Here, check my solution:http://codeforces.net/contest/915/submission/34157745
Can you explain your solution ?
Solution with centroid decomposition is too slow.
My TLE code: http://codeforces.net/contest/915/submission/34159437
Thank you
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.
Ok, I understand now.
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.
Any corner case for B ? lot's of solution of B is getting hacked!!
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).
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.
It looks like there should be some movement if I am not wrong. I compared top-ranked person's solution:
With my solution:
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.
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.Any critical case for C?
How to solve Problem D: Almost Acyclic Graph?
Why do you hack others if you can hack yourself? (2 line)
halyavin is certainly crazy madman
I don't he is doing it manually, looks like halyavin has automated the whole process!
@halyavin Thanks for the early system testing
How to solve E, F?
The feeling that Educational contests is more difficult than Div 2(((
What was the idea behind D? Was there some fast way to check for a cycle, or something else?
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
Good Solution!
You are right xD.
Probably i get TLE on some new test.
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
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): 34163831
How 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!
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.
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.net/contest/915/submission/34164542
Let'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.
Cool and simple solution!
My solution (and I guess most of other solutions) use Möbius inversion formula
I did exactly this though my solution somehow runs quite close to TL.
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.
Is it even possible for
len(b)
to be less thanlen(a)
? The problem statement doesn't add this constraint but I don't think a solution is guaranteed iflen(b)
is less thanlen(a)
, since leading zeros are not allowed,a
will always be larger in this case.What about this case :
4000 599
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
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!)
In case you missed the hack festival:
Update: 725 and counting!
hmm hacked mine .
What about this case in Problem C
1230 123
answer should be 0123 but many solutions which are giving answer 1230(wrong answer) ,still accepted. (weak test cases in problem C)
0123
is clearly not a valid answer. As in the problem descriptionNo number in input and/or output can start with the digit 0.
And also the problem promises thatIt is guaranteed that answer exists.
, so1230 123
is definitely not a valid input.You can't discard leading zeroes First Line in Note on Problem C. It Means output can start with leading zeros
"The answer can't have any leading zeroes."
This is quote from output format from the problem statement. Read carefully.
judge validator showed me that this is invalid input.
hack attempt tool : hacking attempt tool verdict
in test case4: main test case 4
why???
my test case was: 102 100
validator said that is test case is invalid.
There is not answer for your test case. The minimum permutation of a is greater than b.
What exactly is the "Division" in the registration form? It contains three options: A, B, and C.
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.
Does this round have an editorial?
Should be published once the hacking phase is over.
When will the rating change be applied ?
Open hacking phase is running. After that system tests will run with hacks. Only after that will ratings be calculated.
And how long is the hacking phase ?
Ends 24 hrs after contest end.
I think we don't even need a system tests) halyavin already done that with 700+ hacks)
When does system testing start?
So many hacks make it hard to start?So sad...Hope I can change my colour.
System testing has started....and looks like it will take forever to finish.
It would take around 2-3 hours for system testing to finish.
jesus christ !
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.
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?
In regular contests (not educational) only the last submssion that passes pretest is considered
So mine should be considered as correct as it is educational, isn't it?
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.
I'll look in it tomorrow.
Any updates Mike?
When does rating appears ?
Good educational round. Very interesting problems.