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

Привет, Codeforces!

28 декабря в 17:05 по Москве начнётся Educational Codeforces Round 35.

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

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

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

Задачи вместе со мной придумывали и готовили Иван BledDest Андросов, Владимир vovuh Петров и Алексей Perforator Рипинен.

Спасибо Михаилу MikeMirzayanov Мирзаянову за отличную систему Polygon!

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

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

Hello everyone!

Registration is open for our upcoming 1st Hello India x Russia Programming Bootcamp, with 20 teams signed up and counting, and we are looking forward to seeing you and your teammates in India this March!

More information

Register here

UPD: В раунде будет 7 задач!

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

Rank Competitor Problems Solved Penalty
1 bmerry 7 212
2 uwi 7 216
3 halyavin 7 287
4 hesihesiwujiuwu 7 314
5 voidmax 7 337

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

Rank Competitor Hack Count
1 halyavin 328:-26
2 Kilani 107:-6
3 Aemon 91:-33
4 algmyr 57:-4
5 Yazdanra 29:-9

Было сделано 1761 успешных и 1237 неудачных взломов.

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

Problem Competitor Penalty
A IHaveInt 0:01
B Benq 0:03
C WZYYN 0:06
D PrashantM 0:08
E perchema 0:15
F pekempey 0:38
G chemthan 0:21

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

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

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

We are having too many rated contest at the end of 2017. We hope that we'll have such opportunities in coming year! Thanks for organizers and competitors. Good Luck to all.

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

I really like rated Educational Rounds! Thank you guys! Good luck everyone!!

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

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

Again no one thank MikeMirzayanov .

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

Did you think about Codeforces div 1.5 round — something liek CS academy?

For me it looks as good experiment and chances to make some interesting contest for guys with rating around 2000 ( we can not be at the top of div 1 and can not participe in div 2).

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

    The idea is really nice! I think here on CF problem sets and groups for which rating is calculated are bound too tight. We could have several groups(Div 1.2, Div 1.4, Div 1.6 etc) competing on same problemset. Currently getting to div.1 you most likely will be back in div.2 after one of next contests. Only Div1+Div2 is ok for 1900-2000 people :)

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

      I think if we have too level in the contests . It is too pressure for writers , and it will be too complex. But I think , If people which rating are in 1900 ~ 2000 can choose to join Div1 or Div2 by itself , It will be great ?

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

        I thought that we can make some only div 2 rounds to be div 1.5. I didn't think about adding one more division on each contest.

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

Again no one thank MikeMirzayanov .

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

35 = 7 x 5 and No of Hours = 2

So, Problems = (7 + 5) / 2 = 6

I wonder why authors mention number of problems! :/

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

Why is nobody thanking MikeMirzayanov

UPD: fixed

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

Если я правильно понимаю, то фаза взломов будет оконченна 19:05 (по Москве) 29 декабря, соответсвенно рейтинг раньше не изменится. А контест Good Bye 2017 начинается раньше (18:35 по Москве).

Мне очень хотелось бы знать, когда и в каком порядке будет пересчитан рейтинг:)

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

    В порядке контестов — сначала пройдет Good Bye 2017, затем протестируем и пересчитаем рейтинг по Educational Codeforces Round 35, затем пересчитаем рейтинг по Good Bye 2017.

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

      Спасибо, Михаил Расихович! Надеюсь, успею подготовить CF-Predictor к такому ходу событий :)

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

Does hacking fetches you points in Educational rounds as well?

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

Guys i will be giving Educational rated round for the first time so i just wanted to ask whether difficulty level of educational rated round is less than Div2, equal to Div2 or greater than it.

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

Another rated Educational Round? I love them. Good luck, guys.

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

Is there a negative score for a failed hacking attempt in Educational Rounds?.

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

Just curious, but with a tight schedule like this, how could system-rejudging process of this round work?

I mean, without any changes, the rejudge (after the hacking phase) will start in 23:05 (UTC+7), right in the middle of the Good Bye 2017.

Two issues may occur due to this:

1 — Rating changes for Div.2 members will be available very late, perhaps even after system tests of GB2017 (wow this is unexpected xD )

2 — As the judging machines have to work with a huge load of submissions from the previous contest, entirely; long waiting queues may be expected...

(I'm quite new here, and I haven't seen any tight schedule like this before. If it had happened, then I guess I've worried too much ;) )

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +42 Проголосовать: не нравится
    1. Testing of Educational round (after the end of Goodbye)
    2. Testing of Goodbye round
    3. Rating for Educational (probably somewhere during the testing)
    4. Rating for Goodbye
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It will be better, if it had scoring distribution.

P.S. Sorry for my English.

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

I like the rated Educational rounds (for Div.2), but this means that for Div.2 coders, there is rarely an unrated round (of suitable difficulty) for us to have a relaxing contest without a lot of stress. Perhaps this could be changed so that only some of the Educationals are rated?

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

Is it going to be the editorial for this contest?

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

Contest ID — 911. Coincidence? I think not.

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

I've made temporal fix of the CF-Predictor for educational round (calculates rating changes only for div2 participants), so I suppose actual rating change should be close to predicted:)

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

Sorry but Mishka sounds like a Girl's Name ..

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

I officially announce that this contest was shit.

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

problem_C

What do you mean by "LIT Garlands "

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

    We have "question to jury" option btw. Right below the problem list in the main page of the contest.

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

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

I didn't participated in the round. If I hack someone's solution successfully or unsuccessfully, would it affect my rating?

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

how to solve D

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

    Inversion number parity always changes whenever you swap two arbitrary elements in a permutation.

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

      thanks.

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

      Proof?

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

        let x be the total number of inversions before reversing the segment and y be the number of inversions between the range l &r. Then the total no of inversions after reversing the segment wiil be ( x-y+(d*(d-1))/2-y) =(x+(d*(d-1))/2-2*y) where d is the length of segment. Hence parity of inversions does not depend on number of inversions in between the range

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

Contest is now. How to solve D?

Edit: Meant "now over"

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

    swapping any two numbers changes the parity of number of inversions.. so just calc the initial number of inversions and how many pairs are being swapped in every query

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

    The parity of the number of inversions of a composition of two permutations is the sum of the parities of the permutations, mod 2. A permutation that reverses a segment of length d has inversions, hence it suffices to add this after each query and consider the amount mod 2.

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

anyone else getting run time error in test 30 of E ?

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

"The round is over"

refreshes

"System Testing: 99% Done*

So fast!

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

What is pretest 9 of E?

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

What is the test 6 of problem C..?? :|

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

Anyone has any idea regarding the test case 9 of problem E?

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

I literally did it .. today and couldn't find the mistake for 1hrs.45min. for the problem C.LOL

if(a==b==c and b==3)
   cout << "YES" << endl;
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    warning: suggest parentheses around comparison in operand of '==' [-Wparentheses] if (N==a==b)

    that's what -Wall, -Wextra etc is for

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

how to do problem D??

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

    You can count the initial number of inversions (we will call it x thenceforth) through brute force.

    For each query, it is certain that inside the segment, the inverse pair will become non-inverse and vice-versa. Therefore, the oddity of x after each query is decided by the oddity of nC2 (the number of distinct pair in the query's segment).

    If nC2 is odd, then if x was even back then, it will be odd, and vice-versa. Simply because the numbers of non-inverse and inverse pairs are not both odd or both even, therefore, the state of x will be changed.

    Similarly, if nC2 is even, x keeps the same state it was before the query.

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

      "If nC2 is odd, then if x was even back" doesn't the x means the number of inverses back in this segment? And if so then how to calculate inversion for a particular segment online?

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

        x is the number of inverses in the entire array.

        The idea here is to find out if x is odd or even. We don't have to (and in fact, to my experience, cannot within time) calculate the exact value of x.

        P/s: Maybe the ambiguity was caused by the "n" variable. By that I meant r-l+1 in each query actually.

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

          inverting a segment [l, r] will inverse all the pairs within it or will change entire array? I am thinking it change only that segment and if so then the extra number we have to add or remove from our count of inversion will depends on the previous value of inversion in [l,r].

          I know i am missing something please correct me!

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

            The pairs within it. It means only (r-l+1)C2 pairs are toggled.

            You don't need to update the permutation though. (well but you do need to update your count on the entire array, modulo 2).

            Let's assume that C = (r-l+1)C2 — the number of pairs in the current segment.

            Each pair among those C pairs are toggled — non-inverse will become inverse and vice versa.

            If we have z as the number of non-inverse pairs before applying the query, therefore we will have (C-z) inversions.

            After the query, as all pairs are toggled, we will have (C-z) non-inverse pairs and z inversions.

            Therefore, the difference of inversion count will be: abs(z - (C-z)) or abs(2*z-C).

            It's easy to see from there that, only the state of C (odd or even) affect the answer in each query.

            If C is even, then the difference will be even. Therefore, the state of the inversion count is unchanged; i.e. if it was odd, then it is still odd — same goes if it was even.

            If C is odd, then the difference will be odd. As a result, the state of the count is changed — from odd to even or from even to odd.

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

How're you going to start a rated round before calculating rating for previous one?

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

    You can check out this comment.

    Also, since Good Bye 2017 seems to have no rating restrictions (Div.1 and Div.2 users can join equally), then I guess there is no need to calculate rating before this round.

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

How to find number of current permutation?

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

    I think you mean inversions, in problem D you could have just done two loops to check for one, and for an better algorithm read this.

    And if by any chance you wanted the number of permutations, there are n! of them and you can read more about them here.

    Or you are trolling (no offence).

    edit : no trolling.

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

The solution of E is guessable from sample cases..

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

r/UnexpectedFactorial

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

Whats the solution for 2B? I tried DP by updating

DP[i]= floor(DP[x]/2), DP[x] = DP[x] — DP[i]

Where x is the index of the maximum element at each iteration but getting WA on T#3

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

    no need to use dp its just a simple math

    int n, a, b;
    cin >> n >> a >> b;
    
    int sm = min(a, b);
    int mxs = max(a, b);
    int ct = 1,mx = 0;
    while (ct < n) {
    	int cx = n - ct;
    	int smc = sm/ct;
    	int mxc = mxs/cx;
    	mx = max(mx,min(smc,mxc));
    	ct++;
    }
    
    cout << mx;
    
    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Can you please explain the logic of these two lines:

      int smc = sm/ct;
      int mxc = mxs/cx;
      
      • »
        »
        »
        »
        7 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
        i will explain using the second example 
        4 7 10
        ct is number of plates for the smallest cake 
        loop from 1 to n &mdash; 1 as ct
        for first round ct = 1
        then i will put all the smallest cake in 1 plate and the remain plates for the big cake
        its like 7/1 = 7 and 10 / (4 &mdash; 1) = (int)3.333 = 3 
        so 3 is the lowest value 
        do it for ct = 2
        7/2 = (int)3.5 = 3 and 10/(4-2) = 5
        so 3 is the lowest value
        ct = 3
        7/3 = (int)2.3 = 2 and 10 / (4-3) = 10
        so 2 is the lowest value
        ct = 4 = n
        7 / 4 = (int)1.75 = 1 and 10/(4-4) = infinity
        
         
        
        
        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          I tried to distribute the cakes according to the ratios a/(a+b) and b/(a+b). So the person with more cakes gets more plates to fill and so on. It got hacked. Could anyone please suggest what is wrong in this logic of assigning plates to cakes?

          Here's my code https://ideone.com/cNB2Ly

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

            i generated 1 million testcase and compare with my solution you got tooo many WA for example for this testcases 4 11 18 your output is 5 my output 6 4 13 21 your output is 6 my output 7 4 15 24 your output is 7 my output 8

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

              Thanks a lot for the cases! The issue was not in the logic, but in the implementation. Instead of using the round() function, checking the max of the answers for ceil and floor suffices IMO.

              Here's my final code: https://ideone.com/jeAaa2

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

    Some of the n plates are going to be of type 1 and the others of type 2. If you know how much plates of each type you will have it's easy to get the optimal answer, Then just try every possible distribution of the number of plates, there are only O(n) of them.

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

how to solve E?? Thanks in advance

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

loading...loading...RIP Hacking

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

How to solve F?

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

I have a question. Will the rating be updated before GoodBye 2017?I remember the distance between the ending time of this round and the beginning time of GoodBye 2017 is 23.5 hours. When GoodBye 2017 begins, this education round's hacking process haven't ended. Shall we decrease the hacking time of this round or postpone the beginning time of GoodBye 2017 to let us know the rating change before GoodBye 2017?

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

    awoo's words

    1.Testing of Educational round (after the end of Goodbye)

    2.Testing of Goodbye round

    3.Rating for Educational (probably somewhere during the testing)

    4.Rating for Goodbye

    that's the order

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

The problems were very good, especially problem F but I couldn't solve it.

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

    if you understand the solution now then please explain it. It will be a great help :)

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

Will (un)successful hacking attempt cause increase/decrease in penalty?

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

I 'm sorry for this troubles make. Sorry! See you in Goodbye 2017

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

Will hacking change the rank list ?

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

Does hacking help in increasing the rank other than the people which is not hacking? Your text to link here...

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

    NO

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

      So why do people waste time on hacking? the fault will eventually occur in system testing

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +32 Проголосовать: не нравится
        1. You can add your test to system testset;
        2. You can appear at main page of codeforces by getting to top-5 hackers of the contest;
        3. You can have your friends to see that sweet "+k" near your handle in standings;
        4. You can just enjoy it!
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In problem D if the question is modified as :- there will be Q queries and type 1 and 2 type 1 l r — reverse the segment from l to r type 2 l r — give the number of inversions from l to r

Then how would we solve it ? . using a segment tree or something i guess

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

    I am not sure if it can be solved in something under .

    Here is such a problem but with swaps instead of segment reversals.

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

      do that fit time limit?

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

      If n=1500, then we can find all the pairs (i,j) and for each pair we can map it to 1 if inverted else 0, sort it according to j values and build a segment tree of sums out of that. Then, for every l and r we can find effective r' (means how many pairs are there till r) and update (1,r') and effective l' and update (1,l'). In update operation we just invert it (0 if 1, 1 if 0). And the answer will be sum of all nodes in segment tree. Complexity- O(q*log(n*n)) Will this work?

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

Any hint on how to solve E ??

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

    When performing the stack sort, you can never push a number onto the stack that is bigger than a number already on the stack, otherwise they will come off the stack out of order. So a successful stack-sort, if it exists will always be: pop the stack until the top is bigger than the front of A (or empty), then pop from A onto the stack. You can simulate that for the first k values to check if it is valid (as in, numbers popped were 1, 2, 3, ... up to some value). Note that the stack will always be sorted (smallest at the top).

    To complete the sequence, suppose that the top of the stack is currently X. A must then contain all missing number less than X before any value greater than X. To get a lexicographically maximal solution, they should appear in A in decreasing order. It's also easy to verify that this will give a valid solution.

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

Is there any way to stop the scoreboard auto-refreshing. It's really annoying when I'm looking at a solution to find a hack, and the scoreboard reloads and I lose what I was looking at.

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

How to solve G?

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

    segment tree. but i've tried to solve it by UFS && block_division

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

    Try to solve it with several segment trees :D

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

    I've seen two solutions:

    1. O((Q + H)\sqrt{N} + N), where H = 100. Divide the array into blocks of size . For each block and value, store a linked list of all the places that value occurs in that block (in no particular order). To process a query, process the two partial blocks at the ends iteratively, but for the full blocks, just do an O(1) splice of one linked list onto another.

    2. O(QH\log Q + N). Store a segment tree over the updates, where each element in the segment tree is a transition table. At the leaves, an transition table is either the identity (for an "inactive" update) or an identity but with f(x)=y (for an "active" query). The root of the segment tree gives the composition of all the active updates. Now do a sweep through the array, activating updates when reaching l and deactivating them when reaching r, and looking up each a[i] through the root of the segment tree. Composing two transition tables takes O(H) time, so each activation/deactivation takes O(H\log Q) time.

    EDIT: took the big-O times out of maths mode since the images seemed to be broken.

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

    Build a segment tree, where each node has an array to[1...100](to[i] refers to what the number i will become after all modifications on the interval).

    Yet actually, I solved the problem using 100 bitsets(S[1...100]) of length n, where S[i] consists of all appearances of number i. Despite the O(nq) complexity, the constant is so small that I passed all the test cases. 33723537

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

I think Problem D needs N*M big test cases. Some of the programs are obviously O(NM), with constant > 2, which is most likely to be TLE, but we cannot submit that big test cases to hack.

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

    Can you link one of this submissions ?

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

    You can use test generators.

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

      I'm curious: are you using some sort of automated system to download source code for local testing? I can't imagine doing 300+ challenges by hand...

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

        Well, I always fill the hack form by hand (does copy-paste count?). It is as tedious as you can imagine.

        Local testing is the primary source of the challenges. It is a good idea to check the test locally in any case to avoid unsuccessful challenges. Unless it is UB, in which case I use custom invocation tab for checking and tuning the test. I also use Virtual Box for all local testing just in case.

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

          Are you also manually copy-pasting from the solution view into the file you test on locally? Assuming the majority of solutions aren't hackable, then presumably that involves more work than the actual hacks.

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

how to solve F : Tree Destruction ?

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

E is just a simulation problem , why added the "data structure" tag ??

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

Got plenty of TLE on G qwq

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

When I first saw problem D, I thought of splay tree.... But then I found that a is equal to -a under modular 2.... Then it was solved under the complexity of O(n+m)...

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

    Can you explain the preprocessing part of your code? How to count initial no. Of inversions

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

      It's well known that if you want to get the exact number of inversions of a given permutation , you can solve it in no less than O(n log n).

      However ,this problem is only about the parity of the permutation.

      Consider a theorem in linear algebra:If you swap any 2 elements of a permutation ,the parity of the permutation will change.And we know that the permutation "1 2 ... n" is an even permutation.That is, if we swapped C pairs of numbers to make it identity permutation, the parity of the number of inversions is the same as C's.

      Sorry for my terrible English if it does trouble you :D

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

In problem C, how to prove 4 2 4 is a valid case ?

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

    ((1,3)(2)(4))for every 4 numbers.

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

      Sorry still don't get it :-( maybe if you can tell me the logic behind your solution please.

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

        Well...The question is to ask whether there exists some residue classes whose union is N_+.

        It's obvious that if S= 1/k_1 + 1/k_2 + 1/k_3 < 1 , then it's impossible to reach the condition.

        May wish to let k_1 <= k_2 <= k_3 , that means, if k_1 > 3 , it's invalid.

        Next, if k_1=3 the only solution is that k_1=k_2=k_3=3 , otherwise S < 1.

        We can easily get the idea that if there exist k_i = 1 , it's always correct.

        Finally we think of the state of k_1 = 2.

        The valid solutions are (2,2,x) and (2,4,4) ,because we can let (x_1,x_2,x_3)=(1,2,x)and(1,2,4) respectively.

        It can be proved that most of the other conditions lead to S < 1 , except for (2,3,3),(2,3,4),(2,3,5),(2,3,6), but we can verify that they are invalid.

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

    We can start the garland with time interval = 2 on an odd number(let's say we start from 1). So according to the problem statement 1,3,5,7,......,2*n + 1 are covered by this garland. With odd time intervals covered, now we need to cover only the garlands that occur at even time intervals.

    Now lets start another garland with time interval = 4 from an even number( say 2). Now this garland covers time interval 2,6,10,14,....4*n — 2. Now we see the only time intervals left are multiples of 4. 4,8,12,....,4*n. Thus starting the next garland with time interval = 4 from 4 will cover all the time intervals. Hence we get the solution.

    Hope this helped!

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

    Take values of k 1,2,3

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

when will we have editorials for this round ??

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

Hi guys. I'm doing hack on prob.E

i used code generator

https://ideone.com/GslUJN

on following two submissions. above code generator seems generating valid input (actually hack results show that "Checker: ok jury and participant have equal answers" in both submission)

http://codeforces.me/contest/911/submission/33736718 http://codeforces.me/contest/911/submission/33726277

But the problem is that in my local environment, above submissions show different output... then, at least one hack should be succeeded. right?

But both hack failed...

is there any problem in my thinking ?

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

    There exist endl at the end of one of them. Remove it or add endl in other one.

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

      What i mean different output was "Totally different" (if you execute code, then you will know) not the existence of endl or not... anyway thanks

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

For problem D, I computed the number of pairs being reversed in a range using

(int)ceil(((float)r - l) / 2)

And to get whether this would change the parity of inversions I just mod the above expression by 2.

Can someone point the mistake.

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

    The correct formula to get the number of pairs being reversed in a range is d(d-1)/2, where d is the number of elements you are swapping ( r — l + 1 ). First number can form d-1 pairs, second one d-2, ... , 2 , 1.

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

I don't know if it's already mentioned in the comments, but here's a solution for problem G that is online and can be adapted for arbitrary-sized alphabet:

http://codeforces.me/contest/911/submission/33762818

It uses the Split-Merge Segment Trees chinese trick, where merges amortize to overall O(n * log(n)) complexity. The code is conceptually simple.

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

Editorial :/

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

It shows testing has finished. But, my solution is still in queue.

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

Regarding to message from system

Your solution 33722462 for the problem 911A significantly coincides with solutions priyanka1998/33722461, priyanka1998/33722462. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.me/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties.

Sir as you can see both solution priyanka1998/33722461 and priyanka1998/33722462 were submitted from same user priyanka1998. Sir due to network problem this error occured that when I clicked on submit button same solution submitted twice. I haven't violated any rules.

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

what the contest will be rated on # of prob. or what ?

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

Когда будет пересчитан рейтинг?

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

Excuse me.

I have an inquiry and objection about the system.

At the end of the round, the system said me that "Your solution 33733110 for the problem 911D significantly coincides with solutions physics0523/33732628, physics0523/33733110. "

I just noticed that I may made a little mistake in my program and only repair that,but the system said I did wrong,and change my submission to unofficial.

It is natural that the two submit both I made has some similar points,and,of course,I DO NOT leeking or cheating.

I DO NOT did wrong, I swear!

So,please change my submit official and Rated.

I'm sorry I'm not good at English.

[the full text of the message from the system]
Attention!

Your solution 33733110 for the problem 911D significantly coincides with solutions physics0523/33732628, physics0523/33733110. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.me/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties.

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

    Hi physics 0523. Same thing happened to me. "Your solution 33730274 for the problem 911C significantly coincides with solutions aashifkhanate/33729291, aashifkhanate/33730274. "

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

I think I just got disqualified using my own solution.

I recieved "Your solution 33730274 for the problem 911C significantly coincides with solutions aashifkhanate/33729291, aashifkhanate/33730274.". I changed the array size from 10^5 to 10^6 which may not be a huge difference to you but I was expanding my guessed solution space for problem C. Please see what's wrong here. Thanks

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

Hi, I've just got disqualified because one of my solution coincides with another user's solution (the message is below).

I want to clarify that I did not see/copy/plagiarize his solution prior writing my own solution. Our algorithms are very similar, but I assure you that's purely coincidental. I don't know what kind of evidence I can give, but I got my solution on my own, not from reading a leakage or something. I never even viewed user sazzach before.

Thank you for you reconsideration.

Attention!

Your solution 33715309 for the problem 911A significantly coincides with solutions sazzach/33713630, hypermassive/33715309. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.me/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties.

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

I have been caught in plagiarism with my own solution.

Your solution 33722840 for the problem 911C significantly coincides with solutions sdssudhu/33722503, sdssudhu/33722840.

I resubmitted my solution with some changes as I wasn't sure about my first one and since it was ICPC rules if my first one got AC the second one didn't matter.

Please help.

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

Attention! Your solution 33736695 for the problem 911A significantly coincides with solutions HunterYH/33715069, HunterYH/33736695. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.me/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. **my English is poor ** You can see both my 33736695 and HunterYH/33715069 and HunterYH/33736695 were submitted from same user HunterYH. I only submit same code twice,because at first I used GNU C++17 Diagnostics it will easy get TLE so I submit same code with GNU C++. I think I haven't violated any rules.

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

Hello Everyone, This morning I got a message from system that my submission http://codeforces.me/contest/911/submission/33725640 during the Educational Codeforces Round 35, has been found significantly similar to http://codeforces.me/contest/911/submission/33725051 and my account may get blocked due to this.

Both of the submissions were made my me for Question C, and i was thinking that the earlier one would be ignored as we have in any normal Round.

I request the community to help me out here. I have attached the screenshots for more details.

Educational Codeforces Round 35 (Rated for Div. 2)

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

Editorial?

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

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

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

Раунд, вроде как образовательный, а разбора всё ещё нет. Нехорошо.

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

do we have editorials for educationals. if yes when will they be released??

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

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

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

I know administrators are busy and this week is the New Year's Holiday, But please corresponding to the problem(the message from the system) as fast as you can...
Because of this problem,I may will miss to promotion to blue coder... Please change my submission Rated...

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

Hey,do administrators forgot this problem...?

I've not got any replys...

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

I am new on codeforces. I have much question about this bootcamp. I am from bangladesh and I am a school student, Read in 0 Level. I want to participate on this bootcamp.but I didn't understand how? is there any school student's allowed?if allowed then I want to go. But I haven't money to pay for this my family isn't have enough money. and most of I haven't any passport and paypal or anything bank account.But I want to participate on this. But How? please Help me? vovuh awoo

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

//solve of the problem

include <bits/stdc++.h>

using namespace std;

define ll long long int

define ln endl

define pb push_back

define po pop_back

define lop(i, a, b) for (ll i = a; i <= b; i++)

define lup(i, a, b) for (ll i = a; i >= b; i--)

define bs binary_search

define ub upper_bound

define lb lower_bound

bool is_possible(int n, int a, int b, int m)//this is the main part of the code...in every binary search space problem the condition part is the main .. {

if ((a / m) + (b / m) >= n)// check weather two cakes are overlaping or not
    return true;
else
    return false;

} void bz() { int n, a, b; cin >> n >> a >> b; int s = 1; int e = min(a, b); while (s <= e) { int mid = s + (e — s) / 2; if (is_possible(n, a, b, mid)) { s = mid + 1; } else e = mid — 1; } cout << e << ln; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); bz(); return 0; }