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

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

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

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Вам будет предложено 6 или 7 (или 8) задач и 2 часа на их решение.

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

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

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

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

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

Также спасибо ashmelev, Vladosiya, mesanu и I.AM.THE.WILL за тестирование раунда и полезный фидбек по задачам!

Удачи!

UPD: Обратите внимание, что задачи раунда частично пересекаются с задачами Внутривузовской олимпиады Саратовского ГУ по программированию. Если вы участвовали в олимпиаде, то воздержитесь от участия в раунде.

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

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

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

Good luck everyone!

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

omg vovuh div3s are back!!! :D

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

Yes, I hope no smurfs and good luck to everyone!

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

Best way to celebrate my birthday!! Vovuh's Div3s are lit!

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

I have been participating in Div3 for quite a long but this contest never went unrated for me. I wish it doesn't happen again after this contest.BTW, Best of luck everyone.

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

Best Wishes everyone for the contest and Happy Eid to all of you.

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

vovuh, welcome back

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

I have a question why some of the announcements don't give us exact numbers of problems?

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

    I think because they don't have a final problemset yet, maybe because they have 8 or more problems made but they are not sure which problem to put on 1-2 places, and they will decide later

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

hopefully i get specialist yoooo

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

Eid Mubarak today

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

Did someone notice, its Codeforces Round #786(the holy number) on the eve of Eid-al-Fitr!!! Such coincidence Much wow!

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

vovuh welcome back in div 3s

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

welcome back in div 3s, vovuh

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

You will be offered 6 or 7 problems (or 8)

or 9

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

Eyeing specialist from a distance 0_0

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

Hope I will be specialist after this div3 contest!!!

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

I want be specialist after this contest.

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

vovuh welcome back

please make the time of the contest 2 : 15

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

Long time these authors have not done div 3. All good solutions!

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

I think this will be a div 3 round.

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

Very Bad contest

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

Marinush

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

Why there is not any example or description note for test cases in problem F... can't really understand the test cases :(

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

Spent 30 minutes to understand F :(

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

I has closed div 3. Very good problems! Upd: hacked E :(

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

I think D is the hardest problem :))

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

    what was your approach? I tried like this but failed — the pairwise mins in array A must have an increasing order. for odd n the pairing excludes the first element, but it has a constraint to be the smallest integer.

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

      sort each pair of (N, N — 1), (N — 2, N — 3).... and check if you can get sorted array. your solution does not work for 2 4 3 5.

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

    Orz

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

G is a simple but educational problem. Hope there will be more problems like this in the following div2/3 contests.

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

    Can you explain it please?I think it's the longest path in the graph after deleting some edges but there are some cases that I choose edges that I shouldn't

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

      It's a simple dp problem where you first topsort the vertices, and then for each vertex $$$u$$$ with in-degree greater than 1, you iterate over the parent nodes $$$v$$$ ($$$v \rightarrow u$$$), and if the parent node has out-degree greater than 1, you update the dp value as $$$dp_u = dp_v + 1$$$.

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

E — Breaking the Wall, Wrong answer on test 32. What was that?

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

can u unfreeze the standings + let us submit

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

Interesting tasks and good round! Thanks :)

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

I did'n noticed that problem G statement:'a valid directed acyclic graph', I tried tarjan to shrink strongly connected components into points (poor english).Although it was unnecessary, I'm just wondering if this algorithm would be correct without such a condition.I would be grateful if someone could help me.

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

Why results are frozen?

I can't submit((

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

How it should work? It just reloads the page

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

I spent 40 minutes on D and got TLE because I'm using native linked lists, there is no way you wanted me to implement an optimized liked list for this right?

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

    Nope, note that you can only change the relative order between two elements after sorting ($$$a_{n} \leftrightarrow a_{n - 1}, a_{n - 2} \leftrightarrow a_{n - 3}, ...$$$)

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

    you don't really need to do the operation.

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

      can you explain how to calculate it then please

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

        do some simulation and you will find you only can pairwisely revert elements from the right side.

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

vovuh rocks!!

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

anyone explain F pls

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

    remember the total number N of current icons on the screen, and the number of icons in the first N cells. The result is the difference between them. Use fenwick tree to find out the second value.

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

      Actually there is no need for a Fenwick tree. You can simply iterate through the columns for each query and sum the amount of operations needed

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

    You can consider unraveling the matrix resulting in a vector (i.e. taking the first column, then second, then third, and stick them to make a new vector). Then, the apps need to be in a prefix of this vector. when adding a image, you extend the prefix, otherwise you need to shrink the prefix (where you need to move the icons). Then, to find how many images you need to move is to calculate the number of images you have in the prefix you currently are in. If this number is X, and you have Y images on the desktop, then $$$Y - X$$$ is the answer. To calculate X, you can do some if's when erasing/inserting images (to see if they spawn/despawn directly from your prefix)

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

    You had to count gaps in the icon arrangement using segment/fenwick trees.

    Video Solutions: A-F

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

      No need of segment tree or fenwick tree it can be done without any extra log factor just have a two variables currow curcol which will denote the position for last icon after rearrangement. And whenever a new * is added somewhere just change the curpos to next postion by curcol+=(currow+1)/n currow=(currow+1)%n; and calculate total stars and number of stars inside the consecutive region. Submission- https://codeforces.com/contest/1674/submission/155735790

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

Aight, guys. This comment may seem a bit toxic or something, but I still want to express how do I feel about this situation. Firstly, I want to say that the problem F is mine (I'm an author of the idea and I prepared this problem).

I get when people are confused about palindrome bracket sequence (as it was in some recent Educational Round), this thing can be really confusing when you see it. But I can't get how people are not familiar with the order of icons appearance on the desktop. Like, if you code from your phone or from fedora or some other OS without GUI, the desktop itself for you can be really confusing, but I don't think there are a lot of such people among Div.3 participants. So, I can't believe nobody saw that when you install some application and mark the field ''add the icon to the desktop'', this icon appears in the first column that is not full, and then in the first position from the top inside this column. Also, when you sort your icons, they're rearranging exactly as in this problem. I thought I created a very life-based problem and people will understand it easily, but I was wrong.

Moreover, the statement wasn't perfect, but was clear enough. There was the following sentence in the second paragraph: ''In other words, some amount of first columns will be filled with icons and, possibly, some amount of first cells of the next (after the last full column) column will be also filled with icons''. I agree that I could add some pictures or maybe highlight some words in the second paragraph, but I thought this is very-very life-based thing that anyone will understand without problems.

At last, I agree that I'm not completely right in this situation, because our task is to make statements as clear as possible for anyone. But, as I said before, this is just my personal opinion, so you can discuss it with me here or maybe just downvote this comment if you disagree.

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

    The statement is a bit hard to understand, but anyway it's still OK to me.

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

    Hey, thanks for the problem, and for the years of service!

    I think the statement was okay, but when reading it for the first time, I felt like an image with the statement would be perfect. Or maybe, explanation of one test case.

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

    As a tester, I agree with vovuh. I also thought everyone encountered desktop arranging at least once and would understand the problem perfectly. To me, it seems like a very nice life-based problem so I didn't suggest any changes to the statement. Will definitely keep such things in mind from now on though.

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

    For problem F, why did the question allow a time limit of 3 seconds? It'd be reasonable to make the participants to use a time limit of 1 second instead.

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

      Yeah, that's probably true. I was just scared that some python/java/(any other non-CP language) users couldn't solve this problem because there is too many IO. But I was completely wrong, so there are also some $$$O((n+m)q)$$$ solutions in C++, and this is a bit disappointing. I also discussed this with Ivan, and we decided that 3 seconds is okay, but turned out it wasn't.

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

    "But I can't get how people are not familiar with the order of icons appearance on the desktop."

    On mac, by default it is right to left:

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

Problem E's pretests are so weak!!!!!!! I have already hacked myself!!!!

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

    Educational rounds and div3s are meant to have weak pretest. Why do you think there is a 12 hour hacking period?

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

      But it is the responsibility of questions setters to have strong pretests that contains most situation of the problem,rather than called the competitors to successfully hack more than one thousand accepted answer.

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

    Dear contestant...

    Please don't worry if you had to hack yourself in order to see if your solution is good. In a programming competition, the tests used can be useless, you should have assured your code works. Sorry if this does not fit in your view.

    Author of xem sdod

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

      Imposter?

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

        Dear non-contestant,

        Please don't worry if someone else is a fan of EGOI and swapped two letters from your name. In a programming community thoughts as such are completly irrelevant. Apologies if this does not fit your view.

        So, can we please get back to programming ?

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

Thank you vovuh and the team for organizing this Div 3 contest. I love the questions and how they were being framed.

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

Amazed to see some red+ coders getting hacked on E. What is the hack case ?

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

thank you AHMADUL for solving A!!!

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

in D I thought that the operation from b to c was the same as from a to b. F :(

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

    I spent about 30 minutes thinking of a solution for this problem before I realize It was not the real problem

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

Testing data for problem E is far too weak.

We can hack a lot of solutions using this data.

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

idea for d? and whats on pretest 32 in e?

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

so many hacks to E...I have rised from 600+ to 400+.

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

;-; Got WA on C just because I wrote (1ll<<a.size()) as pow(2,a.length())

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

Can someone explain to me, what's the point of the removing condition in G? Doesn't it allow us to remove any edge?

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

    The condition is that, after removing any number of edges, the final graph MUST have in-degree and out-degree of EVERY vertex to be strictly less than the original graph (except if the in/out degree was 0 for any vertex in original graph).

    For example, if there is a graph 1->2->3->4, then we can't just remove 1->2, because in the resulting graph (2->3->4), the in-degree and out-degree of 3 are the same as that in the original graph.

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

thanx for good and strong E test's!

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

any hint for E?

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

    I'm trying to explain my solution while my solution is hacked...so I deleted all my notes...

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

      One minute I was hacking my junior, the next I was being hacked by myself...

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

I didn't noticed acyclic graph in G...

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

Wow tons of hacks on E. Accept number decreases in every second!

I forgot a corner case (1 10000 3), the answer is 2(shoot middle, then right). Weak sample and tests.

Upd: till now, about a half solutions hacked!

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

E's pretests are a joke

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

These hacks are crazy, I have gone from 170th to 89th in 45 minutes after the contest. Maybe I will be next...

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

Cursed spoiler:

open this spoiler
»
23 месяца назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
Only for Newbies
»
23 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

What does E's pretest mean...I wrote this chmin(ans, (mx + mx + 1) / 2); Then it's got AC????? Of course it's hacked...

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

I am a simple man, I solved 5, my rank was initially around 1800, then everyone started getting hacked and my rank became around 1200 :) , and then ( you guessed it right ) I myself got hacked! now my rank is 2200+

Please CF don't troll me XD

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

Problem E: My solution

Whats wrong with this?

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

2000 participants: "I solved E!" Joury: "No You didn't)"

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

    There are more than 50 pages of successful hacking to E. Never imagined to this...

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

The pretests are weak — I solved E, then got hacked. I forgot about the case a[i] > a[i + 1] * 2(and vice versa) (then it's not (a[i] + a[i + 1] + 2) / 3 but (a[i] + 1) / 2)). Such a simple one, but pretests didn't cover that case..

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

    There are no pretests in div.3, div.4 or educational rounds. It's full feedback meaning submissions are judged on all tests. Although, the tests on E were weak no doubt. The solves went from ~3000 to ~550 after system testing was over.

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

interesting in hacking problem E the real game

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

Enjoyed the few minutes when I thought I solved E

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

I have been hacked :(

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

Too weak E pretests!!

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

proof by AC isn't working with problem E

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

This round is amazing ,Because some of my friends get higher ranking than one hour ago。

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

If everyone is hacked, it means everyone is not hacked.

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

I might be making a rude comment but the number of hacks makes me wonder that is the Jury's solution completely correct? Is it not possible for some really correct solutions to get hacked just because the jury's solution happens to be not perfect.

Just a thought.

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

    My dear friend, you are absolutely wrong jury always have a proof to defend their solutions

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

    The hacks are tested against jury's solution, that means the jury solution gives different output from the hacked solutions. Which means it's correct.

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

"You should always prove your solutions before submitting" — Tourist

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

Alright, for those that had wrong answer on pretest 32 in problem E like me, maybe this one will help you:
2
3 6
Answer is 3. I had 4 because I was trying to reduce by 3 both numbers while possible (applying two operations, subtracting 1 2 and 2 1) but this is not optimal, as you can just shoot number 6 three times.

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

Is it May's fool? :')

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

Problem E: failing just like the question name : Breaking the Wall (of pretests)

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

If you prefer command line, checkout CF Doctor for more flexibility and faster feedback.

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.

If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).

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

A B C D E-Hacked

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

I have just refreshed the page and 620 accepted solutions for E became 570(during 2min). I am sure till tomorrow there will not be correct solutions

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

What does "the prefix of the next column" in F means? Does it mean that I need to put all remaining icons to the upper side?

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

    Yes

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

    Yes. Effectively it means that if you took all the icons out, you would fill the columns greedily left to right, and within each column greedily top to bottom.

    Correct configuration:

    ***..
    ***..
    **...
    **...
    

    Incorrect configuration:

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

Can anyone help me know why i am not included in common standing. I do not have a rating of 1900 ever. Am I not trusted participant ?

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

do successful hacks give extra points for this round?

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

    nope!

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

      really? Damn! I hacked 10 submissions. I guess it was a waste of my time... So why do problem setters provide 12 hours of hacking phase for participants? Do they want us to make strong pretests for them?

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

        It was a waste of your time if you didn't learn anything from it. Otherwise it wasn't.

        Div 3 (and 4) rounds are run according to Educational Round rules. The purpose of the 12 hour hacking phase is to encourage the studying of others' code and learning how to stress test, debug, and spot holes in algorithms. Often the tests deliberately leave out certain cases to make hacks more likely (though rarely as extreme as problem E today).

        If you only did it for points then yes I suppose you did waste your time; otherwise you did exactly what the round is designed for.

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

          I meant to say that doing 10 hacks was a waste of my time since nearly all of them failed on same test case, and obviously I learned why those submissions failed

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

        it's not a waste of time if you hacked people with better ranking than yours

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

        Anyways, You don't get points for hacking in Div 3

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

hacks ;-;

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

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

Was hacked in E because of the case for (i,i+1) we have equations

2*k1+k2>=a[i] 2*k2+k1>=a[i+1]

when k1<0 or k2<0 my solution was not working. This case should be in pretests!

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

E: WA on pretest 14 and 32 -> could not even enjoy the temporary happiness

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

Could someone please try and hack 155731727

I want to see if I have written the correct solution. Thanks,

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

I have a question when this contest is rated.

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

Here are video Solutions to all problems in case people are interested.

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

Can you explain me why I haven't got any rating after participating in the contest and solving 3 problems there?

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

This F problem is not as difficult as F problem. Original two-dimensional problem can be very very easy converted to one-dimensional.

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

Hello MikeMirzayanov,BledDest,vovuh,adedalic.System

I find out some plagiarism activity in Codeforces Round 786 (Div. 3).

Please check out submissions of problem 1674B - Dictionary,submissions are 155621247 and 155678427 They both have same function with same variable but just comment down it and wrote it again with some variable change. Please look out at it.

Proofs given below and also you can check submissions...