By PikMike, history, 6 months ago, translation, ,

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
497 successful hacks and 440 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A xiaowuc1 0:01
B TOSHINO_KYOKO 0:06
D BoolX 0:08
E bmerry 0:24
F rkm0959 0:10
G apink 0:28

•
• +131
•

 » 6 months ago, # |   +64 Imagine a CF round everyday xD
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 I could get addicted...Which would be kind of a good thing, if you asked me!
•  » » 6 months ago, # ^ |   +3 With a few more problemsetters, why not??
•  » » 6 months ago, # ^ |   +2 It would be awesome <3 <3
•  » » 6 months ago, # ^ |   0 That would be great. Everyday codeforces.
 » 6 months ago, # |   0 3 continious contests in three days.
 » 6 months ago, # |   -12 Finally an Educational Round after long time :P
 » 6 months ago, # |   0 What happens to my score if I hack my own solution which otherwise will pass tests?
•  » » 6 months ago, # ^ |   0 You will have one point less
 » 6 months ago, # |   +30 three consecutive contest in three days.it is wonderfull! thank you CF for your contests!
•  » » 6 months ago, # ^ |   +3 Yes!I like it too.
 » 6 months ago, # | ← Rev. 2 →   0 please make it easy like today’s contest
 » 6 months ago, # |   -78 10000000000 Upvote for me to beat tourist
•  » » 6 months ago, # ^ |   +16 Ok.Take it.
•  » » 6 months ago, # ^ |   +8 1 downvote for you to beat worse XD
»
6 months ago, # |
-49

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

•  » » 6 months ago, # ^ |   0 Bullshit. I'd rather practice falun dafa.
• »
»
6 months ago, # ^ |
+3

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

•  » » 6 months ago, # ^ |   0 djp_cqq will beat you.
 » 6 months ago, # |   0 I like edu round, I am going to turn light blue tonight!:)
 » 6 months ago, # |   -7 Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).
 » 6 months ago, # |   +4 Wow! It's the golden jubilee educational codeforces round.
 » 6 months ago, # |   0 Half century of educational round.50*
 » 6 months ago, # |   -104 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?
 » 6 months ago, # |   +4 2 minutes to go!
 » 6 months ago, # |   +4 I wasted one hour because if(!x%2) while it should be if(!(x%2)) yikes >_<
 » 6 months ago, # |   +20 I feel that this time the problems have pretests which are strong enough. But I still think halyavin will hack everyone.
 » 6 months ago, # |   +59 swap(C, D)
•  » » 6 months ago, # ^ |   +3 was not C digit dp? but it had too many cases to cover, ultimately I left it after wasting an hour :(
•  » » » 6 months ago, # ^ |   +20 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.
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   0 how will that even work? like there will be too many such numbers isn't it?
•  » » » » » 6 months ago, # ^ | ← Rev. 2 →   +4 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.
•  » » » 6 months ago, # ^ |   0 I solved it using digit DP, but I think there are other ways to solve it also.
 » 6 months ago, # |   +23 I hate geometric-observation based problems -_-
•  » » 6 months ago, # ^ |   0 Why? Listen Andrey Stankevich
 » 6 months ago, # |   +4 erm hi sorry, how does one do problem B? thanks in advance!
•  » » 6 months ago, # ^ | ← Rev. 2 →   +4 If you observe then you'll notice that: let, x=max(n,m). if k
 » 6 months ago, # |   0 How to solve C?? Got three damn TLE on it!!!
•  » » 6 months ago, # ^ |   0 By using "Digit Dp"
 » 6 months ago, # |   +16 Using cin costed me a TLE submission for D :(
•  » » 6 months ago, # ^ |   0 And wasting my over one hour penalty too
•  » » 6 months ago, # ^ |   0 You can add std::ios::sync_with_stdio(0); std::cin.tie(0); to optimize your program.
•  » » » 6 months ago, # ^ |   +5 scanf & printf rock :D
 » 6 months ago, # |   +37 Lol, one Div2's F is another Div2's C
•  » » 6 months ago, # ^ |   +18 And one Div2's D is another Div2's B XD
•  » » 6 months ago, # ^ |   -14 I can't send messeges for you. Can I have your email ?
 » 6 months ago, # |   +14 Got TLE in D for not using fast input/output T-T
•  » » 6 months ago, # ^ |   +18 #define this_is_so_sad_alexa_play_despacito_2 ios_base::sync_with_stdio(0); cin.tie(0); you're my new idol
 » 6 months ago, # |   0 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.
 » 6 months ago, # |   -16 Using int costed me a WA submission for D :(
 » 6 months ago, # | ← Rev. 2 →   0 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 linesEdit: ans=sum(integer points on segment)-sum(degree of intersection points)
•  » » 6 months ago, # ^ |   +3 No. not sum(length of segments) but number of integer points on the line
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 yeah sorry!!,so it was sum(integer points of segments)-sum(degree of intersection points)..,right?
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   0 Yeah it is.
•  » » » » » 6 months ago, # ^ | ← Rev. 2 →   +5  +  number of integer intersection
 » 6 months ago, # |   +13 Interesting problems, thanks to authors!
 » 6 months ago, # |   +32
•  » » 5 months ago, # ^ |   0 Thanks for the link. It helped me a lot. Have you solved any similar problem? Please share if you have.
 » 6 months ago, # | ← Rev. 7 →   0 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!!!!!!!!!!!
 » 6 months ago, # |   +5 How to solve F? How to solve G?
•  » » 6 months ago, # ^ |   +5 F: a number is elegent only if it is not a perfect power. It can be counted with inclusion-exclusion principle
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +5 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?
•  » » » » 6 months ago, # ^ |   +5 yes
•  » » 6 months ago, # ^ |   0 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.
•  » » » 6 months ago, # ^ |   -6 What do you mean by non-empty and non-full subsets of sources?
•  » » » » 6 months ago, # ^ |   0 Any subset of sources that is neither empty nor full
•  » » » » » 6 months ago, # ^ | ← Rev. 3 →   0 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. :|
•  » » » » » » 6 months ago, # ^ |   0 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.
•  » » » » » » » 6 months ago, # ^ |   0 Thanks tengra.
 » 6 months ago, # |   -44 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
•  » » 6 months ago, # ^ |   -13 beside the type of the problem (Number Theory) i couldn't find any similarity between both problem.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +55 Difference between solution for that C(36625920) and this F(42649710).
 » 6 months ago, # |   0 Can anybody give a neat idea about problem B?
•  » » 6 months ago, # ^ |   +6 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.
•  » » 6 months ago, # ^ |   0 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).
 » 6 months ago, # | ← Rev. 2 →   -23 Rejudge problem D with the Time Limit per test being 2000ms, so unfair that it wasn't declared that it needs fast in/out methodsUPD: okay i see that my knowledge at the time complexity is kinda trash, my apologies to everyone.
•  » » 6 months ago, # ^ |   +26 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.
•  » » » 6 months ago, # ^ |   -18 From the problem's constraints 2 seconds won't be enough for n^2 solution
•  » » » » 6 months ago, # ^ |   +22 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.
 » 6 months ago, # |   +33 A scared me at first
 » 6 months ago, # |   +40 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
•  » » 6 months ago, # ^ |   +15 Don't worry, we didn't have any doubt in each problems originality as well :D
 » 6 months ago, # | ← Rev. 2 →   +5 Hope that the next round can be set up sooner, with better statements of the problems.
 » 6 months ago, # |   -9 https://codeforces.com/contest/950/problem/BToday's problem D.The round should go unrated.
 » 6 months ago, # |   -8 This Solution for D got WA, i tried this test case : input 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 :).
•  » » 6 months ago, # ^ |   +3 You cannot sort the array, it will change the order of the sum of subarrays and the answer to your test case is 1.
•  » » 6 months ago, # ^ | ← Rev. 2 →   +1 Ans should be 1A 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
•  » » 6 months ago, # ^ |   +1 that's all ! i think i have to sort the elements, i don't no why i did this assumption T_T
•  » » » 6 months ago, # ^ |   0 You actually can't sort elements.
•  » » 6 months ago, # ^ |   +1 anyway, thanks guys.
 » 6 months ago, # |   +24 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.
•  » » 6 months ago, # ^ |   0 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
 » 6 months ago, # |   +9 42640437Why double fails int the problem A ?
•  » » 6 months ago, # ^ |   +11 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.
•  » » » 6 months ago, # ^ |   0 i'll never use it again :"(
•  » » 6 months ago, # ^ |   0 I had to use binary search to get rid of that. Damn I was too scared to see an obvious solution failing :(
 » 6 months ago, # |   0 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.
•  » » 6 months ago, # ^ |   -8 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 ?
•  » » 6 months ago, # ^ |   +4 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 .
 » 6 months ago, # | ← Rev. 2 →   +28 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)
•  » » 6 months ago, # ^ |   +3 He maybe stores problem solutions!
•  » » 5 months ago, # ^ |   +11 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 (>__<)
 » 6 months ago, # |   +12 hope the very next contest will coming soon
 » 6 months ago, # |   +38 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 >_<
•  » » 6 months ago, # ^ |   +18 I made one look at B tests and decided to skip hacking this problem.
•  » » » 6 months ago, # ^ |   +2 So precisely now we require systests on Problem B only
•  » » » » 6 months ago, # ^ |   +3 There is no succesful hacks for this problem. So no additional tests for systests.
•  » » » » » 6 months ago, # ^ |   +9 HEIL HALYAVIN
 » 6 months ago, # |   0 How to solve C instead of precomputing?
•  » » 6 months ago, # ^ |   +4 Digit DP
•  » » 6 months ago, # ^ |   0 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)...
 » 6 months ago, # | ← Rev. 3 →   -28 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 ME sorry :P
 » 6 months ago, # |   0 why this code got AC https://codeforces.com/contest/1036/submission/42654776while this one got WAhttps://codeforces.com/contest/1036/submission/42633090it is the same logic I think .
•  » » 6 months ago, # ^ |   +1 Doubles become inaccurate after about 15 digits. If you wanted to use doubles you can use BigDecimal in Java for more precision!
•  » » » 6 months ago, # ^ |   +3 Ok thank you a lot .
•  » » 6 months ago, # ^ | ← Rev. 4 →   0 it is awesome,why my solution used long get wr(http://codeforces.com/contest/1036/submission/42622516 ),but you get right
 » 6 months ago, # |   0 How to solve F? Can anyone explain the approach?
 » 6 months ago, # |   0 halyavin hacked my submission 42638507. I resubmited the same solution 42655238 and it was accepted. Is something wrong?
•  » » 6 months ago, # ^ |   +2 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
•  » » » 6 months ago, # ^ |   0 oh damn :( Though there were a hope for me
 » 6 months ago, # | ← Rev. 2 →   0 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/iV22N9https://ibb.co/cT95aUhttps://ibb.co/fKfYUp
•  » » 6 months ago, # ^ |   0 He actually submitted D twice during the contest. So the first one got hacked.
 » 6 months ago, # |   0 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.
•  » » 6 months ago, # ^ |   +1 average case of unordered_map is O(1). But, worst case is O(n). On the other hand, map gurantees O(logn) everytime.
•  » » » 5 months ago, # ^ |   0
 » 6 months ago, # |   0 How to solve C by using digit DP?
•  » » 6 months ago, # ^ |   0 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 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 are i digits long, end in j and they have k digits bigger than 0.dp[i][j][k][1] = number of integers equal to x that are i digits long, end in j and they have k digits bigger than 0.j is going to be between 0..9 and k in the range from 0..3, because a classy number contains no more than 3 non-zero digits.
 » 6 months ago, # | ← Rev. 2 →   0 Problem F:how to calculate fast enough？
•  » » 6 months ago, # ^ |   0 Binary search.
 » 6 months ago, # |   -6 Can anyone tell me why 42622172 failed and 42624685 passed?
•  » » 6 months ago, # ^ |   +3 double is not enough to store 18 digits without errors.
•  » » » 6 months ago, # ^ |   0 Oh, Thanks :)
 » 6 months ago, # |   +63 ![ ]()
•  » » 6 months ago, # ^ |   +7
•  » » » 6 months ago, # ^ |   0 system testing has been done actually,now it's just a coverup.
•  » » » 6 months ago, # ^ |   0 systesting started !!!!hoooray !
 » 6 months ago, # |   +8 Editorial?
 » 6 months ago, # | ← Rev. 2 →   +25 educational rounds are very good:good problems, hacking phase and ...but they have one disadvantage: system testing start very late!!!
•  » » 6 months ago, # ^ |   0 Someone said that this round should go unrated, is it true?Click here!Or the system test just start very late?
•  » » » 6 months ago, # ^ |   +19
 » 6 months ago, # |   0 This is my first time to join.I feel...bula~bula~,haha!
 » 6 months ago, # |   0 In problem E is this a valid input111 11 11 11
•  » » 5 months ago, # ^ |   0 No, because A (first point on line) will not be equal B (second point in line), this is mentioned in the problem statement.
 » 6 months ago, # | ← Rev. 4 →   0 System Test has been started.
 » 6 months ago, # |   +8 After system-testing This is my most valuable one-twentieth second since I first joined Codeforces :DSubmission ID: 42637102
•  » » 6 months ago, # ^ |   0 I don't get it :D
•  » » » 6 months ago, # ^ |   +1 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
•  » » » » 6 months ago, # ^ |   0 Can you explain me your brute force approach?
•  » » » » » 6 months ago, # ^ |   +1 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).
•  » » » » » » 6 months ago, # ^ |   0 That's quite some bruteforce but the only thing that matters is your solution passed.
•  » » » » » » » 6 months ago, # ^ |   +1 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 ;)
•  » » » » » » » » 6 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » » » » » 6 months ago, # ^ |   0 Nah, the "Trie" name was a dead joke used in Competitive Programming Community's Discord. No real trie involved :D
 » 6 months ago, # | ← Rev. 3 →   0 I just read problem E.. Is it a direct 2d segment tree problem ? Or I am just over simplifying it ?
•  » » 6 months ago, # ^ |   +6 Or you overdid it somehow.I solved it with bruteforce and some math observations :D
•  » » » 6 months ago, # ^ |   0 hhhh true ... I forgot my #1 rule in solving problems :D
 » 6 months ago, # |   0 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.
•  » » 6 months ago, # ^ |   0 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.
 » 6 months ago, # |   +3 And can you publish the analysis? (or throw a link to it)
 » 6 months ago, # |   0 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?
•  » » 6 months ago, # ^ | ← Rev. 2 →   +3 I dealt with that using something like map, set>. The pair is the point's coordinates, while the set 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.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +5 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?
•  » » » » 6 months ago, # ^ |   +3 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.
•  » » » » » 6 months ago, # ^ |   0 Yes this is possible as there are 1000 lines only, thanks a lot.
 » 6 months ago, # |   -8 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.
•  » » 6 months ago, # ^ |   +8 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.
 » 6 months ago, # |   +6 I really liked problem F!(except for the fact that this is 955C - Sad powers and it is mine, lol)
•  » » 6 months ago, # ^ |   +21 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:
•  » » » 6 months ago, # ^ |   +7 Both.
•  » » 6 months ago, # ^ |   +5 fyi
•  » » 6 months ago, # ^ |   +5 Actually, funnily enough, our problem was inspired by another problem but that one came from project euler)
 » 6 months ago, # |   0 Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).
 » 6 months ago, # |   0 Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).