On Sep/07/2018 17:35 (Moscow time) Educational Codeforces Round 50 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 Vladimir vovuh Petrov, Roman Roms Glazov, Ivan BledDest Androsov, Maxim Neon Mescheryakov and me.
Good luck to all participants!
Our friends at Harbour.Space also have a message for you:
Hi Codeforces!
We are excited to announce our Work & Study Programme, geared towards diving into the worlds of Computer Science, Data Science, and Robotics, while kick starting a fulfilling paid internship with one of our industrial partners!
Required Education:
Degree in Robotics or Computer, Electrical, Mechanical Engineering or related disciplines
Qualifications and skills:
- Hands-on robotic programming
- Ideally experience within the automotive manufacturing sector
- Knowledge understanding of robot control interface with ancillary equipment
- Use of robot simulation packages
- Deep experience with all things robotic, from infrastructure-free autonomy, to ROS, computer vision, and machine learning
- Experience working with robot parts and components, developing robotics devices
- Ability to concurrently manage multiple diverse and often complex issues and / or projects at the nexus of software, sensors, and hardware
If you are interested in this opportunity, APPLY HERE!
Should you be selected, we will invite you to a series of interviews with admissions, and our industrial partners.
Our programmes are both fundamental and practical. Upon joining, you start working with professionals from admired technology, design and communications companies. You will have strong technical and academic support, alongside industrial experience. This is a unique opportunity to benefit from both worlds of education and industry, in one of the most innovative cities Western Europe has to offer.
Congratulations to the winners:
Rank | Competitor | Problems Solved | Penalty |
---|---|---|---|
1 | eddy1021 | 7 | 298 |
2 | bmerry | 7 | 301 |
3 | LYJabc | 7 | 547 |
4 | thjchph4trjnh | 7 | 551 |
5 | BigBag | 6 | 192 |
Congratulations to the best hackers:
Rank | Competitor | Hack Count |
---|---|---|
1 | halyavin | 240:-18 |
2 | greencis | 47:-3 |
3 | vinuthegr8 | 15 |
4 | antguz | 14 |
5 | cubercsl | 14:-9 |
And finally people who were the first to solve each problem:
Problem | Competitor | Penalty |
---|---|---|
A | xiaowuc1 | 0:01 |
B | TOSHINO_KYOKO | 0:06 |
C | cb_Adam | 0:07 |
D | BoolX | 0:08 |
E | bmerry | 0:24 |
F | rkm0959 | 0:10 |
G | apink | 0:28 |
UPD: Editorial is uploaded
Imagine a CF round everyday xD
I could get addicted...
Which would be kind of a good thing, if you asked me!
With a few more problemsetters, why not??
It would be awesome <3 <3
That would be great. Everyday codeforces.
3 continious contests in three days.
Finally an Educational Round after long time :P
What happens to my score if I hack my own solution which otherwise will pass tests?
You will have one point less
three consecutive contest in three days.
it is wonderfull! thank you CF for your contests!
Yes!I like it too.
10000000000 Upvote for me to beat tourist
Ok.
Take it.
1 downvote for you to beat worse XD
I'll be the rank 1 of this contest.
I'll be the rank 0 of this contest.
ppc_qjd will beat you.
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Wow! It's the golden jubilee educational codeforces round.
Half century of educational round.
50*
div3 is for retards, div2 for normal people, div1 for nerds and we even have div0 for tourist.
So what is the purpose of edu rounds? is not just a regular div2 round?
2 minutes to go!
I wasted one hour because if(!x%2) while it should be if(!(x%2)) yikes >_<
I feel that this time the problems have pretests which are strong enough. But I still think halyavin will hack everyone.
swap(C, D)
was not C digit dp? but it had too many cases to cover, ultimately I left it after wasting an hour :(
You can just generate all the possible numbers and store them, then binary search for the answer. Or use a data structure, if you dislike binary search.
how will that even work? like there will be too many such numbers isn't it?
Since we are working with 18 digits along with 1e18, I think their count will be:
(18C3)*(9^3)+(18C2)*(9^2)+(18C1)*(9^1)+1 = 607420. Which is not much.
I solved it using digit DP, but I think there are other ways to solve it also.
I hate geometric-observation based problems -_-
erm hi sorry, how does one do problem B? thanks in advance!
If you observe then you'll notice that:
let, x=max(n,m).
if k<x then there's no way.
if n,m both are odd then, ans=k when x is odd, else ans=k-2.
if n,m both are even then, ans=k when x is even, else ans=k-2.
if either one of n,m is odd and another is even then, ans=k-1.
How to solve C?? Got three damn TLE on it!!!
Using cin costed me a TLE submission for D :(
You can add
to optimize your program.
scanf & printf rock :D
Lol, one Div2's F is another Div2's C
And one Div2's D is another Div2's B XD
Got TLE in D for not using fast input/output T-T </3
you're my new idol
Using int costed me a WA submission for D :(
wasn't E just about finding intersection points or was there something more to it?
I mean ans=sum(length of segments)-sum(degree of intersection points)
where degree means its the intersection point for how many lines
Edit: ans=sum(integer points on segment)-sum(degree of intersection points)
No. not sum(length of segments) but number of integer points on the line
yeah sorry!!,
so it was sum(integer points of segments)-sum(degree of intersection points)..,right?
Yeah it is.
+ number of integer intersection
Interesting problems, thanks to authors!
Problem F: http://codeforces.net/contest/955/problem/C
Thanks for the link. It helped me a lot. Have you solved any similar problem? Please share if you have.
Hello, at problem A and B, the input data integer less than 10^18, why I occurred to the error about out of range by use long of Java(the max of long in java more than 9*10^18), why ??????? it make my rating so bad. please tell me .sadly!!!!!!!!!!!
How to solve F? How to solve G?
F: a number is elegent only if it is not a perfect power. It can be counted with inclusion-exclusion principle
So can we generate all powers from 1 to 106 and consider only powers of ≥ 3 and for powers of 2 we take square roots?
yes
G: build a reachability graph from each source to sink. Now, take all non-empty and non-full subsets of sources. If number of elements in any subset is equal to number of sinks reachable from any of the sources from these subset, then it is possible to build a scc containing only these sources and sinks and not any other. So, answer in this case is no. Otherwise answer is yes.
What do you mean by non-empty and non-full subsets of sources?
Any subset of sources that is neither empty nor full
Oh yeah. Sorry my bad.
Please correct me if I am wrong.
Let, S is the set of sources and s is a proper subset of it, i.e . Now, say number of sinks reachable from s is x. And also, |s| = x.
So it means if we arbitrarily choose sources and sinks, it may happen that we choose this subset of sources and those sinks, which will leave one or more sources
untouched and they will not be able to turn into non-source nodes.build connected component with some other sinks (or maybe not).Sorry if I am not clear. :|
yes, since the untouched nodes are not reachable from the subset with existing edges, this kind of assignment would keep them unreachable even after addition of new edges.
Make raund unrated. I think, it will be better. Because problem F is 90% similar to this problem.
P.s. What about author solution?
Sorry for my poor English
beside the type of the problem (Number Theory) i couldn't find any similarity between both problem.
Difference between solution for that C(36625920) and this F(42649710).
Can anybody give a neat idea about problem B?
If destination is (x,y), you can first go from (0,0) to the destination in min(abs(x),abs(y)) diagonal steps then max(abs(x),abs(y))-min(abs(x),abs(y)) straight steps, if this is > k, then the answer is -1. If the straight steps count is s, there are 2 cases for it:
1) it is even, so you can use it all as diagonals, then let the remaining steps to reach k is rem, if rem is even you can use them also as diagonals, and if it is odd: if it is 1 you can break one of the previous diagonals into 2 straight steps and you are done. But if it is >= 3, you can use rem-2 as diagonals and the remaining 2 as straight steps.
2) it is odd, you can use s-1 as diagonals and the remaining 1 as straight. if rem is even you use them all as diagonals. And if it is odd, you can change your last step to be diagonal, and use rem-1 as diagonals and the last 1 as straight.
Imagine the K steps as 2 arrays: X[] and Y[] consisting of -1, 0 and 1 only. The i-th step is represnted by (X[i],Y[i]). A step is diagonal if it doesn't have a 0 in it. Let initially X[] and Y[] be full of 0. We are sure we have n ones in X[] and m ones in Y[]. Since we want diagonal moves we can change an even number of zeroes in X[] and an even number of zeros in Y[] to 1 and -1 and the we will still arrive at (n, m). It can be seen that there are only 4 cases to consider, depending on the parities of (k — n) and (k — m).
Rejudge problem D with the Time Limit per test being 2000ms, so unfair that it wasn't declared that it needs fast in/out methods
UPD: okay i see that my knowledge at the time complexity is kinda trash, my apologies to everyone.
You are not the first and will be not the last to fail a problem due to slow input/output.
If slow output is allowed, then it will be much harder to distinguish n*lg^2(n) from n^2 for example.
From the problem's constraints 2 seconds won't be enough for n^2 solution
Some things are incredibly fast such as memmove(), which is used by vector::erase or insert even though they have complexity of O(N), thus making it possible to pass in 2 seconds with an O(N^2) solution.
I don't see a good reason to increase the TL while it can be passed in 1/5 of the time limit with a "plainly fast" I/O, risking passes of "bad time complexity" solutions. Also, optimizing your code is also a part of the contest.
A scared me at first
Seeing all the comments, I wonder if I'm the only one doing this contest without any déjà vu of past problems at all? :o
Don't worry, we didn't have any doubt in each problems originality as well :D
Hope that the next round can be set up sooner, with better statements of the problems.
https://codeforces.net/contest/950/problem/B
Today's problem D.
The round should go unrated.
This Solution for D got WA, i tried this test case :
3
12 13 14
2
13 26
i want to output 2 (turn the first array into the second one), am i right ? if so, how to do this ?
any help appreciated :).
You cannot sort the array, it will change the order of the sum of subarrays and the answer to your test case is 1.
Ans should be 1
A will be converted to [39]
and B also to [39]
there is no other possible way.
As you cannot change the order of elements in the array
that's all !
i think i have to sort the elements, i don't no why i did this assumption T_T
anyway, thanks guys.
Div 2 , problem D is same as https://codeforces.net/contest/950/problem/B .
and Div 2 , problem F is similar to http://codeforces.net/contest/955/problem/C .
The round should go unrated.
This is educational Round,The purpose of the education problem is only to expose the participants to specific algorithms or topics,so having the same idea is just fine,originality isn't a specific requirement but ofcourse it's always better to have original problems
42640437
Why double fails int the problem A ?
Floating-point types are not magic types that can represent every numbers — no matter how big they are — 100% correctly.
double
can only hold up to around 15 digits, and afterwards they will have errors.Can you please explain why this submission(https://codeforces.net/contest/1036/submission/42633251) is getting WA, I know there is a precision problem of double type variable. But I need explanation.
Double can't accurately store such large numbers, meaning 1018 - 1 when converted to double becomes 1018 (as i think double always rounds up. Correct me if I'm wrong) and , but the answer is .
When it takes dreamoon 20 seconds to read A,understand it and code it(excluding that he never went back to check if B got Ac or not)
He maybe stores problem solutions!
I submit A about 3 min after contest start. But the connection of the Internet is break and I don't notice it immediately until I submit B...
Above is what thing happen during contest (>__<)
hope the very next contest will coming soon
I want to apologize to all who were affected by such a bad tests in the problem A. For one day before the round I thought "Hmm, this will be good idea, if I will give queries in the problem B, then there would not so many hacks!". I made it. But I don't even thought about the same enhancement in the problem A. This was very stupid mistake. I'm really sorry >_<
I made one look at B tests and decided to skip hacking this problem.
So precisely now we require systests on Problem B only
There is no succesful hacks for this problem. So no additional tests for systests.
HEIL HALYAVIN
How to solve C instead of precomputing?
Digit DP
use combinatorics. I dont understand what idea with DP. We calculate answer for some x from 1 to x. Then answer is calc(r)-calc(l-1). For calculate answer we look digits of number x from left to right and try put digits from 0 to d[i] — 1 (there d[i] digit of number on position i) because we want build another number with same prefix until position i-1 and in this case if we put digits less than d[i] to position i then our
"new number" will be less than number x and we can put any digits to remain part after we add to answer for every "putted" digit C(n,m)...
why this code got AC
https://codeforces.net/contest/1036/submission/42654776
while this one got WA
https://codeforces.net/contest/1036/submission/42633090
it is the same logic I think .
Doubles become inaccurate after about 15 digits. If you wanted to use doubles you can use BigDecimal in Java for more precision!
Ok
thank you a lot .
it is awesome,why my solution used long get wr(http://codeforces.net/contest/1036/submission/42622516 ),but you get right
halyavin hacked my submission 42638507. I resubmited the same solution 42655238 and it was accepted. Is something wrong?
Your new submission was checked only on original test cases ( they do not include the hack test cases used by people to hack other's codes) that is why your new submission got accepted
oh damn :( Though there were a hope for me
I don't know if it's glitch or not. But eddy1021 D's solution was hacked but still he is in the first position and his solution stands accepted.
Screenshots:
https://ibb.co/iV22N9
https://ibb.co/cT95aU
https://ibb.co/fKfYUp
Hello, everybody! I used unordered_map on problem D. And I got TLE on the System Test. But I changed it into map after contest, and it got accepted. I thought unordered_map runs faster than regular map. How can I be sure to use which one? Please, Somebody explain it. Thank you.
average case of unordered_map is O(1). But, worst case is O(n). On the other hand, map gurantees O(logn) everytime.
we can make it 10 times faster than map
How to solve C by using digit DP?
Here is my solution using digit DP 42675923, it may help you. There are quite a lot of cases to take care of.
The main idea is that for each interval
[L, R]
the answer isF(R) - F(L - 1)
. WhereF(x)
equals the number of classy integers from 0 to x.How to you calculate
F(x)
? Just using Dynamic Programming.For a number x, the DP looks something like this:
dp[i][j][k][0]
= number of integers less than x that arei
digits long, end inj
and they havek
digits bigger than 0.dp[i][j][k][1]
= number of integers equal to x that arei
digits long, end inj
and they havek
digits bigger than 0.j is going to be between
0..9
and k in the range from0..3
, because a classy number contains no more than 3 non-zero digits.Problem F:how to calculate fast enough?
Binary search.
Can anyone tell me why 42622172 failed and 42624685 passed?
double
is not enough to store 18 digits without errors.Oh, Thanks :)
![ ]()
system testing has been done actually,now it's just a coverup.
systesting started !!!!
hoooray !
Editorial?
educational rounds are very good:good problems, hacking phase and ...
but they have one disadvantage: system testing start very late!!!
Someone said that this round should go unrated, is it true?
Click here!
Or the system test just start very late?
In problem E is this a valid input
1
11 11 11 11
No, because A (first point on line) will not be equal B (second point in line), this is mentioned in the problem statement.
After system-testing This is my most valuable one-twentieth second since I first joined Codeforces :D
Submission ID: 42637102
I don't get it :D
The time limit of C is 3s, and my solution was a bruteforce one which I implemented (quite) poorly.
If fluctuated a bit more, my source code might get TLE :D
Can you explain me your brute force approach?
The concept is, we'll add all classy number into one set as preprocessing.
The number only has at most 18 digits (except for 1018, but since it's the only classy number with 19 digits, we'll deal with that exclusively).
For simplicity, let's initialize a string S of "000000000000000000", which resembles number 0. Obviously this is a classy number.
Let's iterate all (i, j, k) triplets (1 ≤ i, j, k ≤ 9), and for each triplet, iterate all (x, y, z) triplets (0 ≤ x, y, z < 18).
With each pair of triplets: change Sx to i, Sy to j, Sz to k, add the number resembled by the new string to the set. Remember to reset the string before next iteration.
As you can see, I gave no criteria of i, j, k or x, y, z being pairwise distinct, therefore, we can be sure to generate all valid classy numbers without dropping out any.
After preprocessing, for each test case, we can handle easily by binary searching the set (as in my calculation, the set's size won't surpass 6 millions, so no worries).
That's quite some bruteforce but the only thing that matters is your solution passed.
Yeah, actually what I've just said is the optimized form of my solution. My original one kept all numbers as strings (I was lazy :D ), and you get how consuming in both time and memory that was ;)
While opening your code I saw the Trie keyword and was wondering how Trie DS was used in this problem but that was just a map DS. :-) Generating numbers using recursion is much much faster as compared to string method, my solution passed in 108ms. Now just trying to solve it using DP. Hints will be helpful.
Nah, the "Trie" name was a dead joke used in Competitive Programming Community's Discord. No real trie involved :D
I just read problem E.. Is it a direct 2d segment tree problem ? Or I am just over simplifying it ?
Or you overdid it somehow.
I solved it with bruteforce and some math observations :D
I was mistakenly caught in education round 50 rated for [div 2] for coincidence code with GT_18 on question 1036A. GT_18 is my senior and I used his snippets available at https://github.com/govinda18/Sumblime-snippets. I think that's why the system caught me for coincidence of code and I did not violate any rules. I hope that I will be rated for this contest.
Even I used code snippet for E from code book of One of my friend And skipping someone's code for a question in which we just need to print ceil(k / n) is unfair.
And can you publish the analysis? (or throw a link to it)
For problem E, any hint on how to get the count of integer coordinates that are part of more than one line along with how many lines they are part of?
I dealt with that using something like
map<pair<int, int>, set<int>>
.The
pair<int, int>
is the point's coordinates, while theset<int>
stores the IDs of the lines which include that point.So, to get the count of the lines one point is part of, I'll get the size of the set mapped into that point's coordinates pair.
I thought also about literally storing every integer point that appeared on a line but thought it won't fit the constraints (I misread them).
But suppose a test with 1000 vertical lines each with ymin and ymax = -10^6 and 10^6 (the lines for example are: x=0, x=1, x=2, ...). Isn't storing 2e9 points two much?
EDIT: Or you will store those which contribute to more than one line only?
I won't store all of them. You know, storing points that lie strictly on one segment only is useless.
Therefore, I'll do a O(n2) brute force to find all possible intercept points of a pair of distinct segments (if such point exists), and for each point found, the set mapped with that point will get inserted two IDs of the two segments intersected on that exact point.
Yes this is possible as there are 1000 lines only, thanks a lot.
My code for ques 1036B was caught matching with eight different user i think that occurs due to my working on ideone as i was not aware that this easily code can be taken from ideone also adityasr try to copy my code for ques C but me and him both end up with TLE on test 23,there is very strange thing in his activities that his every code varry in coding style and for especially ques C firstly he was writting a totally different code and instantly changes to my code and you can also see his past record his many contests been cancelled. I gave this contest with full honesty and dedication,please update my rating and make this contest worth giving for me.
This should be a lesson for you. Be careful next time.
Actually, the issues with Ideone has been warned in the Codeforces rules (if I remembered correctly), so in technical views, this isn't something too unfair.
I really liked problem F!
(except for the fact that this is 955C - Sad powers and it is mine, lol)
A Div2C problem become problem F in an Educational Round
Is that Grape's D2C is too difficult or Educational's problem F is too easy? :thinking:
Both.
Actually, funnily enough, our problem was inspired by another problem but that one came from project euler)
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).