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

Привет, Codeforces!

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

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

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

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

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

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

Также есть сообщение от наших партнеров, Harbour.Space University:

Hi Codeforces!

We want to remind everyone that the Hello Barcelona Programming Bootcamp is right around the corner, and we’d love to see you there!

Our boot camp will once again feature the all-time greats Mike MikeMirzayanov Mirzayanov, Andrey andrewzta Stankevich, Michael Endagorion Tikhomirov, Gleb GlebsHP Evstropov, Artem VArtem Vasilyev, Ivan ifsmirnov Smirnov and other world renowned Russian coaches to train the participants.

We would also like to extend a welcome to some of the newest teams to join us from Colorado School of Mines, University of British Columbia and Reykjavík University.

Be sure to register before August 1st so everyone has time to get visas if needed, and of course for the Early Bird Discount of 15% or the Loyalty Discount* of 20% off registration for the boot camp!

*The loyalty discount is offered to universities and individual participants that took part in Hello Barcelona Bootcamps and Moscow Workshops ICPC.

Learn more about Barcelona ICPC Bootcamp

You can ask any questions by email: [email protected]

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

Место Участник Задач решено Штраф
1 tribute_to_Ukraine_2022 7 159
2 hohomu 7 274
3 guille 7 338
4 radoslav11 7 580
5 waynetuinfor 6 148

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

Место Участник Число взломов
1 halyavin 689:-132
2 2014CAIS01 91:-13
3 Al-Merreikh 20:-1
4 Ali_Pi 16:-3
5 gsparken 15:-3
Было сделано 978 успешных и 798 неудачных взломов.

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

Задача Участник Штраф
A Harpae 0:01
B eddy1021 0:05
C tribute_to_Ukraine_2022 0:09
D BARPITF 0:09
E Roundgod 0:19
F radoslav11 0:15
G chemthan 0:28

UPD: Разбор опубликован

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

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

Would you consider making the hacking time 6 hours instead of 12 hours as it has been discussed before.

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

No weak pretest plz.

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

Can the contest be rescheduled as it clashes with the FIFA WC 3rd Place match tomorrow? Probably delay it by 1 or 1.5 hours?

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

How to solve div 2a?

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

The penalty for WA is 20 or 10?

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

I can watch Hataraku Saibou right after this contest! It's great!

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

Educational WorldCupForces Round!

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

?detaR ti sI

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

?detaR tI sI

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

Minimize hacking phase to 6 hours

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

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

awoo What will be the penalty in this round, 10 or 20 ?

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

its reated? lol OALollolol xDXDxD :)))))))))))))))))))

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

btw :: How to solve div2 D,E?

in this contest yes .

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

    Not sure if this comment meant to gain upvote like before or to gain more downvote so he could be on the last page of contribution rank.

    Edit : he's already on the last page !

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

Why Codeforces (Contest writer) doesn't mention directly that this Educational Round will be rated for Div 3 participants also? As they mention "Rated for Div 2" directly.

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

    ¯\_(ツ)_/¯

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

    div3 is a subset of div2 maybe that's why who knows

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

      IMHO whether the round is rated and for which divisions should be an attribute of the contest like "Writers", "Start" and "Length", and not be part of the "Name" of the contest.

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

    Using the same logic, Why he didn't mention that it is unrated for Div. 1 participants also? Maybe because they are smart enough to know the contest is unrated for them.

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

Penalty Time??

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

When you want to take part badly but your laptop's display broke 3 hours before the contest :(

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

problem E is too poisonous,i mod 10^9+7 instead of 998244353.

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

    Well, it's even somewhat bold in the statement. And also repeated a couple of times. Should be noticeable.

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

      But why though? Why did you choose this mod?

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

        Well, there are two reasons.

        The first is that nowadays problemsetters tend to choose this modulo for all problems (not only ones requiring modular FFT) so that people don't see this modulo and instantly react like "Ok, we need a convolution here".

        And the second reason is that, when I started preparing this problem, I didn't understand that there is a simple math solution, and tried to solve it with online modular FFT instead xD

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

OEIS is your friend for Problem E : link

Edit: this sequence gives the number of occurences of each element in reverse order (last one occurs 1, second to last 3 times etc.)

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

    aah shit

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

    But 40343744 ??? I think that problem E require another sequence 40349064

    UPD: sorry, my wrong, I just forgot about modulo

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

    Not sure why this is being downvoted, I found the exact same sequence online during the contest.

    A fairly common problem solving technique: 1) write naive solution 2) find pattern (possibly look online) 3) hard code in formula

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

What is the 5th test case for problem C?

and someone also give me some hard test case for this problem.

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

For problem C, Why my solution failed? http://codeforces.com/contest/1009/submission/40348123

Edit: Failed on pretest 5

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

    n is an int up to 10^5 and you are doing n*(n+1) when you calculate beech

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

    One obvious reason is overflow. You have beech = n*(n-1), but n is an int. See what happens when n = 100000 or n = 99999.

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

I've been really enjoying this series of contests, but out of curiosity, wouldn't it be better advertising to create Div 1 rounds? I'd love to go to the camp, but considering how far away I am from making ACM worlds, it's hard to justify the expense.

I think Div 1 participants are more likely to take the plunge and spend 1000+$ and a week away from school.

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

A very good contest with a very smooth difficulty curve, not an easy thing to make. Good job to the writers

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

When can we submit?

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

Taking strong tests to another level :P

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

    There are actually 130 tests in this problem.

    It was originally used in Saratov SU trainings a few days ago, and there was a man who managed to receive RE 130.

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

    Yeah, strong tests in tree problem without test "1-2-3-...-N". This is Educational round.

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

Can somebody explain why my code for E got TLE in Test Case 9 (though I think it's O(n)) and for C got WA in test 5 ?

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

    For C: check overflow. You're multiplying two ints and storing the result in a long long. Overflow happens before the storing does.

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

    For E: You're reading 10^6 numbers using cin. Speed it up with ios::sync_with_stdio(0) and cin.tie(0) or use printf/scanf.

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

Could someone please explain why this code doesn't work for problem D? http://codeforces.com/contest/1009/submission/40345268

Here's the approach I used —

Since the graph has to be connected, the M has to be >= N-1 otherwise impossible. I then proceeded to take the sum of all phi(n) from 1 to N (phi(n) being the Euler Totient Function). If this sum >= M, I then use sieve to create the graph.

I started matching 1 to all nodes from 2 to N, thus making the graph connected. This meant I had M — N + 1 edges left to add. I used sieve to find relatively prime numbers and as soon as the count of edges hit 0, I returned 0 and proceeded to print the graph.

I would really appreciate a counter-test so that I know where I was going wrong. Thank you!

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

    I tried 20 45 and the last edge you print is 4 10. GCD( 4 , 10 ) = 2. Hope this helps

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

    Looks like you're just counting multiples of a number as non-coprime with it, which is only true for primes — not composite numbers. Try 6 11. You print 4 6.

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

    For every x, sieve will only delete every multiple of x (not relatively prime of x). So your sieve will delete every multiple of x, add every y where y is not multiple of x, and readd every multiple of x

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

    Got it, thank you Diegogrc, IceKnight1093 and Firastic! I'll upsolve this now.

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

Educational.....

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

I don't know why I was getting TLE on test case 6 on problem C here. The time complexity looks linear to me. Maybe the logic for the problem I am using is wrong. But stil I shouldn't get TLE as I guess the complexity of the code I am using is O(n). Can someone explain both the logic and the problem with my code?

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

    I'm not sure but i think your arrays are too small (10000 instead of 100000).

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

      Damn! I also figured that out like a minute ago and yeah the array size is small. I just missed it literally by a '0'. It's frustrating. But the contest was really good. Hats off to problem writers!.

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

      So if there is a segmentation fault then TLE is given as error on codeforces right?

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

        It means it failed to meet the segmentation fault. Instead, it probably got into an infinite loop by changing the value of nearby variables (i.e., 'i' or 'm'), therefore getting TLE from it.

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

Great difficulty balance of the problems, shoutout to the writers!

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

Oh.... I fall a trap in Problem B and got confused a lot on that problem

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

How to solve B?

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

    1011201120112 is 0111111120202

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

      greedy doesn't work? I am getting the same soln but still dreaded test case 4 fails

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

        It works perfectly. my submission : http://codeforces.com/contest/1009/submission/40342688

        Greedy doesn't mean that you put all small values before bigger ones, we have to do so but under some constraints.

        Explanation of my solution: Maintain a reverse_ans string, initially null.

        Start from last, if there is a '0' or a '1' increase the counter for '0' or '1. If there is a '2', we know that we can't shift any '0' beyond this point, so first put all found zeroes to reverse_ans and reset its counter and now put '2' in reverse_ans.

        Important step (greedy but different to what is done above)

        At the iteration is over, first put all '1' to reverse_ans and then all zeroes.

        reverse the reverse_ans and print it.

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

          what I thought was get all 21 and convert to 12 and 10 to 01. The only exception to this rule was 201 which becomes 120. run this till I have no 201, 21 or 10 in my string. this soln fails and I want to know why or what test case am I missing.

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

            2121111111111111111111111111111(up to 10^5 length)

            If you look for all occurrences of "12" or "21", you should get a TLE.

            For WA, 0000212000001 Answer : 0000112200000

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

    Put all '1' s just before first "2". 012012 becomes 011202 , whereas your code gives 012012

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

    so, count '2' and '0' from first '2' and put them back of the string with same order. fill the rest of numbers 1

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

    count 1 in string then count 0 before any 2 comes then print 0 as per count then print all 1, then just print 0/2 as they come in string. for eg. 101201120 becomes 011112020

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

    Maintain the order of 0's ans 2's. Take all 1's and put them just before 1st occurence of 2.

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

1:59:59 :D

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

Cool problems, thanks to round authors.

why is this recurrence wrong for E?

where dp[0] = 0 and a[i] is the prefix sum. I can use fenwick tree for prefix sum but why logic error? I am choosing the rightmost stop and then I calculate difficulty for remaining sub problem.

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

    This recurrence is wrong because it doesn't take probabilities into account.

    For example, suppose you are analyzing 4-th kilometer and trying to find a closest rest stop before it. The probability that it will be on position 3 is 0.5, the probability that it is on coordinate 2 is 0.25, and so on. So we can't just sum all these dp values up, we need some coefficients.

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

How to solve E ?

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

    Note: I didn't actually solve E but I got the problem right after contest ended...

    The answer is:

    where

    P[i] = 2N - i - 1·(N - i + 2) for i = 1...N-1

    P[N] = 1 (technically same as above but 2 - 1 is fractional)

    mod MOD at each step of course

    I used brute force to find array for first 10 numbers and entered the list into OEIS

    edit: off by 1

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

Why this got MLE 40349306 and this didn't 40349677? Very strange, how much memory deque uses...

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

NEVEEER USE DEQUE If you don't like to get MLE :(

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

problem B was very good!

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

Huh. For problem E if you use cin, you get TLE on test case 7, but if you use scanf you get AC :O

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

In D problem even the custom invocation is showing possible but the test case 18 is giving Impossibe for my code Please check out this solution http://codeforces.com/contest/1009/submission/40348587

Same Code gets submitted after ccontest http://codeforces.com/contest/1009/submission/40350442

OOps figured out n*(n-1) crossed int limit

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

    Looks like your solutions just overflows in m>(n*(n-1)/2).

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

    The problem with the first one was overflow: you were comparing m with (n*(n-1))/2 where n was an integer. If n is large enough the product will overflow and become negative. Second submission doesn't have that comparison so it passed.

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

For C i used double instead of long double to store (double)total_sum / n. Can it cause wrong ans in main test due to precision issue?

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

Today's D was easier (till now I think) compared to the last contests. And I wasted my time to look for corner cases and if any case that will lead me to TLE. Could not get time to solve E (which had a nice pattern). Anyway, educational contests are fun than the usual ones. Though I messed up today's one badly. Did not think today's one was going to be simpler than the past.

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

In the test 11 of problem C:

Checker comment ok found '621354311313.3487500', expected '621354311564.2170400', error '0.0000000'

Why is the output correct?

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

...

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

    We can always bring any 1 to the beginning of the string, since we can swap 1 with any other digit.

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

    because there are sufficiently many 1s in the string, the 0 and 2s have become invisible after the moves.

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

guys someone sent me a message which asks me to help him solve C and that he will help me solve B. Fortunately I was not noticed with that message during the contest and as you guys can see I ended up without solving B and after the contest i solved it by myself. My question is: how can I report him for cheating?

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

In the test 11 of problem C:

Checker comment ok found '621354311313.3487500', expected '621354311564.2170400', error '0.0000000'

Why is the output correct?

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

    Its relative error is smaller than 10 - 6

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

    In terms of relative error, it's correct.

    If it is stated that "Your answer is considered correct if its absolute or relative error doesn't exceed 10 - x", then checker considers the minimum of absolute and relative errors.

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

how to solve D?

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

    Run two loops(1 to n and from i+1 to n)and calculate gcd (i,j)if it is 1 then print as m can be atmost 100000 so the both loop terminates after m iteration. And if n>m-1 you have to print impossible as the graph then can't remain connected

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

      "as m can be atmost 100000 so the both loop terminates after m iteration" can you please prove it or can give some intuition behind it?

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

        It's not true, using this method at least. Since every pair is being checked, even those with gcd(i, j) != 1 will be checked, leading to more than m iterations in total.

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          for(int i=1;i<=100000 && al.size()<=100000;i++){
                  for (int j = i+1; j <=100000 && al.size()<=100000; j++) {
                      if(gcd(i,j)==1){
                          al.add(new pair(i,j));
                      }
                      x++;
                  }
              }

          x came out to be 100002

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

            The worst case for this will actually be with a somewhat smaller n but large m. Maybe something like n = 10000, m = 100000 will work, I haven't tested exactly. If n is very large, most of the edges will come very quickly since you get n-1 from 1, and 2 and 3 are both prime. Only when you need i to go fairly high (and be composite) do you start getting less edges added per iteration.

            Edit: n = 10000 and m = 100000 gives x = 161528. This algorithm is probably going to be fast enough, but certainly not going to stop in exactly m steps.

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

        The ratio of number of relatively prime pairs (i, j) that 1 ≤ i ≤ j ≤ n and all pairs is:

        Probability of coprimality. We can generate random pairs using uniform distribution and choose only $ m $. In C++ I used std::uniform_int_distribution, std::mt19937 and my hastable and got accepted.

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

    Given n, the number of possible edges is basically all those (unordered) pairs (x, y) such that x, y ≤ n and gcd(x, y) = 1 and x ≠ y. This number is simply φ(1) + φ(2) + ... + φ(n) - 1, where φ is the totient function. (subtracting 1 since we can't have the pair (1, 1).

    This gives us 2 edge cases: if m is greater than this number or m < n-1 it's not possible to create such a graph — either it won't be connected or there won't be enough edges.

    In every other case, it's possible. Connect 1 to every other node first to connect the graph. Then, for each pair (i, j) such that gcd(i, j) = 1, i ≤ j, 1 < i, j ≤ min(n, 600) you have one edge. 600 because φ(1) + ... + φ(600) > 100000 so you're guaranteed to have enough edges with just that.

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

    In D, the most important task was to check possible or not because other than that, we just need to output co-primes together.

    In order to check co-primes of available, you just need to implement Euler's totient function. Thus in O(n), we can check possibility or not.

    We could have stored this value in a vector to check is total count is greater than required and n-1 as well. But that can bring TLE for large cases.

    Submission

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

How to solve F? Can it be done in O(NlogN) or O(N)?

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

    Do dfs on a tree, and for every node x, you can find the array d(x). You can make it in O(nlogn) if you merge there arrays carefully. MLE solution: 40349306 Correct: 40349677

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

      This technique is called dsu on tree?

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

      In fact, we can even make it O(n) if we merge the structures for subtrees not according to their sizes, but according to their heights (merge lower subtree to higher).

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

        Can you explain this, how to merge in O(n)?

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

          It seems that 40349677 (if I understood the code correctly) actually uses this method of merging in O(n). You just need to do the same things you do in standard small-to-large approach, and it "magically" works in O(n) time if the size of subtree's structure is proportional to its height (and merging two structures can be done in time proportional to the size of a smaller structure).

          A more detailed explanation, proof and my implementation will be in editorial.

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

После просмотра переборных решений на D

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

Can someone confirm if everything is okay with Problem-D ? My solution SEEMS to be working well on my system but failed pretest number 3.

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

Obviously http://codeforces.com/contest/1009/submission/40351881 submission will eventually fail, because of taking limit small, but I can't for the life of me figure out why it is getting wrong answer on test case 4. Could someone please help me out? Every single thing besides considering number of nodes(which should in no way be a cause of getting wa at this test case) seems fine in here to me and yet I'm getting WA on F, test case 4

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

Can anyone tell why my solution got hacked after passing the preliminary tests here

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

Maybe it's one of the simplest solutions on problem E.

#include<bits/stdc++.h>
using namespace std;
const int p=998244353;
int n,x,l,s;
int main(){
	cin>>n;
	while(n--){
		l=(l*2%p+x)%p;
		cin>>x;
		s=(s*2%p+l+x)%p;
	}
	cout<<s;
}
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In Problem D . I tried to use totient function to find out if it's possible or impossible to form the graph. And then just printed out the no whose __gcd(i,j) == 1. Is this approach correct although I'm getting wrong answers . Am I missing some vertices? http://codeforces.com/contest/1009/submission/40351068

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

    The graph should be connected.So your solution got wrong when m<n-1

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

      So what's the correct procedure to print?

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

        You are supposed to print "Impossible" when m<n-1,since in that case you can't connect all n vertices within m edges.

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

    Yes, 3 things-

    1) Your graph is not necessarily connected so include all the edges of type 1 i ,i>=2

    2) Check condition for p>=m and m>=n-1 in your if part

    3) Run loop only till 600 because summation of euler function is >100000 for 600 i.e upto 600 you will get enough edges to make the graph connected satisfying condition for m edges.

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

Я в третьей задаче(c) использовал setprecision для регулировки кол-ва цифр после запятой, но не учёл, что эта функция регулирует просто кол-во цифр в выводе, так вот каким-то неведомым образом она прошла стартовые тесты на контесте и потом у меня её взломали, сейчас я решил посмотреть, что за были за предсистемные тесты, так она выводила неправильный ответы, а вердикт был "ОК", на этих тестах, подскажите, пожалуйста, это баг или я чего-то не понимаю? Фото прилагается.1009C - Надоевший подарок

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

    В данном случае error показывает минимум из абсолютной и относительной ошибки. Так как относительная ошибка меньше 10 - 6, то ответ считается верным.

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

Can't be more accurate

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

    This works, but wouldn't there be any overlapping cases ?

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

      It says that "This scheme is exhaustive and non-redundant with no invalid members" so it shouldn't produce overlaps.

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

Sequence A001792 in OEIS for task E.

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

Was the evaluator for problem C correct? My solution ( 40334143 ) got hacked after the contest, and after checking the test cases that were ok i found something weird. In Test 11 my answer was off by more than 100 and the evaluator returned ok. Is this a problem with the evaluator? I believe this shouldn't happen

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

None of this matters much, but I'm curious how the standings and problems solved vary during the hacking phase. I understand that as solutions get hacked, people lose credit for problems, so their ranking would go down. That means that if you don't have a solution hacked, your rank tends to get better. And, the dashboard generally shows fewer of each problem solved, as solutions get hacked.

But, I've also seen my ranking get worse (without having a solution hacked) at some points during the hacking phase — generally just a little bit — maybe 10 places. And, I occasionally see the number of solved problems go up during the hacking phase. I imagine the number solved might include people submitting them afterward, but presumably that doesn't affect ranking. Any ideas how this is happening?

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

In today's contest I saw many solution of C got hacked,after the hacking phase could anyone please state in what case many of the contestant's solution went wrong.

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

    most of them have kept of datatype of sum variable as double which will overflow for large values x and d when summed across m queries.So use long double instead!!

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

      I also have used double, but when I tried to hack my solution by putting maximum constraints, even then it passed the test.

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

      I used long long. Still no hack. And a lot of used long long. long long sum and then cout << fixed << setprecision (10) << (double) sum / n * 1.0 << endl;

      This seems to work fine. So, I am curious about what the hack case is.

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

        I see that Test #11 says "ok found '621354311564.2196000', expected '621354311564.2170400', error '0.0000000'". Umm why is this? Edit: Sorry for the mistake, I just found out that it is the relative error.

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

      Yeah I just checked the sizes of double and long double.Double is of 8 bytes while long double is 16 bytes on C++ 14. I kind of had a misconception both were of 8 bytes,but now I see those were for older versions.

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

Can somebody please explain how double in C++ works? I was sure it takes 8 bytes and has diapason from -9 * 10^18 to 9 * 10^18. Where am I wrong?

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

    Double (and other data types for real numbers) can have precision errors. The numbers in computers are represented by bits. Int takes 4 bytes, long depends on the OS, long long 8, float 4, double 8 and so on.. Check this link for more information: https://www.tutorialspoint.com/cplusplus/cpp_data_types.htm

    I think you know that int data type is limited to values between -2^31 to (2^31 — 1). In that range, there are exactly 2^32 different numbers which is the maximum we can represent with 32 bits. Float is a data type for real numbers and its size is 4 bytes (same as int). That means, we have 32 bits and we can represent at most 2^32 different values. We know that float can be used to represent some real numbers which we cannot represent with int. That means for one real number, we have used one of those 2^32 combinations for its representation. Then if we try to represent every possible integer in the int range, there will be some numbers whose int and float values will be different. Thus those floats will be rounded to another value.

    Real numbers can be represented with the IEEE 754 standard. You can Google it for more information if you want to see how it works. That representation, allows us to represent very high numbers (I think it’s something like 10^308). But, we can only represent 2^size different numbers where size is the size of the data type in bits.

    I explained you about float, and I hope you understand what’s the problem with those representations. It’s similar for double, its length is just 8 bytes.

    Try the following program. An example of an integer that gets rounded when represented by double.

    #include <bits/stdc++.h>
    
    using namespace std;
    
    typedef long long ll;
    typedef double db;
    
    int main()
    {
        ll x = (1LL << 61) + 13213124123213213LL;
        db y = (db) x;
    
        cout << fixed;
        cout << x << endl;
        cout << y << endl;
        return 0;
    }
    

    And since some integer numbers get rounded by real data types, it’s also true that some real numbers will get rounded as we don’t have infinite precision. And if your program rounds the number many times, you may get wrong answer verdict for some example.

    I fixed your program: http://codeforces.com/contest/1009/submission/40360084 My advice is, try to use as less real data types as possible. In line #13, you were using double to calculate a number which can be as big as 10^10 (= (10^5)^2) and as I explained you, it’s a bad idea.

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

halyavin is doing wonders!!! What a hacker!!

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

I think that the judge for C should be made with integers to check for precision, because halyavin made too many hacks.

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

I think that for C the judge should be made with integers, because it can be not fair sometimes.

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

After how many hours does system testing start for educational CF rounds?

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

Where's editorial?

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

Can anyone please tell me what is wrong with this 40362288 ?

40362440 This one gives me AC. The Only difference is I have declared the variable sum as long long is this submission and as double in the previous submission ? How can this give me wrong answer ?

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

Can someone help me with problem A? My solution passed all test cases yesterday but now it shows wrong output on test case 9, but on my machine the output matches correctly with the answer.40325412

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

how did halyavin hack 600+ in 12 hours manually?

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

I don't understand why my solution got Hacked

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

    double has problems with precision. For example, calculating 1e18 - 1 - 1e18 sequentially results in 0.0 instead of -1.0.

    View test provides the generator of the hack. It constructs a general input hacking all solutions that accumulate the answer with double.

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

      thanks!!! and can you suggest how can I tackle this problem

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

        The answer before being divided by n won't exceed mn2(d + x) about 1e18. Thus int64 (long in Java?) is efficient to store the answer. Then you can output the answer divided by n in double.

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

Can anyone tell if my submission for problem C is correct or not? Whether it will pass the tests used in the hacking. http://codeforces.com/contest/1009/submission/40330305

I used double in the end for division and before that used long long to store the sum. Can’t double store till 10^18?

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

I didn't understand problem F.

How depth array of vertex 1 of example 1 look like?

I thought it would be {0, 1, 1, 1, 0, ...} and the dominant index would be 1 but 0.

Is a vertex an ancestor of itself?

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

    It depends on how we define i guess. I think it should have been specified to consider a vertex as ancestor of itself,but by looking at the sample tests you can get it.

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

    Yes, vertex is an ancestor of itself in this problem.

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

    The array is actually [1, 1, 1, 1, 0, 0, ...]. The first element is 1 because (by definition) there is one vertex so that the simple path between 1 and y contains 0 edges. Path with 0 edges means its the vertex itself, so it's 1. And yes, the vertex is its ancestor. The same is true any other vertex, so the array always starts from 1.

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

    Thank you all for kind reply.

    During the contest, I was searching the definition of ancestor over and over... to understand example

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

Great contest

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

can you tell me why my submission 40370101 is WA at test 39?PLz PLz PLz

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

Can someone list what should I study to solve C, E and F. Thank you.

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

Where's editorial ?? Also what's the approach of E? Or should we just use OEIS to find the pattern?

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

    The editorials for educational rounds are always really late. Probably will take a few more hours/days. :-(

    E is just dynamic programming. Find a recursion for dp[i] = sum of all path between 0 and i. Hint: think about the location of the last rest site.

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

    Editorial will be published in 4-5 hours, sorry for the delay.

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

How to solve F with Dsu?

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

How to solve F with dsu?

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

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

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

Can someone explain how halyavin's hack for C causes double to not be precise enough?

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

    I construct a test where answer is close to zero but intermediate results are as large as possible. This causes catastrophic cancellation and loss of relative precision.

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

978 successful hacks

So the green hacks team won again?