Автор PikMike, 5 месяцев назад, По-русски,

Привет, Codeforces!

В 15.05.2019 17:35 (Московское время) состоится Educational Codeforces Round 65 (рейтинговый для Див. 2).

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

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

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

Задачи вместе со мной придумывали и готовили Роман Roms Глазов, Адилбек adedalic Далабаев, Владимир Vovuh Петров, Иван BledDest Андросов и Максим Ne0n25 Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.

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

Так же от наших друзей и партнёров из Harbour.Space есть сообщение для вас:

Привет Codeforces!

Мы рады объявить об уникальной возможности получения стипендии для девушек, которые хотят изучать кибербезопасность или финансовые технологии, как по бакалаврской программе, так и по магистерской программе.

Стипендия включает в себя:

  • стипендию в размере до 10000 долларов на покрытие оплаты за обучение,
  • оплаченную поездку на саммит EMEA 28-30 октября 2019 года в Берлине,
  • наставника в отрасли, являющегося профессионалом кибербезопасности.

Подайте заявку до 30 мая, не упустите шанс учиться у нас в Барселоне!

Если у вас остались вопросы о стипендии, пожалуйста, свяжитесь с нами hello@harbour.space!

Подать заявку→

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

Место Участник Задач решено Штраф
1 Radewoosh 7 174
2 mnbvmar 7 183
3 I_love_Tanya_Romanova 6 119
4 Farhod_Farmon 6 124
5 xiaowuc1 6 142

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

Место Участник Число взломов
1 algmyr 57:-1
2 mnbvmar 16:-2
3 xavier_cai 11:-1
4 halyavin 10:-3
5 avm 7
Было сделано 291 успешных и 306 неудачных взломов.

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

Задача Участник Штраф
A Dalgerok 0:01
B Farhod_Farmon 0:05
C DieOrBreakout 0:04
D nuip 0:10
E Farhod_Farmon 0:23
F ugly2333 0:13
G Dukkha 0:57

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

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

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

Will there be a scholarship for men also?

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

Is he considered as a woman ?

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

Educational round logic :D

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

Seems this round will be started before publishing division 3 rating change xD

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

Rmind:Educational round correspond the third category in System problem something and i hope Reconciliation to All Participants

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

wait this round is dedicated to women? Then I guess its a div 4 guys shit.

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

Good luck to everyone!

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

I have no experience of rating adding in edu round :(

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

hope to become an expert = =

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

What's the difference between Div 3 Rounds and Educational Rounds besides the rating limit?

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

    Problem difficulty. Div. 3 problems are generally easier than Educational rounds.

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

      I do not agree with you my friend.

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

        I do not agree with you my friend.

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

        Div 3 are full of greedys!

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

          That's accurate, no doubt about it, but it doesn't mean dificulty in Div 3 problems is lower, at least the way I perceive it.

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

            You have compete in so much CF rounds . If we take into account what I see is you have solve max (3) problems in Educational rounds sometimes (1) and if we look into Div 3 most of the time you solve (4) problems.I am not saying that div3 rounds are so easy but it is easier than Educational rounds and you prove most of the time by solving more problems in Div3 if we compare with educational.Rest is up to you.:P

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

Typo perhaps? Paid by the University not to the.

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

I have submitted for B around 10 times it says idleness limit exceeded please help

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

    flush the print. You can read the linked page, given in problem.

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

      Why were you guys here during the contest, lol?

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

        I stuck at C so was taking a break. Still trying to understand why it is timing out. Perhaps it would be better if I jumped to D instead of coming here :)

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

          Are you using Union Find?

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

            I was using DSU with weighted Union Find. Got WA though :(

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

            Kinda, I created disjoint sets and then calculated connected components. Worked fast with my random N=500k test. Here is the solution.

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

              Hmm. Python :/

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

                It looks like my solution has a problem with cycles. I created a big sample, when I set M to 20000 it returns result in 0.2 secs but when set to 30000 it loops forever. let me convert it to a proper Union Find.

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

      Can you tell what i did wrong in this code 54197918

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

        You're using flush after second cin, not sure it effects something but delete it. In you first query you're sending "? 1 1", that returning a[1]*a[1], you need to add sqrt of that value to v (first v.pb(x)). One more thing, your solution is too crowded for that problem. After finding first number you can easily find others with a simple approach.

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

Any hint for E and F? I think F can be solved by divide and conquer, but I don't know if my idea is correct..

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

    I think E is related to finding the inversions in the array but couldn't improve the time complexity from O(n^2)

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

      You can use 2 pointers because it is monotonous. I used binary search and got WA on test 57 but not sure if the method is wrong or i have a bug.

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

    For E: Fix l, starting from 1 to x. The idea is similar to 2 pointers and you will need some precomputated arrays.

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

    Precalculate p[x] = are numbers <= x sorted, s[x] = are numbers >= x sorted, l[x] = max number <= x, f[x] = min number >= x, you can check if (l, r) is good in O(1), just do binary search.

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

    F is just counting the coefficient of each $$$b_i$$$. You can process the $$$b_i$$$'s in sorted order and use a BIT to efficiently count how many terms smaller than your current $$$b_i$$$ are in a range, and their contribution to the coefficient.

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

      Actually there are $$$O(n^2)$$$ range pairs, and I got stuck on this ranges. I try to consider left range and right range separately, but I cannot figure out how to count that for each i efficiently.

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

        Say you're processing the ranges containing $$$a_i$$$. These are $$$[l, r]$$$ with $$$l \le i \le r$$$. If $$$a_j < a_i$$$ and $$$j < i$$$ then you add $$$1$$$ to the coefficient for each of the ranges that contain $$$a_j$$$. The right endpoint doesn't matter, so for each right endpoint $$$a_j$$$ is contained in $$$j$$$ ranges, and the total contribution to the coefficient is $$$j \cdot (n - r + 1)$$$, the latter being the number of right endpoints. You can get a similar expression for $$$a_j < a_i$$$ and $$$j > i$$$. To query efficiently you can build a BIT that allows you to get the sum of $$$j$$$ for $$$a_j < a_i$$$ and $$$j < i$$$, and another one for the right side. Then when you finish processing an element, you add it to the BIT.

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

please anyone show his code for problem B in c++14 PLEASE...

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

Has someone's nlog^2n in E passed? I kept getting TLE on test 6. I binary searched the r for each l. Edit: Passed after I dropped a logn.

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

    I was thinking on similar lines but wasn't that n^2 logn? How fast do you test if a particular l,r is valid?

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

      No that is not n^2logn. What you are thinking is to check all possible (l,r) pairs whether it gives non-ascending array or not. Correct idea would be to get minimum r (using bs and some preprocessing) for each possible l (1..n) and adding n-r to the ans.

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

      No, what I did was to fix a particular l. Then calculate the first 'r' such that [l, r] is valid. Then added n — r + 1 to the answer. Check my code here. I maintained the max prefix and suffix till the array is sorted for calculation.

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

How to solve B?

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

Hello, I tried solving problem C and I was getting runtime error on test 3. I could not find the error, can someone help me please? Here is my code: http://codeforces.com/contest/1167/submission/54204878

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

What is test 57 on problem E?

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

What's with the super tight bounds in F? My O(n log n) solution takes 1996/2000ms. 54195181

Happy hacking :P

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

My code WA test 1???? 54208002

check the answer on CodeBlacks why this code Run on Codeforces get "WA" and this test example is test one !!!

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

The problem D inputs by "cin" will get "WA" ,replace "scanf" get "AC" ,why??

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

among 8 div2 participants eho is better than me 7 of them are fake accounts. it is unfair lol i should be the 2nd, not 9th

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

[submission:54208002]This code "WA" test 1???

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

Is in problem E wrong to do binary search? Isn't it the same as 2 pointers?

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

What a pity! For E, cin/cout got a TLE while scanf/printf passed.

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

    Input/Output speed is not a problem because I also used cin/cout in E and pased. You just need to add ios_base::sync_with_stdio(0) to make cin/cout as fast as scanf/printf.

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

      Thanks very much. Indeed, with sync_with_stdio(0) my solution passed. But it still has a gap with scanf/printf.

      For cin/cout with sync_with_stdio, it takes 1606 ms. While for scanf/printf, it takes 1278 ms.

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

C and D were easier than B.

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

Why did my solution to problem D gave TLE: code

Removing stack and converting string to character array passed the pretest. Don't know why..

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

    Because adding two strings is linear to their length. If you just push the char in the end is O(1). Changing it with += that equals to push_back it gives acc 54211273 (your sub with this change)

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

Authors should have announced that there will be interactive problems in the contest beforehand.

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

    Why?

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

      Many of Division2 participants didn't have any idea about interactive problems (I am also one of them). Because usually div2 contests doesn't contain this type of problems. To know and learn about them all on a sudden in a running contest is taught and time consuming.

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

        There is nothing to learn, interactive problems don't differ much from usual problems. My first interactive problem was on NEERC 2010, I had green level then but I solved it without any difficulties. I don't understand why so many people are afraid of interactive problems.

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

Any hacks available for problem (B) ?

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

Thank you creators for such cool problems. I really enjoyed it.

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

why this solution(54181282) is getting wrong answer on testcase 2?

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

Is it possible to solve C with a method other than Union Find?

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

Why was problem b hacked?

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

why this https://codeforces.com/contest/1167/submission/54206553 is getting runtime error ?

I did it like the blog example :(

using same code but with cout<<flush is accepted

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

is D the simple stack implementation ?

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

    You can also solve it recursively, by using the fact, that all valid sequences S = (A)B, or empty.

    54212912

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

    Yes. Actually, you just have to invert the color before processing a '(' and after processing a ')'.

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

      @MMXIX can you explain your approach in detail,and how does reverting colors gives us required answer

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

        You have to minimize depth, so as you encounter two same brackets in sequence invert your color . This will minimize the depth.Simple greedy approach.

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

      Thanks for your comment. I did this in the same way and got accepted but I was in doubt as it 'D' problem.

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

Was O(N logN) supposed to pass on E? I got TLE on test 50 with such an approach. If it was intended to pass, why set the bound as high as 1e6?

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

    There are O(N) solutions using 2 pointers. However, I think only simple O(NlogN) solutions passed (binary search).

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

I don't know what is the hacking format of interactive problems.

Somebody help me with an example,please.

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

The problem B could be more interesting if the number of elements would be greater.

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

The problem B could be more interesting if the number of elements would be greater.

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

    Yeah, it would have been better if the number of permutations were too large for all of them to be checked.

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

xx

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

    memset gives wrong answer and loop initialization got Accepted.

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

    sizeof(vs) is a constant value, you have to multiply it by the size of the array.

    Correct command would be memset(vs, false, sizeof(bool) * (n+1)) because type of elements in the array is bool. sizeof (vs) will typically be larger (8 bytes) than sizeof(bool).

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

    vs is a pointer, sizeof a pointer is generally 4 bytes (8 bytes for x64 compilation).

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

Can anyone explain their approach of solving problem D?? I am not able to make up any thoughts about it

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

    let r0 be the nesting of string with color 0, similarly define r1.

    Initially, r0 = 0 and r1 = 0.

    now ,each time you encounter an opening bracket, if r0<r1, color this bracket 0 (also increment r0)else color this bracket 1 (also increment r1).

    Similarly, each time you encounter a closing bracket, if r0>r1, color this bracket 0 (also decrement r0)else color this bracket 1 (also decrement r1).

    This guarantees that both strings will be balanced bracket sequences because r0+r1=nesting of original string =0 and r0 or r1 can't be negative (because we ensured it in the loop above) so r0=0,r1=0.

    This also guarantees that max nesting is minimised because only the min is incremented when encountering an opening bracket (always better than incrementing max) and the max is decremented when encountering a closing bracket (always better than decrementing min).

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

can someone please explain approach to question D??

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

The judge doesn't judge.

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

Why is Codeforces so slow after every contest? My past 3 submissions in the virtual contest have not been judged.

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

What is the approach for F?

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

    For fixed i, find all j's with (a_i >= a_j), then answer will be the sum of min(i + 1, j + 1) * max(n — i, n — j). Go through i's in increasing order and maintain several fenwick trees.

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

I'm very confused. Can someone please explain how to solve E? I have been reading multiple AC solutions but still can't understand the idea behind that!!

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

    Save the maximum index and the minimum index of each different elements in a. Then think of how to judge a f(l,r) is valid or not in O(1)

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

In problem C, I'm using DFS and getting a TLE in 7th test case. Can anyone help?

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

    Maybe you are not building the graph in an efficient way. Suppose you have 2 5 7 9 Then you don't have to do

    2->5->7->9
    5->2->7->9
    7->9->5->2
    9->2->5->7

    Instead do something like
    2->5
    5->7->2
    7->9->5

    You don't need to make exact graph as you only have to count connected components.

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

    you can skip visited groups

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

It would be nice, if someone please explain me the problem C using sample Case. I didnt figure out it yet for a while xD. Thanks in advance <3

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

    Lets take first case there are 5 groups and 7 people. Each of 5 rows starts with some number that means how many people in Ith group. For example in first group 3 people with number 2, 5, 4 and so on. And problem says if person sends news, their friend can also send info to their friends. After this if person in this group he can share news to this friends and if this friends in other groupes they can share news to other friends in that groupes. At the end we can say that we need to find every component and people in this component can share info with this size of component(including himself). First case if we take person with number 1 he is in two groupes {1, 2} and his friend 2 is in group {2, 5, 4} and if we add this two groups its {1, 2, 5, 4} everyone can share new with themselves that means 4 is the component size. You can solve this problem with dfs or dsu)

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

      You said: "First case if we take person with number 1 he is in two groupes {1, 2} and his friend 2 is in group {2, 5, 4} and if we add this two groups its {1, 2, 5, 4} everyone can share new with themselves that means 4 is the component size."

      But My point is it should be.. if we take person with number 1 he is in two groupes {1, 2} and his friend 2 is in group {2, 5, 4} and{2, 6, 7} and if we add this three groups its {1, 2, 5, 4, 6, 7} everyone can share new with themselves that means 6 is the component size." Can you please clear my confusion. Thanks xD <3.

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

        2 6 7 doesnt mean fifth group contains {2, 6, 7} first number means how many people in this group, in this example 2 people in fifth group with numbers {6,7}

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

          Oh hoooo. Thats clearly show how bad I am in problem statement reading. But Thanks a lot xD. Take love <3

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

could you help me check where is wrong? ID:54220798

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

In E, is it okay to find the max l value and min r value such that l<=r , and f(l,r) is valid. Then we know that f(l-k1,r+k2) is also valid for all possible values of k1 and k2.

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

    That is true but not enough. For example, leaving one element only inside leaves array sorted, if l != r, then we can leave l + 1

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

      couldnt understand

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

        I mean, what if l = n and r = 1. Which max l value and min r value do you choose? If you iterate all, then you count some segments several times.

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

          but l<=r

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

            What about this case. 1 4 2 5. f(4, 4) = 1 2 5. it is valid and we cannot make l bigger or r smaller, because then l > r. So you are saying that all f (4 — k1, 4 + k2) are true for positive k1 and k2, as I can tell. Well that is right. But we also have f(1,2), for example -> 4 5. And it is not of this form, 4 + k2 = 2 so k2 is negative.

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

              Oh, I understood. So you mean that 4-k1 and 4+k2 is correct but it leaves out other cases... because l is unable to become greater than 4 and r unable to become smaller than 4.... Is this what you meant?

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

Why using Dfs to get number of nodes in each connected components gives wrong https://codeforces.com/contest/1167/submission/54223559

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

    You are assigning the value of c to val[i] while running dfs, c being the number of connected components, this doesnot ensure that the parent of all these components is 'i' and therefore the answer is coming out to be less than than the actual number of components. Just a little bit of change and there you go..!!! 54225792

    PS-- This might give you TLE in system tests as you have not used weighted dsu.

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

Hope that I can reach 1600, it is only 12 ratings away but it seems that I am not performing well this time... Btw I really appreciate problem B as an interactive task, as we don't get to meet them often and this is a great opportunity to train up skills related to interactive tasks.

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

I'm new here. Are these contests are Python friendly? Most people solved C with Union Find in C++ and passed the tests, but the same algorithm in Python gets TLE

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

    In div2 and div3 (and most div1) problems can be solved with Python. With medium plus problems, if there is too much list reading or query you will need Pypy3. There are lots of difficult problems looks impossible with Python but we're far away from them (I'm trying to solve some of them on Codechef and even with 5x time limit it's still a big challenge, my current problem). And here Python solution for C: link

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

      Thanks, the key was to change input() to sys.stdin.readline() https://codeforces.com/contest/1167/submission/54233244

      Anyway it's strange that the time limit for python and c++ is the same number.

      And why do you need work with stdin? In real life in 99% you need to write class of function, so why not just give a prototype of the function or class that you need to implement?

      def solution(n: int, m: int, lines: List[int]) -> List[int]:
          """
      
          :param n: number of users
          :param m: number of groups
          :param lines: number of users in group + users in group
          :return: the number of users that will know the news
          """
      

      Sorry for my questions, I'm new here.

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

        Actually you're right about writing a class of function, but here I most time coding what I need for current problem. I'll use libraries if I go up in rank :) For stdin, I only use it when there is lots of reading like in that problem.

        Don't worry about time limit, it's something classic CP thing but Codeforces gives extra time for problems. You'll start to need C/C++ solutions if you become a Div1.

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

    See solution of @algmyr he passed the problem probably with union find

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

Мне пришло сообщение о том, что мое решение значительным образом совпадает с решением других четырех участников раунда. В своем решении я использовал код дерево Фенвика из своего репозитория, который находится в открытом доступе (https://bitbucket.org/mibig/algo/src/master/fenwick_tree.cpp).

Также я использовал ideone.com. Я очень виноват, что использовал этот онлайн-компилятор. Но я никоим образом не планировал нарушать правила Codeforces. Я был в гостях и увидел, что начался раунд, а на компьютере не было среды разработки, поэтому просто позабыв о том, что нельзя использовать онлайн-компилятор я нарушил это правило, из-за большого желания принять участие в раунде.

Прошу меня простить и не совершать блокировки моего аккаунта или других штрафных санкций.

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

    Я завел аккаунт на ideone.com. Теперь такое не повторится.

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

I wonder when I can see the ratings changing...

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

Easy busy contest

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

Why Radewoosh's submit 54183325 didnt get TLE? In his solution (sorry for my poor English) he didnt use rank's heuristic and got AC. I tried to submit solution without rank's heuristic and got TLE 54233682 . Could someone help handle it, please?

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

    And im about problem C.

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

    Because he used a technique called 'Path Compression'.

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

    In his code

    int fin(int v)
    {
      if (v!=oj[v])
        oj[v]=fin(oj[v]);
      return oj[v];
    }
    

    not

    int fin(int v)
    {
      if (v!=oj[v])
        return fin(oj[v]);
      return oj[v];
    }
    

    So after a fin(v) operation, the nodes on the path from v to the root will all directly connect to the root.Therefore, when you perform fin(i) (i is a node on the path from v to root) will just return oj[i]

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

Wait for tutorial

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

I have passed problem G, but I have no idea whether my solution has a right complexity.

My solution is 54235792. It uses a method similar to two-pointer to find the nearest pair that is the same far from point x.

Could someone please tell why it's correct or construct a data that will lead to a TLE?

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

I got compilation error on problem D during system test after it passed during the contest? How is that? :D

54189857

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

Here is my $$$O(N)$$$ solution for problem E: 54241182

The general idea is to maintain, first of all, a global rightmost $$$L$$$ and a global leftmost $$$R$$$ such that ranges $$$[1,L]$$$ and $$$[R,X]$$$ are valid, then for each $$$r$$$ the rightmost $$$l$$$ such that the union $$$[1,l] \cup [r,X]$$$ is valid too.

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

Used DSU for problem C, got WA test 3 and I cant find the mistake, can anyone help? 54184178 Edit: Found the error, I was not checking if nodes are already connected before connecting them.

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

    same for me.
    then I used dfs and it got ac.
    I don't know what is the mistake.

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

    I also got WA test 3. You should check in your connect function that you don't connect the same element.

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

Hello, I tried solving problem C and I was getting TLE error on test 3. Somebody please help in optimizing my code. I didn't get the editorial properly. Here is my code: https://codeforces.com/contest/1167/submission/54269390

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

    The answer is the same for vertices in same connectivity component. You dont need to clean the array.

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

How to solve problem G?

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

can any one explain E problem please ?

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

problem D, solution1 got accepted whereas solution2 gave TLE. The only difference between the two is in line number 21. In solution1 we append 0 in string by res+='0'. In solution2 we append by res=res+'0'. I thought these two operated the same way. Can someone give insight to the reason?

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

Someone please help me with problem C. I am getting MLE. Any help would be appreciated. https://codeforces.com/contest/1167/submission/54526141