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

Автор Vladosiya, история, 3 года назад, По-русски

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

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

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

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

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

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

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

Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацией нашей работы. Задачи были придуманы и написаны командой Университета ИТМО: MikeMirzayanov, MisterGu, myav, Gol_D, Aris, senjougaharin, мной Vladosiya.

Также большое спасибо mango_lassi, espr1t, karemo, starboy_jb, Fly_37, omikad, Katya_Goryachkina, Omja, teraqqq, oversolver, Jostic11, yorky, _4dr_ и doreshnikov за тестирование раунда и весьма полезные замечания.

Всем удачи!

UPD: Поздравляем девушек с Международным женским днем <3.

UPD 2: Разбор

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

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

finally a div3 contest after a 2 month break

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

mango_lassi tested so good he got mentioned twice.

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

Good luck to everyone !

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

This will be an important contest for me, the wait has been long, let's hope to turn blue.

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

First unrated div3 for me, yay :)

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

I might become pupil after this round. I am excited :)

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

Guess who is skipping school tomorrow hahaha

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

First div 3 contest for me yay!! thanks to all the testers and it will be challenging as we have to solve more problems in less time!!

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

Is this challenge suitable for beginners?

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

Div3 contest, long time no see

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

I am happy to participate in a contest on by birthday. I wish to be pupil after this contest. Wishing everyone positive delta. GL&HF!!

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

As a first time tester for a Codeforces round. Please give me some upvote :).

Good Luck and High Rating.

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

Good to see a contest after every one two days. Well done codeforces!!

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

The contest is vital for me,I want to be blue.

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

Hope I can solve today's problems and get my handle colored.

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

Nice gift for March 8)

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

Very excited for div3 after a long time. All the best everyone.

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

Dear contest, make me > 1700 rated pls. thx in adv, wil pay the <> by tomorrow evening

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

Vladosiya's Div 3 rounds are really good. Looking forward to some great problems in the contest.

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

Nice gift for 8th of march , and here's my best wishes to you on International Women's Day 2022 ! Wishing a very happy Woman's Day to strong, intelligent, talented and simply wonderful women of this world! Don't ever forget that you are loved and appreciated. And also good luck on Div 3 !

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

    Good luck also for mediocre and normal women (not only talented and strong ones) which also deserve respect

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

Can anyone help me understand why untrusted people will not be included in the rankings? The round is rated for anyone having a rating less than 1600 anyway so how is the decision having any effect on rating changes?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
  • не иметь в рейтинге точку 1900 или выше.

Наверное всё-таки 1600?

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

    нужно быть < 1600 на данный момент, и < 1900 за всю историю участия в контестах

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

HahahaHaIluminatiHa11-2023

I hope to be the best myself

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

Good luck at International Women's Round #1!

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

Plz, no number theory in problems

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

Finally my first participation as unrated one.

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

implementation forces

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

It took me 20 minutes to understand the statement output 2 numbers in next n lines of the problem C

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

I think C was written so bad

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

Really cool round. Thanks to creators

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

Logic for C please?? is it implementation based problem

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

when i read E I thought it's too easy but then i realized there are things i didn't count in my solution and it was too late

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

    i thought too what ever i was thinking should work but it didn't. then i changed my perspective and did some implementation with multiset to check what would be answer if i change $$$i^{th}$$$ exam date.

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

      I think you should only change the smallest value but I didn't check that maybe if i delete a1 for example and put it somewhere else then maybe a2-a0 is the new smallest value

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

        yes you are right only difference can be made by removing minimum gaps. also need to make sure there are two ways to remove each gap that is not the left most. and also the way i implemented it didn't hurt to check every index, so to keep code a bit simple i didn't think of optimizing on that

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

Problem G: Counting Shortcuts is a great extension of ABC211: Number of Shortest Paths

In fact, you only need 5 to 6 lines of code changes in the Atcoder version to get it working.

I've summarized my approach for ABC211: D in this comment

How to extend it to this version?

First, break it into 3 parts. If the shortest path is of length $$$\delta$$$, we need to compute paths of length $$$\delta - 1$$$, $$$\delta$$$ and $$$\delta + 1$$$. Computing $$$\delta - 1$$$ is a trick question, you should figure that out yourself. Computing $$$\delta$$$ is same as ABC211:D. So, we just need to compute paths of length $$$\delta + 1$$$.

As mentioned in the previous comment, edges in a BFS tree can only exist between nodes of same level (horizontal edges) or consecutive level (vertical edges). If we observe a shortest path, it needs to descend the tree at each stage, i,e, it can only contain vertical edges. A path length of $$$\delta + 1$$$ implies that we added one extra edge in our shortest path. Notice that this extra edge cannot be a vertical edge, as we will miss the target vertex by 1 height. So, we are allowed to add one edge between nodes on the same level. This simplifies it to,

How many paths from source to target are present such that you are allowed to use EXACTLY 1 edge at same level.

Let's rename the DP of the previous problem to $$$dp\_tight$$$, and the DP array of the new problem to $$$dp\_loose$$$.

$$$dp\_tight[node]$$$ is the number of ways to reach $$$node$$$ from $$$source$$$ when you are not allowed to use unnecessary edges.

$$$dp\_loose[node]$$$ is the number of ways to reach $$$node$$$ from $$$source$$$ when you are allowed to use exactly one extra edge.

To compute $$$dp\_loose[node]$$$, we need to consider every edge on the same level (horizontal edges), and increment the $$$dp\_loose$$$ of one vertex by $$$dp\_tight$$$ of the other vertex. Since we should precompute the DP values of all nodes on the same level before populating DP values of next level, we can use a temporary queue for each level (Although I think we can do it in one pass too).

Time Complexity: $$$O(N)$$$

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

Feel like output for C could have been simplified without taking away from problem difficulty. But pretty fun contest anyways.

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

Anyone else ? Who wasted 10 minutes thinking about output in C because of poor language

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

I will reach expert if not hacked.

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

    Can you explain your approach for E?

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится
      1. use a sorted map, such as TreeMap in Java, then maintain all the gaps' count;
      2. Try to remove a[i] for i in [1, n — 1], you will have 2 cases: case 1. insert a[i] in a gap where it has exams on both ends; you will pick the largest gap maxGap and put it in the middle to get a new gap of (maxGap — 1) / 2; case 2. insert a[i] at d with a new gap of max(0, d — a[n] — 1);

      take the better one of the above 2 cases and compare it with the smallest key and update answer. During step 2, remember to update your map accordingly: first remove deleted gaps and add newly generated gaps. After processing a[i], restore the map for the next element.

      I had this idea but forgot to take care of the special case where if we put a[i] at the end on d, it is just d — a[n] — 1 instead of (maxGap — 1) / 2. Feels bad :(

      I've added some comments in my submission, the idea is fairly straightforward: 148911439

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

        i tried using map in C++.... my last brain cell is trying to figure out why my code mutates the map in each iteration, tried using delete when key's value is 0, but when i add some value to it, keys are not appearing back.........

        edit: i mistakenly deleted the value of the map not the key T_T, still got WA tho

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

          I ran into a similar key not found error during contest. I think it is because the way I updated the sorted map.

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

        but would'nt the complexity become more O(n*n) or O(n*nlogn)? That should give tle. You are doing this O(n) computation for every a[i].

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

          it is O(N * logN), each iteration we uses 6 map operations (3 insert, 3 removal). Building the maps takes O(N * logN) then for each iteration, it takes 6 * log(N) time.

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

      I binary searched the answer (maximum μ possible by shifting the element with minimum rest days before it). You can see that for some μ: all smaller values are possible to achieve, this forms an array of True and False: T T T T T F F F F ...

      So now you can apply binary search to find the last T (Last T is maximum possible μ). Now, to find if the current candidate for μ is T or F. You can write a function F(M) which will return True/False if rest days before A[i] <= M for all i. You can try to achieve this by removing the element E with smallest rest days before it and placing it in between any two elements with maximum rest days.

      My implementation for F() is very bad and I believe you will find much better code for understanding in top standings. Please ask if there is anything you didn't understand.

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

C is the one of the worst questions I have seen in a while. The last paragraph of the problem is so confusing, even looking at samples didn't help. I had the idea in 5 minutes, but took 4 WA's on test 1 just because the output formatting is wrong. Also, what does this line have anything to do with anything?

The order in which you output the endpoints of a segment is not important — you can output the index of the left endpoint first and then the number of the right endpoint, or the other way around.

This just makes the problem even more confusing. And lastly, would it kill you guys to give the initial points as sorted? So much extra implementation just to print the indices of the points in original order after god knows how many times I used sort().

On the other hand, the problem itself and the idea behind it is nice. I just don't like the fact that I have to spend 10 minutes on thinking about the solution + implementations and then 30 minutes to properly format the output just so that it passes samples.

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

Question C was worded so poorly!

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

too heavy implementations

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

ImplementationForces

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

Open hacking means if I fail in hacking a solution it would not negatively affect me?

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

Can we get -1 in D?

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

    No. It is always possible to sort the array. Think of it as bubble sort, but use rotates instead of swaps. Every time we move the greatest element to the right, and repeat the same process on the remaining elements until the array is sorted.

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

      Can you elaborate on what do you mean by Every time we move the greatest element to the right ?

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

    no, it is always possible to sort an array by rotating its prefix. actually what i have observed, this fact is used in quite some problems. For instance, this problem

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

Is it necessary for the answer of Problem G to module 1000000007?

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

    Yes

    It is easy to construct a test case for which answer is $$$2^k$$$ if $$$n=3k+1$$$.

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

is there a solution for E that does not involve too many caseworking? my solution had to consider like 6 cases to pass.

Also, props to the very strong sample case that actually helped a lot

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

    Binary search, to check if x is okay find first gap with length < x and try to remove one of endpoints of the gap. Try to place the removed exam in midpoint of gaps, or at the end of session.

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

    you can check out my solution, I made it pretty similar to yours. solution

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

Problem G is very similar to this problem, with the subject of weighted directed graph;

Additionally, more sophisticate version is NOIP2017-S P3953, with the restrict of weighted directed graph($$$w_i \ge 0$$$), to calculate the number of ways of path length no more than minimum_path + k.

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

It's funny that there is no pretest with answer >=998244353 in G:)

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

Is there an O(n) time complexity solution for D?

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

How to solve G? any hints?

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

Video Editorial for A-E for anyone looking

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

There is an issue with the problem G: the variable $$$t$$$ has been reused. Please fix immediately. Highest priority.

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

Hints for problem E ?

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

    I think the way I solve wasnt the expected solution but try this:

    hint 1
    hint 2
    Solution
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can we do d in o(n)?

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

hope to be Specialist

Oh, I submitted B for three times. I might not be Specialist

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

Yesterday,I used 998244353 as the modulo and passed the pretests of G,but today my submission was hacked.

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

The pretests of G were so weak that I used 998244353 as the modulo in this problem and passed them!

But today I was hacked!

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

My rating is 1200. Why was this round unrated for me?

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

Is there any indication that the match has been unrated? My friends and I have found that this match is Unrated for us. A lot of thanks if you could reply to me. :(

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

In this contest, I found an act of unfair means where the user D_K_307 hacked his solution from a fake account to increase his score. Is there a way to report such things ? Proof here

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

    In div.3 contest you can't increase your score with hacking

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

      Cool, but still it's a wrong practice and will be effective for some contests. I have seen some users in past too doing this.

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

    I did not have any Idea about hacking So I just tried it in div.3 contest Beacause I don't know this. Sorry For that.

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

After the system testing. Still didn't change the rating...

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

Mr. Vladosiya I think it is your best contest.Make more contests

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

Waiting for rating changes with 29138 others :)__ Edit: Released yaay

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

The system told me that I cheated because of my Problem G solution coinciding with others. However, this problem had a same version on http://poj.org/problem?id=3463 ,and I had finished the problem with the help of a blog https://www.cnblogs.com/xingxing1024/p/5224363.html .So I use the code to finish problem G.Is it illegal?

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

    The blog was posted in 2016,I cant understand why i am cancelled in this round...

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

    my problem d is coinciding with others but i did it on my own what can i do in that case !?

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

The system told me to cheat because my g question is highly similar to others, but this question is written with reference to a board written before. The link is: https://www.acwing.com/problem/content/385/ , I did this question six months ago. I hope I can get a reply. Thank you.

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

[deleted]

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

Nice contest, I really liked it! I went from newbie all the way up to specialist :D!

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

is there an Editorial?

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

There's a piece of news floating around on Reddit that Russia is gonna cut off the global internet from 11th March. Is it correct? And is it gonna affect codeforces?