Автор awoo, история, 6 лет назад, По-русски

Привет, Codeforces!

В такой замечательный день недели, как 07.09.2018 17:35 (Московское время) состоится Educational Codeforces Round 50.

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной придумывали и готовили Владимир vovuh Петров, Роман Roms Глазов, Иван BledDest Андросов и Максим Neon Мещеряков.

Удачи в раунде! Успешных решений!

А вот сообщение от наших друзей из Harbour.Space:

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.

Поздравляем победителей:

Место Участник Задач решено Штраф
1 eddy1021 7 298
2 bmerry 7 301
3 LYJabc 7 547
4 thjchph4trjnh 7 551
5 BigBag 6 192

Поздравляем лучших взломщиков:

Место Участник Число взломов
1 halyavin 240:-18
2 greencis 47:-3
3 vinuthegr8 15
4 antguz 14
5 cubercsl 14:-9
Было сделано 497 успешных и 440 неудачных взломов.

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

Задача Участник Штраф
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: Разбор доступен

  • Проголосовать: нравится
  • +131
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +64 Проголосовать: не нравится

Imagine a CF round everyday xD

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

3 continious contests in three days.

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое).

Означает ли это, что во время контеста решения будут тестироваться только на претестах? Или все-таки тесты будут полными, но тем не менее возможность взломать решения дается?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Решения будут тестироваться на претестах, но писать будет "Полное решение", если решение пройдет на претестах

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    Будет тестироваться на всех тестах, заготовленных авторами. Учитывая их качество, их и претестами то зачастую сложно назвать.

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится -9 Проголосовать: не нравится

    Решения будут тестироваться только на претестах во время контеста

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится

      Я кодфорсесы гонял, когда ты еще пешком под стол ходил :p

      Правка: Если что, мой коммент относится к первой версии комментария NotIdeal.

      NotIdeal, нехорошо так значительно менять содержание комментария.

»
6 лет назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

Finally an Educational Round after long time :P

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

three consecutive contest in three days.

it is wonderfull! thank you CF for your contests!

»
6 лет назад, # |
  Проголосовать: нравится -78 Проголосовать: не нравится

10000000000 Upvote for me to beat tourist

»
6 лет назад, # |
  Проголосовать: нравится -49 Проголосовать: не нравится

I'll be the rank 1 of this contest.

»
6 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Half century of educational round.

50*

»
6 лет назад, # |
  Проголосовать: нравится -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 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

2 minutes to go!

»
6 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +59 Проголосовать: не нравится

swap(C, D)

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +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 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
          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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

I hate geometric-observation based problems -_-

»
6 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

    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.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Using cin costed me a TLE submission for D :(

»
6 лет назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +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 лет назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

Using int costed me a WA submission for D :(

»
6 лет назад, # |
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 lines

Edit: ans=sum(integer points on segment)-sum(degree of intersection points)

»
6 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Interesting problems, thanks to authors!

»
6 лет назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
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 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

How to solve F? How to solve G?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 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 лет назад, # ^ |
        Проголосовать: нравится -6 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Any subset of sources that is neither empty nor full

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
          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 лет назад, # ^ |
              Проголосовать: нравится 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 лет назад, # |
  Проголосовать: нравится -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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anybody give a neat idea about problem B?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +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 лет назад, # ^ |
      Проголосовать: нравится 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 лет назад, # |
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 methods

UPD: okay i see that my knowledge at the time complexity is kinda trash, my apologies to everyone.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +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 лет назад, # ^ |
        Проголосовать: нравится -18 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +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 лет назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

A scared me at first

»
6 лет назад, # |
  Проголосовать: нравится +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 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In A, suppose the input was 4 and 8, why can't we push all points to 1 and make a rectangle of area 8?

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

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

Today's problem D.

The round should go unrated.

»
6 лет назад, # |
  Проголосовать: нравится -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 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 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 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

42640437

Why double fails int the problem A ?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +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 лет назад, # |
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 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    He maybe stores problem solutions!

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +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 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

hope the very next contest will coming soon

»
6 лет назад, # |
  Проголосовать: нравится +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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve C instead of precomputing?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    Digit DP

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +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 лет назад, # |
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/iV22N9

https://ibb.co/cT95aU

https://ibb.co/fKfYUp

»
6 лет назад, # |
  Проголосовать: нравится 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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve C by using digit DP?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 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 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Problem F:how to calculate fast enough?

»
6 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Can anyone tell me why 42622172 failed and 42624685 passed?

»
6 лет назад, # |
  Проголосовать: нравится +63 Проголосовать: не нравится

![ ](2hhbjk)

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Editorial?

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +25 Проголосовать: не нравится

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

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

in problem E is this is a valid input

1

11 11 11 11

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In problem E is this a valid input

1

11 11 11 11

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 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 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

Submission ID: 42637102

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I don't get it :D

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +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 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Can you explain me your brute force approach?

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится +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 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

            • »
              »
              »
              »
              »
              »
              »
              6 лет назад, # ^ |
                Проголосовать: нравится +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 лет назад, # ^ |
                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 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Or you overdid it somehow.

    I solved it with bruteforce and some math observations :D

»
6 лет назад, # |
  Проголосовать: нравится 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 лет назад, # ^ |
      Проголосовать: нравится 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 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 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 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    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.

    • »
      »
      »
      6 лет назад, # ^ |
      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 лет назад, # ^ |
          Проголосовать: нравится +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 лет назад, # |
  Проголосовать: нравится -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 лет назад, # ^ |
      Проголосовать: нравится +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 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

I really liked problem F!

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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