Educational Codeforces Round 50 [Rated for Div. 2]
By awoo, history, 6 years ago, translation, In English

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

  • Vote: I like it
  • +131
  • Vote: I do not like it

Comments Comments (154)
| Write comment?
»
6 years ago, # |
  Vote: I like it +64 Vote: I do not like it

Imagine a CF round everyday xD

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

3 continious contests in three days.

→ Reply
»
6 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Finally an Educational Round after long time :P

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What happens to my score if I hack my own solution which otherwise will pass tests?

→ Reply
»
6 years ago, # |
  Vote: I like it +30 Vote: I do not like it

three consecutive contest in three days.

it is wonderfull! thank you CF for your contests!

→ Reply
»
6 years ago, # |
  Vote: I like it -78 Vote: I do not like it

10000000000 Upvote for me to beat tourist

→ Reply
»
6 years ago, # |
  Vote: I like it -49 Vote: I do not like it

I'll be the rank 1 of this contest.

→ Reply
»
6 years ago, # |
  Vote: I like it -7 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Wow! It's the golden jubilee educational codeforces round.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Half century of educational round.

50*

→ Reply
»
6 years ago, # |
  Vote: I like it -104 Vote: I do not like it

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?

→ Reply
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

2 minutes to go!

→ Reply
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

I wasted one hour because if(!x%2) while it should be if(!(x%2)) yikes >_<

→ Reply
»
6 years ago, # |
  Vote: I like it +20 Vote: I do not like it

I feel that this time the problems have pretests which are strong enough. But I still think halyavin will hack everyone.

→ Reply
»
6 years ago, # |
  Vote: I like it +59 Vote: I do not like it

swap(C, D)

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    was not C digit dp? but it had too many cases to cover, ultimately I left it after wasting an hour :(

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        how will that even work? like there will be too many such numbers isn't it?

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          ← Rev. 2   Vote: I like it +4 Vote: I do not like 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.

          → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I solved it using digit DP, but I think there are other ways to solve it also.

      → Reply
»
6 years ago, # |
  Vote: I like it +23 Vote: I do not like it

I hate geometric-observation based problems -_-

→ Reply
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

erm hi sorry, how does one do problem B? thanks in advance!

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?? Got three damn TLE on it!!!

→ Reply
»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Using cin costed me a TLE submission for D :(

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can add 

    std::ios::sync_with_stdio(0);
std::cin.tie(0);

    to optimize your program.

    → Reply
»
6 years ago, # |
  Vote: I like it +37 Vote: I do not like it

Lol, one Div2's F is another Div2's C

→ Reply
»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it 
    #define this_is_so_sad_alexa_play_despacito_2 ios_base::sync_with_stdio(0); cin.tie(0);

    you're my new idol

    → Reply
»
6 years ago, # |
  Vote: I like it -16 Vote: I do not like it

Using int costed me a WA submission for D :(

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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)

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    No. not sum(length of segments) but number of integer points on the line

    → Reply
»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Interesting problems, thanks to authors!

→ Reply
»
6 years ago, # |
  Vote: I like it +32 Vote: I do not like it

Problem F: http://mirror.codeforces.com/contest/955/problem/C

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for the link. It helped me a lot. Have you solved any similar problem? Please share if you have.

    → Reply
»
6 years ago, # |
← Rev. 7   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve F? How to solve G?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    F: a number is elegent only if it is not a perfect power. It can be counted with inclusion-exclusion principle

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      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?

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      What do you mean by non-empty and non-full subsets of sources?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Any subset of sources that is neither empty nor full

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          ← Rev. 3   Vote: I like it 0 Vote: I do not like it

          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. :|

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
»
6 years ago, # |
  Vote: I like it -44 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody give a neat idea about problem B?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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).

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -23 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -18 Vote: I do not like it

      From the problem's constraints 2 seconds won't be enough for n^2 solution

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +22 Vote: I do not like it

        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.

        → Reply
»
6 years ago, # |
  Vote: I like it +33 Vote: I do not like it

A scared me at first

→ Reply
»
6 years ago, # |
  Vote: I like it +40 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Don't worry, we didn't have any doubt in each problems originality as well :D

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Hope that the next round can be set up sooner, with better statements of the problems.

→ Reply
»
6 years ago, # |
  Vote: I like it -9 Vote: I do not like it

https://mirror.codeforces.com/contest/950/problem/B

Today's problem D.

The round should go unrated.

→ Reply
»
6 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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 :).

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You cannot sort the array, it will change the order of the sum of subarrays and the answer to your test case is 1.

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    that's all !

    i think i have to sort the elements, i don't no why i did this assumption T_T

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    anyway, thanks guys.

    → Reply
»
6 years ago, # |
  Vote: I like it +24 Vote: I do not like it

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

and Div 2 , problem F is similar to http://mirror.codeforces.com/contest/955/problem/C .

The round should go unrated.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

42640437

Why double fails int the problem A ?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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 .

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +28 Vote: I do not like it

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)

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    He maybe stores problem solutions!

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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 (>__<)

    → Reply
»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

hope the very next contest will coming soon

→ Reply
»
6 years ago, # |
  Vote: I like it +38 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    I made one look at B tests and decided to skip hacking this problem.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      So precisely now we require systests on Problem B only

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        There is no succesful hacks for this problem. So no additional tests for systests.

        → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C instead of precomputing?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Digit DP

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)...

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why this code got AC

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

while this one got WA

https://mirror.codeforces.com/contest/1036/submission/42633090

it is the same logic I think .

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

halyavin hacked my submission 42638507. I resubmited the same solution 42655238 and it was accepted. Is something wrong?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      oh damn :( Though there were a hope for me

      → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C by using digit DP?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem F:how to calculate fast enough？

→ Reply
»
6 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Can anyone tell me why 42622172 failed and 42624685 passed?

→ Reply
»
6 years ago, # |
  Vote: I like it +63 Vote: I do not like it

![ ](2hhbjk)

→ Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Editorial?

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +25 Vote: I do not like it

educational rounds are very good:good problems, hacking phase and ...

but they have one disadvantage: system testing start very late!!!

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E is this a valid input

1

11 11 11 11

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No, because A (first point on line) will not be equal B (second point in line), this is mentioned in the problem statement.

    → Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

After system-testing This is my most valuable one-twentieth second since I first joined Codeforces :D

Submission ID: 42637102

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't get it :D

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you explain me your brute force approach?

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          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).

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            That's quite some bruteforce but the only thing that matters is your solution passed.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              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 ;)

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                6 years ago, # ^ |
                ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                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.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Nah, the "Trie" name was a dead joke used in Competitive Programming Community's Discord. No real trie involved :D

                  → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I just read problem E.. Is it a direct 2d segment tree problem ? Or I am just over simplifying it ?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Or you overdid it somehow.

    I solved it with bruteforce and some math observations :D

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

And can you publish the analysis? (or throw a link to it)

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like 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?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes this is possible as there are 1000 lines only, thanks a lot.

          → Reply
»
6 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I really liked problem F!

(except for the fact that this is 955C - Sad powers and it is mine, lol)

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    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:

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    fyi
    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply