Блог пользователя Vovuh

Автор Vovuh, история, 5 недель назад, По-русски,

<almost-copy-pasted-part>

Привет! В 24.07.2019 17:35 (Московское время) начнётся Codeforces Round #575 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач (или 8), которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты — так же как и вы буду расстроен, если у многих попадают решения после окончания контеста.

Вам будет предложено 6 или 7 (или 8) задач и 2 часа на их решение.

Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

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

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацию моей работы. Спасибо моим очень хорошим друзьям Михаилу PikMike Пикляеву, Максиму Ne0n25 Мещерякову и Ивану BledDest Андросову за помощь в подготовке и тестирование раунда.

Удачи!

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

</almost-copy-pasted-part>

UPD: Я также хочу отдельно поблагодарить Ивана BledDest Андросова за помощь в подготовке задач, а также danya.smelskiy, greencis, chenjb и STommydx за тестирование раунда!

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

UPD3: Я также хочу поблагодарить моего друга Максима Ne0n25 Мещерякова за улучшение тестов задачи F! :D

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

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

Sofa!

Vovuh makes a lot of div3 rounds!

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

If you are to say "You will be given 6 or 7 (or 8) problems" to the notice, why don't you announce exact number of problems later?

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

Nice! A round just for us newbies.

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

Ура,я так ждал этого момента!

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

How can a normal round be ICPC rules!

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

Hope the statements are easy to understand.(I understand the problem wrong for too many times!)

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

Vovuh: Announces a new Div. 3 round
Me: Aw shit, here we go again...

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

Thanks to Mikemirzayanov for this great platform. You are doing a tremendous job. making 2 or 3 Contests almost in every week.. :)

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

MikeMirzayanov, after some updates on Codeforces when I copy my code into IDE on every empty line there is a strange symbol which brokes my compilation. Is it going to be fixed?

Maybe anybody had such problem, how did you fix this? I use Codeblocks. Few time ago there wasn't such problem :(

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

    It is not an error.It is a common thing,but yeah it causes problems for most of the users. In sublime-text i paste the code with Ctrl+Shift+V and it works for me

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

    I'm also facing the same problem. Whenever i try to copy my code from CF using copy button and paste it on by IDE , the code doesn't compile. However , when i copy my code manually using cursor the code does compile. Strange.

    MikeMirzayanov , please fix this.

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

    I ran into the same issue. If you're on Linux/Mac you can use perl -pi -e 's/[^[:ascii:]]//g' to strip all non-ASCII characters from a file.

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

Hope the statements are easy to understand and very short.

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

i wish this round will be a real div3 not a hidden div2

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

I wanna be blue.

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

Я тоже собираюсь создать контест 3 дивизиона из 6 задач.

И меня беспокоят несколько вопросов, не могу найти на них ответы. Надеюсь на помощь опытных в составлении контестов и отправке на ревью

  1. Какой должен быть минимальный уровень последней (самой сложной) задачи?

  2. Через сколько месяцев можно ожидать ответ (какую-нибудь информацию о том, что мой контест увидели) ?

  3. Если мой контест не понравился, обязаны ли мне сообщить об этом или могут месяцами молчать как рыба?

  4. Как указать, что раунд div3? потому что там только 1 и 2 див

  5. Может ли рассматриваться задача, предложенная в одиночку, не в составе контеста? (могут ли её пристегнуть к какому-нибудь сборному контесту)?

Заранее спасибо за информацию

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

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

Только в спортивном программировании девушка весом 1000 кг может быть самой красивой

Зто задача 741B - Хрупкий амфитеатр Arpa и ценные девушки Mehrdad, я не смог кинуть скрин по техническим причинам

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

Как здесь вставлять скриншоты?

Я как только не пытался его всунуть, и в ВК его добавлял, и на гугл диск, и даже через файлообменник не работает

Кто постит мемы, прошу подскажите!

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

Serouisly!!!! This is supposed to be a Div3 Round?

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

Queryforces!

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

wtf this is harder than a div2 contest

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

How to solve problem C?

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

    Make a variable to store the area where any robot can get. This area whould be a rectangle, so just store x and y of left bottom angle and x and y of the right top angle. Next for the first robot get the area where it can get. In python it would be like this:

        if r[0][2]:
            pos[0][0] = -100000
        if r[0][4]:
            pos[1][0] = 100000
        if r[0][3]:
            pos[1][1] = 100000
        if r[0][5]:
            pos[0][1] = -100000
    

    where r is the array of all robots an pos is an array in shape of [[x0, y0],[x1, y1]]. Set all robots reachable area as first robot's, because we've checked only one so far. Now get the same area for all of the other robots and compare it with all robot's area:

            if robot_pos[1][0] < pos[0][0] or robot_pos[0][0] > pos[1][0] or robot_pos[1][1] < pos[0][1] or robot_pos[0][1] > pos[1][1]:
                print(0)
                break
    

    This huge line can't even fit the screen, but it checks if current robot's area intersects with all robot's area somewhere. And if it does, then set all robot's reacheble area to this intersection area:

    pos[0][0] = max(robot_pos[0][0], pos[0][0])
    pos[0][1] = max(robot_pos[0][1], pos[0][1])
    pos[1][0] = min(robot_pos[1][0], pos[1][0])
    pos[1][1] = min(robot_pos[1][1], pos[1][1])
    

    And then if our loop through all robots didn't break, then it's possible for all robots to reach a single point. It's any point in their area. 57687425

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

    Keep the four variants: min_left, max_right, min_bottom, max_top

    if f1_i = 0, min_left is not less than x_i

    if f2_i = 0, max_top is not greater than y_i

    if f3_i = 0, max_right is not greater than x_i

    if f4_i = 0, min_bottom is not less than y_i

    if on i'th iteration current value of some of four variants don't meets this conditions, update this variant

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

    My thanks to Vovkaez and to kazak. I almost got it during contest, I changed some conditions. FeelsBadMan

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

Good problems, have to sweat in each problem but it was nice. The round more resembles div2.

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

So, how to solve D2?

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

Hi guys,

In Problem C, even O(n) complexity algo is getting time limit exceeded. Can someoone help here, please ? http://codeforces.com/contest/1196/submission/57694392

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

I got 3 of them :(

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

    I just finished 1 of them which makes me so sad,how can i finish as many problems as possible?

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

      You just gotta keep practicing bro. I was in your position a year ago but this time I managed to solve all but the last one. Just keep at it!

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

        Any more details on how you progressed during the year?? Would be helpful to know...

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

It was similar to D2. How are the questions difficulty supposed to be? Div 3 B = div2 A? Div 3 c = div2 B?

Also how to solve D1 & D2?

Overall good contest..

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

    There is 3 type we can do $$$RGB, BRG, GBR$$$ and for every $$$i$$$ $$$mod$$$ $$$3$$$ position we need to check if this position equal to that $$$3$$$ substrings, because of it we create $$$3$$$ counters which counts all positions where $$$i$$$ $$$mod$$$ $$$3$$$ of string is not equal to the position, and for D2 we just need to find $$$pref[i] - pref[i - k]$$$, because its like we adding one letter by deleting first letter, to understand it you can check my solution 57672041

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

Python don't work for D2, :'(. Got penalty and had to rewrite code in C++.

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

    Same here. Had to rewrite B too, though I optimized it in C++. But D2 was exact translation.

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

      Hey vsinha! Would you like to try my previous comment and submit the python code for D2 and B again to see whether it now satisfies the time limit?

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

        It worked. I resubmitted D2 and it got AC. Thank you very much for the tip. I'm not submitting the python version of B, it perhaps suffers more from a poor algorithm than IO limits.

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

          =) I think for B as long it is an O(n) algorithm, it should work perfectly

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

    Hi islingr! I looked at your D2 python code. Do you want to add the lines

    import sys
    input = sys.stdin.readline
    

    on the top of your code and submit it again to see whether it will now satisfy the time limit?

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

I really liked problem B, spent ~ 5 attemps to understand that i need change int->ll

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

    how to slove it ?

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

      You can calculate remainder of sum on prefix, if you find some place where remainder is odd, add it to answer and say that now remainder is zero(we calculate remainder of sum on prefix from that position). Now leave first k-1 elements of that array add n to answer and check that all ok. All ok if sums on that subarrays is odd and answer have size equal to k.

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

        you're right,it seems simple,but during the contest,i thought the way,however i couldn't prove it,so i try to dfs it,which got me into trouble. What a sad evening....i can't fall asleep.

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

      Here is my code

      I initialized an array of size n; then, for each element, I determined if it was even or odd, and kept track of the total number of odds. If it was odd, I would mark that array with a "1"; if it was even, I would mark it with a "0".

      Now, if the number of odds % 2 doesn't equal k % 2, or the number of odds is less than k, I printed NO.

      Otherwise, print YES and print every index of an odd number and keep subtracting from k until you have one left; then, just print n as the index.

      I'm bad but it worked.

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

        I was also doing the same , don't know what's wrong with my soln

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

          got it . I was failing at test case like this when last element was not odd . 1 10 3 2 3 9 4 6 4 2 5 8 8

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

For Problem C:

I sorted according to X then according to Y and found intersection point for X and Y.

The intersection point will be a point for which on left side all robots are coming towards it or equal X coordinate and on right of it all robots should be coming towards it or equal X coordinate.

Same thing for finding Y coordinate.

Am I missing some corner case here ? As I was getting WA on test case 5.

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

Were there any scoring table on the right side, there were not for me.

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

anyone has a good explanation for problem E before the editorial shows in the next era? :)))

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

    Assume b>=w (you can shift all squares over if needed). Make a line bwbwbw...bwbw until you run out of w's. Then you can place the remaining b's by connected them to the top or bottom or left of this line. If there are still b's left, it is impossible.

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

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

I think k can be $$$ 10^5 $$$ in problem F and you can see my solution.

https://codeforces.com/contest/1196/submission/57688661

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

During the contest, for Div2-B, I thought that the only condition for "NO" answer is

if((k%2==1 && sum%2==0) || (k%2==0 && sum%2==1)) pf("NO");

Here sum is the sum of all numbers in the input.

Now I added another condition for "NO" which is ans.size()!=k and it got accepted. Can someone give me a testcase which can help me understand this behaviour?

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

Any hints on how to solve Problem F?

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

    You can see that if you sort all edges by weight, the k+1 edge and another that weight more than k-th aren't in our answer(forger for them). Now you have k edges, up to 2*k vertices have at least one edge, and you can run Floyd–Warshall_algorithm for vertices which have edges and get AC.

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

    You will need to use Floyd-Warshall's algorithm to solve F. Its asymptotic time complexity is O(N^3) and space complexity is O(N^2), so you cannot employ it right away.

    However, there is one thing you need to notice: if a path is k-th in the final sorted distance matrix, it will not include any edges that are longer than the k-th shortest edge given. (Agree that the k-th shortest path is obviously not longer than the k-th shortest edge, at least because the set of edges is a subset of all paths and we already know k — 1 one-edge paths shorter than k-th edge).

    Now sort all the edges and pick out only k shortest ones. Compress the coordinates and create a graph consisting only of these edges.

    Run Floyd-Warshall's, which will have the asymptotic time complexity of O(k^3).

    Slice the distance matrix you're running Floyd on across the diagonal. Find the k-th minimum on any of these slices (they're the same). Output the result.

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

Dafuk is wrong with me Spent 1 hour on C and 17 minutes on D2 and D1

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

Is there some added advantage on asking query-based test cases? Do they do it so they can test on more cases this way?

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

    From what I understand it's purely for ease of judging

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

    I think questions based on online queries ( and even offline ) pose kind of a challenge to the solver compared to the other type because of vast number of queries to answer in such small amount of time and is more practical i think ? Hope the answer helps!

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

      Are you saying that having several separate test cases is worse than having the same test cases compiled into a single query-based test case?

      I'm assuming that the former works by generating a single output file from the code and running it several times. The latter would work by running the same output file only once in this case. But even then I don't see how there would be a significant benefit from doing this.

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

        No, sorry for any misunderstanding, what i meant was that sometimes query based questions require a more algorithmic or cunning approach compared to the ones which doesn't. But i cannot say the same in this contest though(Though i agree that many might disagree with me).

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

          Yes, that makes sense if the tester is expecting an $$$O(1)$$$ or $$$O(log n)$$$ solution. But I suppose for $$$O(n)$$$ and $$$O(n log n)$$$ solutions, it hardly makes a difference.

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

Someone really wants to get their opinions established in D2

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

https://ideone.com/SSYGpq please check my code.. Time limit exceeded on test 3 but i don't find any reason.

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

Any suggestion how to solve F, without Floyd–Warshall_algorithm? I solve it by Floyd–Warshall_algorithm, but I belive that exist some quite good idea how to solve without Floyd-Warshall_algorithm, maybe for k<100000

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

Blin! I don't solved B, where odd subsegments, cos i forgot to write 0LL in accumulate(a.begin(),a.end(),0LL), i wrote accumulate(a.begin(),a.end(),0). This is obidno!

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

    Sometimes such shit happens. But do not be upset.

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

      What is your most offensive error or stupidness in contests? (My subj is here)

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

        I build segment tree with vector in parameters, get memory limit and I spend a lot time to see that so bad, because vector each time copied.

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

Please notice these two codes 57693377 and 57690563, (2018030102067 and Mole_Q) i think they are cheating. 57676867 and 57674699 2018030801054 and 2018030401051 are similar, too.

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

57693377 and 57690563 i think they are cheating.

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

How to solve problem E ?

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

    if(B>=W) build such structure bwbwbwbwbwbwbwbw after you can add b to top or to bottom or to left if you add all and you must add more answer is no this is case (B>3*W+1) else same things as B>=W but swap white and black

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

    I think it can be solved like this : Think of it like a tree , just with this constraint that the tree cannot have more than 3n+1 of the colored nodes which are in majority.By drawing 1 or 2 configurations, you can realize that to get maximum number of nodes of the majority type, one of possible tree is a straight one.So if you select minority nodes = a, then connecting those must be a-1 majority nodes, and the rest can be taken till we fill the required quantity of majority nodes! Hope it helps!

    Consider the picture for example( :D) : Link

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

2018030401093 2018030801054 Mechorca Maybe they are cheating

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

Mechorca 2018030401093 2018030801054 maybe they are cheating

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

I am just wondering, what is the purpose of hacking in a round where the tests are strong ??

I'm not saying that I want what happened in Educational Codeforces Round 67 (Rated for Div. 2) to happen again, but won't it be more fun if there was a problem that has a test where everyone forgets about ?

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

Couldn't solve E due to lack of time during the contest. Now realizing, easiest E ever??

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

Why does a BFS solution of E fail while one with DFS pass?

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

    i think it should solve with Dfs because we need to go deeper in a chain not by level so it make sense to use Dfs not Bfs

    if we go by level then maybe there is some cells that have a common cell with white color (if white is the greater one)

    i can draw something if you don't understand :)

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

Кажется, авторы div3 учли свои ошибки и, наконец, составили одекватный по сложности контест. Респект таким ребятам.

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

I cant make sure about this, but I wonder if this k shortest path routing can be used to solve problem F or may be Im wrong, let me know your thoughts. Why I know this? Because this was a topic for homework at my uni, and I chose this approach to find k-th shortest path in a weighted graph.

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

Big day for Codeforces. We set a new record. The total number of registered users on Codeforces Round #575 (Div. 3) is 12619! Our servers are ready for more. Let's see what happens next!

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

if e can be solved by bfs? help me !! 57713663

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

It is really frustrating that a O(n) solution written in Python3 (PyPy) can exceed the time limit for problem B!

It seems that I am only reading in the values of n, k, l, and doing constant time comparisons in case of 200000 queries. Does anyone know any trick of how I can change the syntax to reduce runtime? I am attaching my code. Thank you!!

Python Code for Problem B

q = int(input())
for _ in range(q):
	n, k = list(map(int, input().split()))
	l = list(map(int, input().split()))
	if n == 1:
		if l[0] & 1:
			print("YES")
			print(1)
		else:
			print("NO")
	else: 
		s = sum(l)
		if k % 2 != s % 2:
			print("NO")
		else:
			p = []
			cnt = 0
			for i in range(n):
				if l[i] % 2 == 1:
					p.append(i + 1)
					cnt += 1
					if cnt == k:
						print("YES")
						print(*p[:-1], end = " ")
						print(n)
						break
			if cnt < k:
				print("NO")

Update: It seems that using sys.stdin.readline() is much better than input(), right?

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

For E I had used ideone not knowing that it was public. Somehow it looks like others have managed to submit my own code to E before I submitted it. I don't know what has happened and am very concerned. I do not know how to prove it but perhaps if you look at code style you can see that it is my code?

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

    I apologise for mistake with using ideone, I did not know it was public in this way. Will not use in future.

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

      Specifically, the void sol() function I use in all my submissions for the contest while none of those copying off me have used it in other solutions.

      I sincerely apologise for the trouble that my use of ideone caused.

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

I'm not able to understand problem E properly. I mean if b=1 and w=5 why can't the answer be (2,1),(2,2),(2,3),(2,4),(2,5) since this is also a connected component.In this way answer should always be possible.We can print b & w coordinates in this linear fashion. Please help inspite of trying hard i'm unable to understand the problem.

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

    if b = 1 and w = 5, you need to output 1 black cell and 5 white cells, so in a total of 6 cells. However, you only have 5 cells. In addition, (2,2) and (2,4) are white and (2,1), (2,3), (2,5) are black, so you actually have 2 white and 3 black instead of 5 white and 1 black.

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

    For chessboards, adjacent cells should have different color, and it is stated that (1,1) is painted white. Your answer is connected, but (2,1) is black, (2,2) is white, (2,3) is black, (2,4) is white, (2,5) is black, which is 3 black and 2 white. one black cell can have at most 4 adjacent white cells, so the proper answer for b = 1, w = 5 is "NO"

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

A very truly great contest for rating less than 1600. All problems were of good quality. Enjoyed the problems.Please make Div.3 like this only.