On Oct/25/2018 17:35 (Moscow time) Educational Codeforces Round 53 (Rated for Div. 2) will start.
Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.
This round will be rated for the participants with rating lower than 2100. It will be held on extented ACM ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.
You will be given 7 problems and 2 hours to solve them.
The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov and me.
Good luck to all participants!
Our friends at Harbour.Space also have a message for you:
Hey Codeforces! We want to remind you that the Scholarship for the Master’s in Robotics programme, which starts on January 7th 2019, has an application deadline of November 12th, 2018.
Harbour.Space University and Remy Robotics are collaborating to offer graduate students from anywhere in the world a once in a lifetime opportunity, a fully funded scholarship for Harbour.Space University’s Master’s Programme in Robotics.
The scholarship value is €34.900 and it includes:
Complete coverage of the University tuition fee (€22,900)
Internship at Remy Robotics (20h per week during 1 year)
€1,000 per month during 1 year (Internship earnings)
UPD: vovuh and me will be waiting for you on the community Discord server shortly after the contest to discuss the problems.
Congratulations to the winners:
Rank | Competitor | Problems Solved | Penalty |
---|---|---|---|
1 | pekempey | 7 | 305 |
2 | ko_osaga | 7 | 578 |
3 | Lewin | 6 | 216 |
4 | fanache99 | 6 | 226 |
5 | natsugiri | 6 | 257 |
Congratulations to the best hackers:
Rank | Competitor | Hack Count |
---|---|---|
1 | halyavin | 238:-15 |
2 | Laggy | 64:-14 |
3 | MarcosK | 59:-9 |
4 | Mistra | 8:-1 |
5 | LordVoldebug | 7:-1 |
And finally people who were the first to solve each problem:
Problem | Competitor | Penalty |
---|---|---|
A | Dalgerok | 0:01 |
B | dorijanlendvaj | 0:02 |
C | fanache99 | 0:10 |
D | bazsi700 | 0:13 |
E | DAyamaCTF | 0:21 |
F | Noam527 | 0:48 |
G | ko_osaga | 0:24 |
UPD2: Editorial is published
...
I always have this question:Why Educational Codeforces Round uses extented ACM ICPC rules? I think the rules of CF regular rounds are very good:-) Thank MikeMirzayanov
I wish if they could make another round type with no pretests .. why is it so wrong that if I submit a solution I will get AC or WA instead of pretest passed and then a short sad story
I'm sorry. The last comment was not posted by me. I'm not mean to do it.
Yes, awoo became orange a few days ago.
After 4 years of hard work, nothing is impossible.
Congratulations, awoo!
Thanks! I still can't believe, I've actually managed to do that)
An inspirational story...I hope that I can do as well as you...TUT
Irelia is also my favorite hero ~
It's admirable and so cool,congratulations! You are my idol !
Hi all! this is my first round here. what should i know about codeforces?
You should know that this is not your first round.
You should know whether or not it is rated.
An Educational round after a bad contest, awesome.
Educational Round is here, Summon halyavin !!
[Again :( ] ^^ halyavin — The Hacking Machine
halyavin has data generator to hack us.
...and Mike allows him to do this in Education rounds.
Halyavin is done hacking, looks like systests are over.
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
How to solve Problem C?
Binary Search on length and check the possibility in O(n) by traversing the string.
Two pointer
Binary search on substring size.
To check if you can get from a position to other in certain number of moves, the sum of absolute differences between positions in both dimensions has to be not bigger than the numer of moves, and be of the same parity.
I did binary search on the length of the subsegment.
I'm so sad that I didn't have a code ready for segment tree beats. This would have been the first time I could use it in a real contest (in problem G) :(
Didn't have time to write it either since It once again took me too long to read other problems after getting stuck in one.
I dont think G needs segment tree beats though it is nice if it can solved that way.
we can compute lcp array and then for each query we can keep 2*query size ranges and perform something like for how many pairs of a and b will particular range be minimum value (its similar to solving sum of minimum over all segments in an array but instead we have weights to elements here).
How to solve E?
In general — digits and masks DP. Calculate the following dynamic programming: dp[pos][mask][f], where pos is the current digit of a number (starting from the greater one), mask is the binary mask of used digits and f equals one if prefix of our current number is the same as in the number n. You can calculate the sum of suitable numbers from 1 to n using this DP. Then the answer is calc(r) - calc(l - 1).
I have a confusion. A prefix can be in the range of 64-bit integer. How can I use this big number as a state?
You don't need to use the number as a state. The position in this number is enough. To do some transactions you need to place the new digit in your number and recalculate DP. Ohh, the most important thing — to calculate the sum of numbers you need to calculate two DPs, one for the count of such numbers (this DP is auxiliary) and DP for the sum of such numbers (to calculate the answer).
Hey, why don't you need to keep track of if you have put something greater than 0, for cases like 000124 and k = 3, because you only turn on the 0-th bit if you had put something greater than zero before?
My solution calculates this DP independently for each length from 1 to |n| and says the sum of numbers of exactly such length. But I thought that I can calculate for all lengths at once because where you places leading zeroes, the count of these numbers will be right. The sum will be right also (because 0 doesn't contributes to the sum at all)
Oh nice, jeje I was calculating all at the same time, that's why mine is different. Thanks.
Sorry, I read that wrong.
I can find number of different integer from [l,r] using digit-dp but how to find sum of these integers?
say calculate for num = 78520193
iterate from left to right, say you are at position 3 (digit - > 5) right now, then how many times (say T) does 500000 in your answer?
it is simply number of ways you can form numbers < = 520193 which can found by DigitDP ( you also need to ignore if number of digits used are > k , for which you can use mask --> set the bit for the digit you included ) then this sum would be 500000 * T.
Now this value if repeated for 78520193, 68520193, 77520193... and so on , since prefix upto position 2 can also change , so for that make another dp table and do the same digitDP for this now.
Thank you very much :)
Probably DIGIT DP, however could not implement it ;(
I tried with digit dp too, couldn't define states.
I always try to make something recursive like answer(A, i) that is filling array A from 17 to 0 and i is the position where we can choose a value. Complexity would be 10^18, but if we make these optimizations complexity drops: If the number cannot be in the range [l,r] return 0; if it will always be in a range [l, r] ask the answer from another dp function.
the contest ended ?? it was scheduled to start now, did i miss something ?
Yes, the contest
I am having a hard time with Problem B, Please Help.
My code which works on every other online IDE under 0.01s is getting TLE on case 1 here. I have used GNU's policy based ordered tree in it. used G++ 17 to submit.
Here is my submission -- > 44858365
I tried tweaking things a bit, using int instead of ll. Nothing helped. This thing ruined my already not so good rank, had to rewrite a different solution. :(
This is undefined behaviour because you are doing something with an iterator that has been erased.
Yes, you are right, I actually figured this out later after I posted here for help.
Iterating while erasing should not be done this way either, because even x++ is invalid after calling erase. I read it here on SO.
Thanks anyway!
Use deque data structure , its pretty fast
Yes it is fast indeed.
Actually this question was pretty easily solvable without any RB tree like i used. I just wanted to try my hands on that special GNU Policy based DS.
After i failed to do that with gnu_pbds ordered set, i did that question using a simple vector and a map.
how to solve D?
The first booth we can't buy must supply the most expensive candies. So we can simulate this procedure. Calculate the current whole price and find the most expensive booth. Then we can compute how much we will spend before we buy the last candy in this booth. Then we subtract the cost and add the quantity.
Until None of candies can be bought.
We can use binary indexed trees or segment tree to compute the cost and the quantity.
D could be solved using SEGTREE descent in n * log(n) without any thought........... But if you observe one can write brute force solution also...that would also fit into time limit because of the fact that for any two numbers a,b ............. a%b <= (a + 1) / 2 its time complexity would also be n * log(n)
how can you say that a%b <= (b + 1) / 2 ?
iff a>b........one can varify that a%b can take values from 0 to a / 2 by taking few examples.
Sorry i still didn't get it. for ex- 15%8>(8+1)/2.
He said <=(a+1)/2, not (b+1)/2.
ohh he changed that now xD.
It was my mistake ....I edited it afterwards...Sorry for that..
Its .
15 mod 8 > 8 implies 7 > 8 which is wrong
Yes, it is wrong.
I just wanted to correct the jonsnow7's comment, where he mistakenly compared wrong values.
Can you please tell me how to do this using segtree descent ?
https://codeforces.net/contest/1073/submission/44861532 Refer to this solution for SEGTREE tree descent solution :)
I think there is a problem with modulo condition.
That’s why I spend about 30 minutes while others only spend 10 minutes solving the problem.XD
Can you please elaborate how can I use segment tree here(like what to keep in node and how to query)?
We can compute the cost and quantity in a interval by SEGTREE. This is my solution 44866016
44935386 What is wrong in my solution??
You are not re-initializing sum=0 in while loop .
I tried to use two pointer technique for problem C.
However I got a WA. Can somebody please help me in figuring out where I was wrong.
Idea:- Caluclate the position x and y based on the given string. Calculate the diff in x and y based on goal x and y. Now calculate diff between goal x and x and for goal y and y. Now if the diffs in each dimension are not divisible by 2 or the required characters needed are less than given in the string output -1. Otherwise use two pointer to find the shortest string length.
did you check if diff in x is divisible by 2 and y ?
because if both is you need 2 chars to cancel each others
for example if you have RUR and x=1 y=0 then it would be RLR
Yes if you check here lines 75-83 do this.
Idk then I was trying to do it with binary search but coding it was a bit hard
are you failing on test 5 like me(http://codeforces.net/contest/1073/submission/44891148) i also implemented using two pointer kind of thing.
in test 5 all 'R' are 24 and all 'L are 27 in number and final destination's x coordinate is -59 which is unachievable if we even turn all 'R' to 'L' which will give 51 'L' hence we can at max go to -51 in x direction isn'it test case no 5 is ->
100 URDLDDLLDDLDDDRRLLRRRLULLRRLUDUUDUULURRRDRRLLDRLLUUDLDRDLDDLDLLLULRURRUUDDLDRULRDRUDDDDDDULRDDRLRDDL -59 -1
r=24 l=27 d=32 u=17 please comment how it is possible
You can change any operation to any other operation. So you can even change U or D to L
Ooo srry my bad , thank you
I feel like D was much easier than C. Some people wasted too much time unsuccessfully solving C, while they could solve D instead.
I'm not sure, but I don't think there's a rule that difficulty(C) <= difficulty(D)... |-)
The problems aren't always sorted by difficulty in educational rounds, I think.
I figured out C easily and implemented it within 20 min, I had 1.1hrs to do D, but couldn't. :(
Dear anyone please try to hack my solution for D 44864411 Thanks :D
I did the pretty much same. :p
How to solve C ?
Binary Search for the answer. To check whether you can have a subsegment of length x as the answer iterate over all the subarrays of length x and then all you have to check is whether the difference between the expected position and the actual position is greater than the subarray length or not and also if the difference is less than the subarray length we need to check the parity of the difference between the 2 values.
in problem C, when I realized that I used binary search in wrong way, and it took a lot of time to correct my solution but too late. Im now feel a little regret about it, hmm. Hope these experiences will help me grow up in the future. Hope you guys have good rating after the contest <3<3<3
can someone tell me why I get so much dislike, i dont think that my comment is annoying people like this. and I also wonder why my contribution is a negative number (-4). why this happened to me, plz help me, (T-T)
can anyone give me a single reason why this solution give tle https://codeforces.net/contest/1073/submission/44874378 and when i change compiler to c++11 it give acc + almost all my friend list got acc with the same code and without fast input and this is my code acc https://codeforces.net/contest/1073/submission/44877617
Nothing strange, since the newer compiler provides better optimizations for your code, therefore better time.
so what
So, your code TLEs and shouldn't get AC ( tho you can get it AC by using static arrays instead of maps and maybe using integers instead of long long since it's not needed)
It seems to me like you didn't "change compiler to c++11" between the two submissions, both of them were submitted with GNU C++11. The difference is one of them uses fast input and
int
type, while the other one uses "slow" input andlong long
type. Obviously, the latter one will be slower. No surprises there.P.S. your solution is already sub-optimal because it runs in
O(n * logn)
time. Had you implemented the optimal solution (which runs inO(n)
time), then it wouldn't have mattered which types and what kind of input you used :)Look at this acc solution pls http://codeforces.net/contest/1073/submission/44877610
https://codeforces.net/blog/entry/62683?#comment-466975
How do you solve D? I thought of using 2 BITs, however the number of submissions indicates an alternate easier solution.
On each iteration you have some money and sum of remaining candies. Just buy as much of every candy as you can and then, when your remaining money will be less than sum of every candy left, just try to buy them one by one in O(n). Also maintain sorted candies to check if remaining T is enough to buy highest costing candy. If not no need for them and just skip until you have one that is less. During that decrease sum of all candies left.
Apparently T's decrease is logarithmic so you end up with O(n log(n)). There are possibilities to improve performance in many ways, but none of them are needed to pass the tests, sadly (I did some and now regretting the lost time in implementation).
How is decrease in T logarithmic?
Check the first part of the editorial for 438D — The Child and Sequence: http://codeforces.net/blog/entry/12513
I solved it with just 1 BIT. You try to buy 1 candy for every booth, if you can't, then you can binary search the position where sum of 1...i becomes greater than T, and you erase it from the bit (you update position i, with -value[i]) and keep doing that until you can buy 1 candy for all remaining booths. At the end, you had to do N Binary search which is O(N*ogN*logN) or O(N*LogN) if you use the trick of binary search on BIT. My submission
Yep, I had a similar idea! How did you keep track of the count of valid booths since you're erasing them from the BIT?
oh, you can use a variable, initially, you have remaining = N, every time you erase one, you do remaining--
or O(N*logN) if you use the trick of binary search on BIT
Could you please explain or give some resource about this trick ?
Of course, here the part of "Find index with given cumulative frequency"
Thanks.
Why, you set - value[i] to i instead of 0? Don't we need to neutralize/erase it?
Yes but remember when I first inserted the value I added value[i] so now I need to subtract that. Remember that BIT is sum of all values lower than i . If you update with 0 you are not doing anything.
Can someone please tell me how this O(n) solution TLEd on B? http://codeforces.net/contest/1073/submission/44854424
Your forgot to use your
fastread
: 44876642Yeah, that's how I got it to pass. But the input size is not that large. I usually don't fastread for this array size and have never faced this problem before. I guess I've learned my lesson about that!
"Input size is not that large", input parsing has the same time complexity as the solution itself (both
O(n)
), so (percentually speaking) it can't really get much "larger" than that.Maybe 'endl' (with flush?) issue? Try to change to "\n" (or '\n'). Reading 4e5 data, maybe use yours 'fastread'?
I have a
#define endl '\n'
in my template. Using fastread made it pass, but I have not had that problem before.Alternating cin and cout automatically flushes cout. So it's technically the same as using endl. cin.tie(NULL); separates cin from cout so that it won't flush it anymore. Therefore it's important to use it here.
Wow, this was the exact explanation I was looking for. Just changing the order of I/O made the same code AC. Thanks a lot!
http://codeforces.net/contest/1073/submission/44899490
i can't hack with Generator and i get invalid input can you help me
There can be two reasons for invalid input. 1. Make sure you have newline character at the end of the generator output. 2. Make sure the last integer or character or whatever variable of generator output is followed by new line character instead of a space i.e. run loop for n-1 numbers and print last number followed by new line character instead of space followed by newline character
Can anyone explain C in detail. What are we exactly doing after applying binary search on the length of a substring?
In C, we can see that if we do change a substring of size k, then it doesn't matter if we change 1 or k elements in the substring. An easier approach would be to change all of them.
Let's say that we're at (x, y) and we have to go to (a, b). The shortest way between the two points is the Manhattan distance between them. However, if your k is greater than this Manhattan distance, you might want to 'waste' some moves before you reach there. It is easy to see that the number of moves you 'waste' will always be even.
So, if we do have to change this k subsegment, we can do it only if we can travel the Manhattan distance, and waste some moves if any. More formally, you get k > = dist((a, b) , (x, y)) and (k)mod2 = (dist)mod2.
Another observation is that if you get a valid subsegment of size k, you can get it for k + 2 as well. However, we don't know about k - 2.
So, we would binary search over all the even sizes and odd sizes of k separately and pick the minimum. We can binary search as the function of whether k works or not is monotonic. Or in other words, it's of the form NN...NYY..Y.
can you please elaborate why binary search works here. i didn't get the last part.
The reason we can apply binary search on a sorted array is because of the property that if i > j = > A[i] > = A[j]. So, if we are searching for an element k, and it's lesser than the present index, it implies that it would be lesser than all the indices on the right, so we don't need to check there.
Similarly here, we can observe a similar property, which is that if we can find a suitable segment of size k, we can find it for all k + 2 * c, where c > = 0. Thus, we could check for a potential minimum on the left. This is because the number of moves we 'waste', will always be even.
On the other hand, if k it not suitable, it means that all k - 2 * c for all k / 2 > = c > = 0 will not be suitable, and thus we need to check on the right.
You could have a look at the Topcoder tutorial here for a better explanation.
Can someone explain it to me why the solution for E got WA on 7? My solution for E I know my solution will calculate wrongly in some big cases but I don't know why.I take mod everywhere. Sorry for my poor english. :)
Can any moderators look into this case? Thanks!
what's wrong with him ??
Maybe that is sunzhihong's clone :))
And DT_Kang too. Their codes are basically 98% the same.
Hmm :(
cheat :))
What are the hack cases on C?
What does this error mean?
How to correct the error?
After successfully generating the test data, print out one last endline character.
(This one is not required in manual hacking, yet mandatory for generator-based ones).
A very very nice observation in D of why brute force would pass: The outer loop won't execute more than log(t) times because after each loop, t becomes t%i where i is some number <= t and if i<=t, t%i can take values from 0 to t/2 (proof is easy :) )
log(t) times in place of log(n) times
Yup. Updated accordingly.
Can you tell the proof? I am only able to figure out by taking values.
Can anyone explain why this gave TLE for problem D: https://codeforces.net/contest/1073/submission/44873511
The complexity according to me is O(n * (log n)^2) which should have passed. Is it because of inefficient code?
What's special in test case 8 for F problem.Getting "Sum of paths in jury is larger than participant".Isn't it just the two farthest nodes from the respective 2 end nodes of the common vertices path?
How to solve F?
I'm very sorry of what I've said
Editorial?
Why is E easier than D and D is easier than C -_-
How to solve E?
It's a basic DP digit problem. Use a bitmask to save the used digits. That's all.
Can any one provide me with nice digit on dp blogs?
Thanks in advance
digit dp
Why E Wa on test8? I'm very confused.
Is the editorials published?
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
The solution of problem F is: use greedy thoughts to find the longest path in the tree. So, we will look for the first point of the common part as root, then dfs () from that root to find the other end
DP is also a good choice!
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Can anybody describe the solution of the problem G (Yet another LCP problem)?
Has editorials been published? If not, can anyone provide me solution to Problem D.