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 Ajosteen Glazov, Ivan BledDest Androsov, Maxim Ne0n25 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.

please make it easy like today’s contest

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.

Bullshit. I'd rather practice falun dafa.

## I'll be the rank 0 of this contest.

djp_cqq will beat you.

I like edu round, I am going to turn light blue tonight!:)

Auto comment: topic has been updated by PikMike (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 -_-

Why? Listen Andrey Stankevich

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!!!

By using "Digit Dp"

Using cin costed me a TLE submission for D :(

And wasting my over one hour penalty too

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

I can't send messeges for you. Can I have your email ?

Got TLE in D for not using fast input/output T-T </3

you're my new idol

Can someone point out where was I going wrong in Div2G 42635807. I was getting WA on test case 9 repetedly, though I think my logic was sound. Wasted 1hr trying to debug it.

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.com/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 10

^{6}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-emptyandnon-fullsubsets 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,

Sis the set of sources andsis a proper subset of it, i.e . Now, say number of sinks reachable fromsisx. 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.

Thanks tengra.

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.com/contest/950/problem/B

Today's problem D.

The round should go unrated.

This Solution for D got WA, i tried this test case :

input3

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

You actually can't sort elements.

anyway, thanks guys.

Div 2 , problem D is same as https://codeforces.com/contest/950/problem/B .

and Div 2 , problem F is similar to http://codeforces.com/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

doublefails int the problemA?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.i'll never use it again

:"(I had to use binary search to get rid of that. Damn I was too scared to see an obvious solution failing :(

Can you please explain why this submission(https://codeforces.com/contest/1036/submission/42633251) is getting WA, I know there is a precision problem of double type variable. But I need explanation.

here is how the compiler deal with the test case 6 ... i know that the double not accurate with the precision but when i got WA i thought that my idea was wrong.

anyway, can any body explain how the double and long double works ?

Double can't accurately store such large numbers, meaning 10

^{18}- 1 when converted to double becomes 10^{18}(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 DPuse 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)...

3 true storys ..

1- the best who solve educational rounds is eddy1021.

2- the best hacker is halyavin.

3- the best who makes jokes and comments is

MEsorry :Pwhy this code got AC

https://codeforces.com/contest/1036/submission/42654776

while this one got WA

https://codeforces.com/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.com/contest/1036/submission/42622516 ),but you get right

How to solve F? Can anyone explain the approach?

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

He actually submitted D twice during the contest. So the first one got hacked.

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 is`F(R) - F(L - 1)`

. Where`F(x)`

equals the number ofclassyintegers 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 integersless than xthat are`i`

digits long, end in`j`

and they have`k`

digits bigger than 0.`dp[i][j][k][1]`

= number of integersequal to xthat are`i`

digits long, end in`j`

and they have`k`

digits bigger than 0.jis going to be between`0..9`

andkin the range from`0..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?

This is my first time to join.I feel...bula~bula~,haha!

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.

System Test has been started.

After system-testingThis is my most valuable one-twentieth second since I first joined Codeforces :DSubmission 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 10

^{18}, but since it's the only classy number with 19 digits, we'll deal with that exclusively).For simplicity, let's initialize a string

Sof "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

S_{x}toi,S_{y}toj,S_{z}tok, 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,korx,y,zbeing 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

optimizedform 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

deadjoke used in Competitive Programming Community's Discord. No real trie involved :DI 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

hhhh true ... I forgot my #1 rule in solving problems :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.Please add editorials.

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 the`set<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(n^{2}) 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 - Грустные степени and it is mine, lol)

A Div2C problem become problem F in an Educational RoundIs that Grape's D2C is too difficult or Educational's problem F is too easy?:thinking:Both.

fyiActually, funnily enough, our problem was inspired by another problem but that one came from project euler)

Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).