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

Автор gen, 5 лет назад, перевод, По-русски

Привет всем!

Рад пригласить всех на Codeforces Round #599, который состоится в 06.11.2019 18:05 (Московское время)!

Меня зовут Евгений Вихров, это уже мой шестой контест на Codeforces. Немного обо мне: я дважды участвовал в финале ICPC (2012, 2014) и сейчас помогаю подготавливать команды Латвийского университета для участия в ICPC. Это мой первый соло раунд, и его подготовка заняла 3.5 лет! (Предыдущий раунд, #347, мы провели вместе с Alex_2oo8.)

В этом контесте вам предстоит помочь Уджану с его реновационными проблемами. Надеюсь, что каждый участник сможет найти задачу по своему вкусу!

Огромное спасибо arsijo за координацию раунда и терпение во время многочисленных задержек. :) Спасибо Xellos, Origenes, KAN и _overrated_ за щедрое тестирование задач. И, как всегда, спасибо MikeMirzayanov за хлеб и зрелища системы Codeforces и Polygon!

Желаю захватывающего раунда!

UPD1: McDic присоединяется как соавтор раунда (причины будут прояснены позже)!

UPD2: Scoring:

Div. 1: 500-1000-1500-2000-2500

Div. 2: 500-500-750-1500-2000-2500

UPD3: Спасибо за участие! Поздравляем победителей!!!

Div. 1:

  1. Benq
  2. jqdai0815
  3. ecnerwala
  4. AndreySergunin
  5. tribute_to_Ukraine_2022

Div. 2:

  1. hakobdilif
  2. is1813r
  3. Fype
  4. KenMuse
  5. tdas

UPD4: Разбор будет опубликован завтра, извиняюсь за задержку. :((

UPD5: Причина тому, что McDic присоединился как соавтор, в том, одна задача оказалась идентичной одной задаче из одного раунда Codeforces. Мы узнали об этом за день до контеста, и McDic великодушно разрешил использовать свою задачу.

UPD6: Разбор опубликован (пока что только на английском).

UPD7: Опубликован разбор на русском.

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

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

С почином) Надеюсь ты сможешь найnи вдохновение для следующего контеста раньше, чем через 3.5 года)

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

Офигеть, когда это номер раунда уже подошел к 600! только вчера решал триста какой-то.

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

I was the fifth person to register for the round.

Hopefully a round that took 3.5 years to prepare is a good round :D

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

Евгений, правильнее будет сказать 3.5 года, а не 3.5 лет. А так, надеюсь, что раунд будет норм. А то обычно первые раунды у людей так себе. Удачи!

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

Its too late for me...

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

    I decided to test rather than participate because it's too early for me...

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

Please add my handle as co-author in your announcement QAQ

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

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

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

Автокомментарий: текст был обновлен пользователем gen (предыдущая версия, новая версия, сравнить).

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

UPD1: McDic is joining as a coauthor of the contest (reasons to be revealed later)!

No chance of giving the round now! ;D

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

    Who do you want to give the round to and how is it possible to give a round to someone?

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

      Lol, I know a lot of Indians who usually tell "giving the round" which means "participating in the round", which is kind of a literal translation from Hindi (The commonly spoken language in India).
      I hope this answers your question :))

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

        Yeah, I'm just making fun of that phrase because it doesn't make any sense in English, but good to know it comes from a literal translation.

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

    :(

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

    Ah, I see you are a man of culture as well.

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

I have already risen to master, fallen to candidate master, risen to master, fallen to candidate master, ...... for totally 11 times. And I just rised to master in last round, I hope I can stay in master in this round.

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

Ставлю бороду Снарка, что orz 300iq вылетит из топ-10 после раунда.

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

How to become a tester for contests and contribute problems??

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

I think I know the reason why McDic added as co-author. In his last round he removed a problem from the contest beacuse of no one can solve it in testing. I thing that problem will be added this round

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

Slow work yields fine products,it mights be a good contest.

Looking forward to my first div.1!

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

Надеюсь, функция качества раунда от времени примерно похожа на функцию коньяка.

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

    Кстати, так обычно и бывает, если идея нигде не появлялась, она наверняка крута. Единственная опасность в таком случае — что ты кому-то рассказал, что у тебя есть такой-то коньяк, и потом на дегустации оказывается, что куча народу уже его попробовали :)

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

Hey, can someone tell me more about the sites which actively create contests and where I can use my knowledge of Data Structures and Algorithms?

Apart from codeforces, I know about hackerearth, codechef, google competitions, atcoder, topcoder.

Recently, I came to know about leetcode through Errichto's youtube video.

Please, can someone suggest anything about it?

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

Last round in Codeforces Round #5xx i hope it would be a great closing

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

So much red color in div2 announcement makes feel worried :| . However, let's hope that this will be balanced.

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

In this contest you will have to help Ujan deal with his renovation issues.

Hoping that the problem statements will be short and clear!

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

Is it rated?do not rate me

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

How many problems will be in the round?

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

Will be there multiple-task problems?

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

How many problems? And what scoring?

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

I can already smell mathforces XD

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

I will come back whenever I will become pupil

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

Expecting speedoforces after seeing the score distribution.

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

I missed this contest as I thought the contest will be started at 9:35 AM (usually CF contests will start at this time) in my time zone. However, unfortunately, the start time for contest was at 9:05 AM.

I know it was my fault that I didn't double check the time. But just as a suggestion for MikeMirzayanov and Codeforces team, it would be great if they unify the time of the contests, which are close to each other, to a certain, fixed time.

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

    That wouldn't work all the time, just most of the time, which seems to be your problem. If a problemsetter can't be online the whole evening because there's something else planned before/after, choosing a slightly different time could be necessary.

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

That was a great contest!

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

Hopefully gonna be expert for the first time. Just an awesome contest

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

What hacks did you guys find and what were they about?

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

Fun fact, Div2D/Div1B's code is almost identical to the problem 920E, even though the thing they asked for is different. I've just done 920E in practice, so I recognized it and ctrl-CVed my code. I'm betting there are many who does this.

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

How to solve div2 D? with 920E :))

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

There are k boxes numbered from 1 to k. The i-th box contains $$$n_i$$$ integer numbers. The integers can be negative. All of the integers are distinct.

I understood this as "all integers in any single box are distinct" and wasted over an hour on C before realising that wasn't the case. This could have been stated much more clearly. For example, "no integer occurs twice, not even in two separate boxes".

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

    rip

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

    All of the integers are all of the integers. If it was in each box, there would be an additional qualifier "in each box". Later, it's mentioned that "all $$$a_{i, j}$$$ are distinct" in a separate paragraph and there's no distinction made between $$$i$$$ and $$$j$$$.

    It took me a while to notice that they're distinct, but it's correct the way it's written.

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

      The reason I misunderstood it was exactly because the qualifier exists:

      The i-th box contains $$$n_i$$$ integer numbers. The integers can be negative. All of the integers are distinct.

      These three sentences to me are talking about the integers in box $$$i$$$. Writing

      The integers can be negative. The integers are distinct.

      Sounds bad, so even if I only wanted to talk about the integers in a single box, I'd write the former version (with all). I guess the correct interpretation makes sense too, if you consider the sentences to be separate entities. Of course, I'm not a native English speaker, so maybe this sounds ridiculous to someone who understands it better than I do.

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

        I'm pretty sure sentences are separate in perkele too. When you string together too many sentences, context can't carry over between them forever, that would break language. Besides, the sentence about negativity in between applies to everything equally, the qualifier is meaningless there.

        You just missed it.

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

    Yeah, it could've been clearer, sorry.

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

Unbalanced round ;__;

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

How to solve Div1 C?

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

    If n has more than 1 prime factor ans is 1. Else ans is the only prime factor n has.

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

    I was doing a dp on processed boxes: added to dp[mask] a number left "unused" if we perform non-cyclic reordering on the boxes in the mask (i.e. normal reordering without one transfer). But I was lost somewhere in building an answer from dp transitions :/

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

    If the sum of all numbers is not divisible by $$$k$$$, then the answer is No.

    Otherwise, let $$$S$$$ be the sum of all numbers. The sum of integers in each box must be $$$S/k$$$

    Suppose the first box sum is $$$S_i$$$. If we decide to take some integer $$$c$$$ out of it, then obviously its sum will be $$$S_i - c$$$, and we need to put the number $$$S/k - S_i + c$$$. Given that all $$$c_i$$$ will be distinct, then this required number should be in at most one box.

    Now, if the required number is $$$d$$$ and its taken from some other $$$j$$$ box, then we should find where $$$S/k - S_j + d$$$ is. We will take $$$d$$$ out of that box and solve the same problem. This will lead us to a cycle, until we reach the box $$$i$$$. Obviously, if some integer is not found within all the boxes, or we have to take an integer from a box that has already been modified, then it's not possible.

    Given that $$$1\leq k\leq15$$$, we can apply a bitmask dp. We will take any box that has not been modified and try to take every possible integer out of it and apply the process explained above. Once we obtain the cycle, we repeat the dp with the other boxes that have not been modified (i.e. don't belong to the cycle).

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

My D solution:

Let's look at the index of the $$$i$$$-th sequence($$$0$$$-indexed) where a number is skipped because it appeared as a sum of some other sequence. Let's call this $$$f(i)$$$.

There are $$$2$$$ cases:

1) $$$k$$$ is even

$$$f(i)=\frac{k}{2}+i*k$$$

2) $$$k$$$ is odd

$$$f(i)=\frac{k-1}{2}+i*k+g(i)$$$

Let's write $$$i$$$ in base $$$k$$$. If there is no digit $$$\geq \frac{k+1}{2}$$$, then $$$g(i)$$$ is $$$0$$$. Else, let's say that the least significant digit which is $$$\geq \frac{k+1}{2}$$$ represents $$$k^x$$$. $$$g(i)=1$$$ if $$$x$$$ is even and all digits representing $$$k^y$$$ where $$$0 \leq y < x$$$ are equal to $$$\frac{k-1}{2}$$$ and $$$0$$$ otherwise.

Using this the rest of the implementation shouldn't be too hard in an awful complexity(I'm not sure if it's ever actually achieved) but the average case is really good. You can feel free to hack this if the worst case really is too slow.

How i figured this out:

Just make a brute force and notice some patterns.

Code: 64419936

There are definitely better solutions though.

Edit: my solution is in fact too slow, it will soon be hacked. There might be ways to use $$$f(i)$$$ which aren't too slow though. The reason the solution is so slow is because finding $$$g(i)$$$ takes $$$O(log n)$$$, I'm not sure if there's a better way.

Edit 2: I realized $$$g(i)$$$ can be calculated in $$$O(log log n)$$$ but that's still too slow.

Edit 3: Actually, the slowness doesn't have anything to do with $$$g(i)$$$; i actually call $$$f(i)$$$ $$$log(n)*log(n/k)$$$ times in the worst case, which is clearly too slow.

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

    My solution for D is different. It will be available on editorial.

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

    I managed to debug and simplify my solution and I think this problem is really beautiful: 64426704

    Let's call the set of $$$K+1$$$ numbers added in one step a block, and set of $$$K$$$ consecutive blocks a superblock. Each block contains $$$K$$$ low values (those are the $$$u_i$$$), and $$$1$$$ sum.

    Now comes the guesservation: the $$$i$$$-th superblock contains $$$K^2$$$ low values from interval $$$[i*(K^2+1)+1, (i+1)*(K^2+1)]$$$, e.g. there is exactly one number missing. When we find this missing number, we can easily find the sum of any block within this superblock (because it consists of at most two arithmetic sequences).

    As the sums are increasing, it is obvious that the number missing in the $$$i$$$-th superblock is the sum of the $$$i$$$-th block. The $$$i$$$-th block belongs to $$$i/K$$$-th superblock, so we can solve this recursively with the initial condition that the sum of $$$0$$$-th block is $$$K*(K+1)/2$$$.

    The algorithm is as follows: we find the superblock to which $$$N$$$ would belong if it was a low value (it's $$$\frac{N-1}{K^2+1}$$$), let's call this $$$x$$$. If sum of the $$$x$$$-th block is $$$N$$$, then the answer is $$$(x+1) * (K+1)$$$, otherwise we can find the answer because we know what is the missing number in our superblock.

    The complexity is $$$\mathcal O(\log N / \log K)$$$ per test case.

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

The Idea for the DIV2 — C was somewhat similar to 1245A - Good ol' Numbers Coloring !!!

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

hakobdilif must have been practicing really hard since Monday!

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

Hi , Can anyone tell me why I got wrong on pretest 6 in Problem C ?

My Code :

long long n ; cin >> n ; bool chk=0;

if(n%2==0) cout<<2 ;
else
{
    if(n==1) cout<<1;
    else
    {
        for (int i=2; i<=sqrt(n); i++)
        {
            if (n%i == 0)
            {
                cout<<i ;
                chk=1;
                break ;
            }
        }
        if(chk==0)
            cout<<n ;
    }
}
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    check at n = 6 the answer should be 1

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

    for 6 answer is 1. your solution prints 2.

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

    The answer isn't always the smallest prime divisor of n. Take the case n = 6, for example. If we paint tile 1 black, then tile 3 and tile 4 have to be black. Since tile 4 is black, tile 2 and tile 6 are black, and since tile 3 is black, tile 5 is also black. So all tiles have to be the same colour.

    The correct answer is finding the gcd of all non-unity divisors of n.

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

    try n = 6.

    1,3,5 should be the same 2,4,6 should be the same 1,4 should be the same

    therefore all should be equal.

    Your code says 2.

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

UPD1: McDic is joining as a coauthor of the contest (reasons to be revealed later)!

What was the reason?

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

reveal ...

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

My problem in this contest is Div1D. Thanks to all people who participated!

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

    It is really a wonderful problem! I did find the pattern but have no time to code — a sad story.

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

My solution to Div-2-C is getting all prime factors of the number if the number have only 1 prime factor print it, otherwise(because it contains more than 1 prime so gcd will be equal to 1) print 1

Is that Right?

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

Can anyone tell me if my code for prob B2 true or false plz. I completed it after the time had ended, just a minnute. I feel so bad but Im also feel nervous if it is true or not, help me plz, Im so so sad now T-T. My Code for prob B2

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

    It passed and I feel so sad, but if it hadnt passed, I would have been sad also. Bad day T^T

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

Hello, I found a sequence in OEIS for problem C div2. Can anyone say if it relates with the problem? https://oeis.org/A014963

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

    It relates but I am not sure how.

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

    Yes it does, when there are more than 1 factor, then they happen to meet at some number, which is not 0 modulo the first factor; hence a imbalance and causes a chaos which leads to everyone having same color.

    When 1 factor: No chaos. So number of colors same as the factor.

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

    It is exactly the same thing.

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

My approach to Div1E (I figured it out 10 minutes before the end, so couldn't implement):

If there is only one face, the answer is obvious.

If there are two faces, then there is an outside vertex (vertex of the whole polygon) $$$v$$$, which has an edge to the inside of the polygon. Notice that we can sometimes "glue" the two polygon edges adjacent to $$$v$$$. And this way we will decrease the perimeter by $$$2$$$. Thus, the perimeter is always $$$3$$$ or $$$4$$$. How to know is it $$$3$$$ or $$$4$$$? Well, take a look at $$$a_1 + a_2 + \ldots + a_n$$$. It's equal to $$$2 * insideedges + outsideedges$$$, so the parity of the number of outside edges is known, so we can figure out the perimeter.

Now the only implementation that came in my mind is to implement the process: build a chain of faces, where two adjacent have one common edge, and then reduce it to $$$3$$$ or $$$4$$$. Is there a better way of writing the code for it?

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

MikeMirzayanov I got Idleness limit exceeded on 64385470 I submitted the same code again but i changed the code so I Can submit it again and I got pretest passed on 64387902, I only removed the all the #define at the beginning of the code.

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

Wow, great Div1C! I especially liked the part with restoring the answer in such an elegant form. orz=3

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

    I think that restoring the answer is very easy to implement in this problem. Also, here it's much better for the checker: if somehow participant finds the answer while author's solution has bug and doesn't, there is way to find this out only if we return answer, too.

    Btw, never saw you posting a comment with positive feedback about problems on CF, but saw a lot of negative. Are all problems on CF so bad?

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

      Hm, no, problems from 572 (Div. 1) were ok :) But I will try to write more positive comments in order to increase contribution!

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

А правда ли что в самом начале контеста фраза "Все данные числа различны." не была жирной?

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

contests like a wine..........

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

What is test case 35 for Div 2 C.

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

    A number n with a prime factor around 10^9 but this prime factor is not n itself.

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

0-1 MST is just a version of the first problem of kickstart round E(Cherries Mesh). Just replace the( 1 and 2 cost) with (0 and 1 cost). Problem link

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

    It was in cf round 120

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

    I think there's an (important) difference — there you have all the light edges, here you have all the heavy edges. Since counting connected components over the light-edge graph is relevant, there you can just DFS the graph itself, here you have to DFS the anti-graph formed (which is a harder problem because the antigraph may have upto n(n-1)/2 edges so you need some tricks).

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

      I still did BFS on the graph with some tricks, as you said. You can do this by keeping the set of vertices not yet in the queue and checking for each whether it's 0 or 1 edge. This has complexity of $$$O(n^2 \log{n})$$$.

      However, you can make an observation that if $$$n$$$ is small, you're fine with this. If $$$n$$$ is large, then because of requirement on total 1-edges, there will be one very large component, and if you immediately eliminate it, you're left with very small $$$n$$$ again, so you're fine with BFS.

      One vertex of such component is the vertex with the least amount of 1-edges out of it. So as long as you begin your BFS with that vertex, your BFS will pass.

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

        That's a cool idea — I did think of optimizing the antigraph traversal, but then convinced myself that that idea was wrong :( It was anyway not a trivial insight for me. Thanks for the comment :)

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

        You actually don't even have to start your BFS at the least degree vertex to get an AC for this problem. You can start from any vertex, and your solution will pass. Is it because of weak test cases?

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

          Interesting. Just tried submitting the solution with the start of the queue at vertex with the biggest degree vertex and the solution still passed with roughly the same time.

          I guess because you can only remove so many vertices from the main component (let's call the amount of them $$$k$$$) that perhaps it just doesn't matter indeed no matter the test cases, in which case writing BFS with only considering vertices not yet in the queue was enough.

          Roughly speaking, the asymptotic of this solution is $$$O(k n \log{n})$$$ (until you reach your main component you'll process $$$k$$$ vertices while considering $$$n$$$ edges for each, and after you reach it, you'll process $$$< n$$$ vertices while considering $$$< k$$$ edges for each). but since $$$k * (n - k) <= 100000$$$, $$$k$$$ is realistically small for large $$$n$$$ ($$$k <= 112$$$ for $$$n = 1000$$$ and $$$k <= 1$$$ for $$$n = 100000$$$), and it's still enough. Wouldn't bet on it though during the contest.

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

    No this is question opposite of Div2D

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

Can anyone please explain how to solve Div2 B2?

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

    If each letter occurs even number of times in total the answer is possible.

    Now, iterate over string. If $$$s1_i$$$ is not equal to $$$s2_i$$$, you find an element in either string that is equal to $$$s1_i$$$ ( and by the first condition you are guaranteed that such an element exists), and bring it to $$$s2_i$$$, either by swapping directly if it is in $$$s_1$$$, or by swapping using an intermediary element (if it is in $$$s_2$$$).

    Submission: 64389826

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

orz isaf27

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

can anyone help me prove my solution in Div2.D 64389079 I just guess if n >= 1e3 I calculate all of the Unicom blocks with a point with a value of 0 with a margin of less than 200, and points greater than 200 as a Unicom block.

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

Please explain solution of Div2 C with a proof.

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

I'm so sad :(

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

thank you .. but please can any one tell me why my Solution for 1243B2 - Character Swap (Hard Version) didnt work ! Checker comment told me : wrong answer Solution not found but exists [test=371] what did that mean !! this my code ! 64414329

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

Why does it work: 64384395? Weak tests or it can be proved?

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

    I came up with a similiar idea to a similiar problem before XD 34872588
    Its worst case time complexity is $$$O((N+M) \log N)$$$. ( $$$O(N+M)$$$ data structure (set,vector access) operations, to be precise).
    I have claimed it here, but I didn't wrote the proof down QAQ.

    This inner loop from your code is the only nontrivial part in time complexity analysis because all other parts are obviosly $$$O((N+M)\log N)$$$. To know its time complexity, we just need to count how many times we access $$$cur$$$.

    for (int w : cur)
        if (!g[u].count(w))
        {
            to_del.push_back(w);
        }
    

    Case 1. When g[u].count(w) == 0, $$$w$$$ is then removed from $$$cur$$$. The number of accesses from this case is $$$O(N)$$$.

    Case 2. When g[u].count(w) == 1, an edge $$$(u,w)$$$ exists. Since each $$$u$$$ is taken out exactly once from the queue and we loop through $$$cur$$$ exactly once for each $$$u$$$. We have an injection from an access to an edge. Therefore, the number of accesses from this case is bounded by the number of edges $$$O(M)$$$.

    So the total number of accesses to $$$cur$$$ is $$$O(N+M)$$$.
    Correct me if I am wrong :)

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

OH Benq just had been broken rank 1

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

For Problem D, I had tried to create a DSU of components connected by 0-edges only. I felt no of components -1 will be the answer. Since this might TLE, I had a visit array so that once I see a node i, I perform union_set(i,j) such that (i-j) is a 0-edge and also mark visit[j]=visit[i]=1. So this may not TLE. But it gave me a WA on TC 13? any idea whats going wrong :(

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

    Even I am facing the same problem.

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

    You cannot mark j as visited before checking all edges of j. For example, imagine a graph of size 4 with the following 0-edges (not 1, it is easier to write only the 0-edges):

    1 3
    2 4
    3 4
    

    When visiting 1 you set 3 as visited, when visiting 2 you set 4 as visited, then you will never consider the edge 3-4.

    Your algorithm answers 2 instead of 1.

    Instead of looping through every possible edge, I did a BFS checking only the edges reaching unvisited vertices, this way you can avoid trying all the edges. When you try the edge (a,b) you will have 2 cases.

    Case 1: it is of weight 0, therefore you add b to the queue and never try any edge reaching b, in this case number of unvisited vertices decreases by 1.

    Case 2: it is of weight 1 and you will do nothing and try b again later, in this case the number of remaining edges of weight 1 decreases by 1.

    Therefore you either decrease the number of unvisited vertices or the number of remaining edges of weight 1, so it is in the order of 2*10^5 operations.

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

Congrats @Benq for #1

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

Congratulations @Benq and all hard workers :D

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

Damn, I solved ABCD, which in theory could give me very good place for me, but I got TLE in D (I think it's just constant factor since if I'm not mistaken I have O(log n / log k) with hashmap per query) and small but in C (removing one line fixed it) and in the result I have >200 place and -145 to rating... I hate it so much >_>

But at least I enjoyed D even though I struggled with +-1s for literally >0.5h. E seems really nice as well

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

    The same thing in C and AC in D, -157. Love CF scoring distribution.

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

    I ran your code for $$$K=2$$$ and $$$T=100000$$$ random values of $$$N$$$. You store values of 24 million states in the hashmap and call your "solve()" function one hundred million times. I've experienced some problems where the number of tests was unnecessarily high (232C - Doe Graphs in particular), but this sounds too inefficient. In comparison, my solution has a clean non-branching recursion with no memoisation required.

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

      Hmmm, that sounds suspicious, maybe I did some mistake in the complexity analysis, I will check than when I have time. Thanks.

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

      FUUUUU, I adjusted my code a little bit so it is more careful and it passed within 1s out of 2s. Basically everything was asymptotically fine with my code, but I sometimes did some unnecessary calls which caused me to store 7 log n states instead of 3 log n states.

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

        11 hacked

        Just generate 100000 random tests with $$$K=2$$$. It still takes 10 seconds locally, my solution takes < 150 ms. Function call overhead and hashmap lookup overhead are probably the worst offenders.

        UPD: And it's down to 4 seconds when I wipe the hashmap as soon as it gets too large and do lookup before function calls.

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

Benq dethroned tourist after years!!! Congrats Benq ! tourist no matter what is your rank we will always love you!

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

Exactly nilesh8757.

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

Решение D(div2) 64423223 Очень жаль, у вас слабые тесты.

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

Div1 B can be solved almost directly using Borůvka's algorithm, but on the contest i found more convenient using a mix of bfs and Borůvka idea 64380663

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

Thank you for the interesting problems! In particular, I quite liked Div1B and Div1C.

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

Can someone explain the exact proof for Div1-A

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

    If n has at least two prime factors, let's say p and q, you can use Bezout's lemma to find that there exists a and b such that a*p+b*q = 1. Therefore you can achieve a net displacement of 1 after many steps of moving forwards and backwards. Thus, the answer is 1.

    If it has only one prime factor p, then every position with the same remainder mod p has the same color, therefore the answer is p.

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

      But won't there be condition on a*p <= n. Or is it always possible to do some +p and -q operations such that the current value is always less/equal to n.

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

        Yes, it is possible that a*p > n. However, when you get near n and cannot move forward by p, you can just move back by q as many times as necessary. As when you have two prime factors both are at most n/2, you can always do this.

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

[Problem D]
I'm looking forward to find a bug in my submission 64417332.
Glad if somebody catches it. The approach i quite straight forward.
I take vertices with largest degrees and connect them with everything, that's possible.
(Keeping track on already picked and connected vertices.)
This way I decrease the number of components and the answer is just components_no — 1.

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

    You cannot set i as done before considering all edges of i. Think about the case of the following 0-edges (not 1-edges):

    1 10
    1 11
    1 12
    2 13
    2 14
    2 15
    12 13
    

    When you process 1 you set 12 as done, when you process 2 you set 13 as done, then you never consider the edge 12-13

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

I am getting this message for DIV2-B2 in testcase3 64427963

wrong answer Integer parameter [name=m] equals to 10, violates the range [1, 8]

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

Problem Div 1 D strongly resembles a problem from the 2015 Putnam competition, which we can see here:

https://artofproblemsolving.com/community/c7h1171035p5624365

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

    Damn, this problem was such a fking pain. Hardest A\B<=2 problem I've seen on Putnam. I decided to write down its elements not larder than something like 60-80 and noticed nothing and decided to abandon it. After the contest I asked some people that solved this problem and they all replied that they generated this sequence up to something like 150 and then noticed some pattern xD

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

It will be better competition if round-600 will be a global round

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

My randomized solution in Div1 B: 64405219. I have no idea what its probability of success is, does anyone have a clue, even for an approximate value or some bounds?

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

    Can you explain how this works on a high-level? There are some things that aren't immediately obvious to me from a quick scan, like what relevance 170 has.

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

      170 is the $$$MAGIC$$$ number :D Increasing it increases the probability of success and also the running time.

      My solution works as follows: for each node, if the number of adjacent nodes to it is larger than $$$n/MAGIC$$$, then join this node with all non-adjacent nodes. Else, choose $$$MAGIC$$$ nodes randomly, and join this node with non-adjacent nodes among these nodes. The time complexity will be $$$O(max(n,m) * MAGIC * O(DSU Operation))$$$.

      My intuition about it is that if some node has so many non-adjacent nodes, then most probably I won't need to join it with every single one of them, because many of them may be already joined or will be joined later.

      However if I just do this for every node, it may be the case that some node has only a few non-adjacent nodes, and it must be joined with each one of them, that's why when the number of non-adjacent nodes is few, I iterate on all of them.

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

My solution for D, upsolved shortly before the contest, is based on one main observation (which I can't prove): the difference between the $$$iK$$$-th and $$$(i+1)K$$$-th sum for each $$$i \ge 0$$$, i.e. $$$s_{(iK+K+1)(K+1)} - s_{(iK+1)(K+1)}$$$, is always $$$K(1+K^2)$$$. Another observation is that $$$s_{(iK+1)(K+1)-1} = i(1+K^2)+K$$$, also unproven.

Clearly, the $$$i+1$$$-th sum is always at least $$$K^2$$$ larger than the $$$i$$$-th sum, so this means the difference between each two consecutive sums is at most $$$K^2+K$$$. In addition, when we want to find the $$$aK+b$$$-th sum, we know that the $$$aK$$$-th sum is exactly $$$\frac{K(K+1)}{2} + a(1+K^2)$$$ and the $$$aK+b$$$-th is at least $$$\frac{K(K+1)}{2} + a(1+K^2) + bK^2$$$ and at most $$$\frac{K(K+1)}{2} + a(1+K^2) + bK^2 + K$$$. The most important property is that for all $$$b$$$, these ranges are disjoint.

Next, we need to realise that we only need to find the first sum $$$\ge N$$$ (both index and value). If it's equal to $$$N$$$, we have the right index, and if it's greater, then before the answer — index $$$id$$$, there are all numbers $$$\le N$$$ and a few sums $$$\gt N$$$. Since we know how many sums are $$$\le N$$$ and that there are $$$id/(K+1)$$$ sums before $$$id$$$ in total, $$$id$$$ is the result of a simple equation.

How to find this sum? We can easily find the greatest $$$a$$$ such that the $$$aK$$$-th sum is $$$\le N$$$, and we only need to find the smallest $$$b \le K$$$ such that the $$$aK+b$$$-th sum is $$$\ge N$$$. The "maximum value of the sum" expression above gives us an easy lower bound on $$$b$$$ — the greatest $$$b \ge 1$$$ such that the maximum possible value of the $$$aK+b-1$$$-th sum is $$$\lt N$$$. Then, the first sum greater than $$$N$$$ must be the $$$aK+b$$$-th or $$$aK+b+1$$$-th, depending on the exact value of the $$$aK+b$$$-th sum, since the minimum value of the $$$aK+b+1$$$-th sum is automatically $$$\ge N$$$. We just need to find a sum with a given index.

Finding the $$$aK+b$$$-th sum uses the same idea, but applied on sums that are low enough that they can interfere with the summands used to create this sum. Specifically, this sum is $$$m + (m+1) + \ldots + (M-1) + M$$$, where either $$$m = M$$$ and there's no sum between $$$m$$$ and $$$M$$$, or $$$M = m+1$$$ and there's a sum between them. From the other observation above, $$$M \ge a(1+K^2)+K+bK$$$ and $$$m \ge a(1+K^2)+1+bK$$$. Let's start with this estimate and consider sums that are $$$\ge a(1+K^2)+1+bK$$$; with some calculations, we get that this corresponds to the $$$a$$$-th, $$$a+1$$$-th etc. sums. For each of these sums, if it's smaller than the current estimate for $$$m$$$, then our estimates for $$$M$$$ and $$$m$$$ should increase by $$$1$$$. If it's between our current estimates for $$$m$$$ and $$$M$$$, we increase just $$$M$$$ (the last $$$M-sum+1$$$ summands, to be precise), but the next sum will be much larger — greater than $$$M$$$, so we've got the summands and can compute the sum. It also turns out that we only need to compute this last sum and use the upper bound estimated above for the rest.

Implementation: 64426937. The while-loop should be $$$O(1)$$$ and we're computing recursively the $$$i$$$-th sum from the approx. $$$i/K$$$-th sum, so the total complexity is $$$O(\log N / \log K)$$$.

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

It seems that the data is so weak.

I used std::map<int,int> in Div1. C but passed the system test.

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

    Umm what's weak about that? All numbers are distinct.

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

      Hack #596829.

      I used map.find(x) to find the id of x or x isn't appeared,

      but x can be larger than INT_MAX so that my code can be hacked by:

      2
      2 1 2
      10 0 1000000000 999999999 999999998 999999997 999999996 999999995 999999994 999999993 589934621
      
»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Yet another FST round

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

Hi, is it ok to submit in the contest code written by somebody else in another contest? For example, submit D2 D using this?

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

a c c e p t e d

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

It's too strange that half of people have been hacked by sys. test case after contest. I think that test case should be added in problem test cases !

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

Hey can anybody help me in finding the difference in these 2 submissions ? One is accepted while the other gets TLE. 64425892 and 64387961. Thank you very much

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

I feel a little stupid, Div 2C. I had the right algorithm and everything. It's just test case 3 is N=1 and I didn't account for that(bc when I search for factors I just assumed the value would have factors that aren't just 1, something to learn out of this).

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

Пробую писать решения на Python3. Подскажите, какие именно там настройки по умолчанию. Так, например, у меня на компе для ввода 3-х целочисленных аргументов нужно сделать вот так:

a,b,c=raw_input().split()

В то время как на сервере нужно использовать вместо этого input()

И вообще пока работоспособности решений не получается добиться (хотя у меня они запускаются). Вот ссылка на неудачную попытку, которая запускается на моей машине (громоздко, знаю, но я пока экспериментирую).

Подскажите, что там не так? Где взять параметры запуска python3? Искал вот здесь: О языках программирования и технических аспектах. Но там для python3 именно та команда, которую я использую у себя на компе.

Мой комп: Mac Book Pro, MacOS 10.13.6.