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

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

Привет всем!

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

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

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

Огромное спасибо arsijo за координацию раунда и терпение во время многочисленных задержек. :) Спасибо Xellos, Origenes, KAN и opukittpceno_hhr за щедрое тестирование задач. И, как всегда, спасибо 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. wxhtxdy
  3. ecnerwala
  4. AndreySergunin
  5. oxytocyna

Div. 2:

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

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

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

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

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

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

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

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

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

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

»
13 дней назад, # |
  Проголосовать: нравится -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

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

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

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

Its too late for me...

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

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

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

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

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

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

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

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

No chance of giving the round now! ;D

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

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

    • »
      »
      »
      12 дней назад, # ^ |
        Проголосовать: нравится +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 :))

      • »
        »
        »
        »
        12 дней назад, # ^ |
          Проголосовать: нравится +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.

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

    :(

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

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

»
13 дней назад, # |
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.

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

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

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

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

»
13 дней назад, # |
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

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

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

Looking forward to my first div.1!

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

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

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

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

»
13 дней назад, # |
  Проголосовать: нравится 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?

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

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

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

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

»
12 дней назад, # |
  Проголосовать: нравится +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!

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

А сколько задач??

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

Is it rated?do not rate me

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

Good luck everyone!

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

How many problems will be in the round?

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

Will be there multiple-task problems?

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

How many problems? And what scoring?

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

I can already smell mathforces XD

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

I will come back whenever I will become pupil

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

Expecting speedoforces after seeing the score distribution.

»
12 дней назад, # |
  Проголосовать: нравится -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.

  • »
    »
    12 дней назад, # ^ |
      Проголосовать: нравится +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.

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

That was a great contest!

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

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

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

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

»
12 дней назад, # |
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.

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

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

»
12 дней назад, # |
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".

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

    rip

  • »
    »
    12 дней назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      12 дней назад, # ^ |
        Проголосовать: нравится +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.

      • »
        »
        »
        »
        12 дней назад, # ^ |
          Проголосовать: нравится +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.

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

    Yeah, it could've been clearer, sorry.

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

Unbalanced round ;__;

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

How to solve Div1 C?

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

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

  • »
    »
    12 дней назад, # ^ |
      Проголосовать: нравится +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 :/

  • »
    »
    11 дней назад, # ^ |
    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).

»
12 дней назад, # |
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.

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

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

  • »
    »
    11 дней назад, # ^ |
    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.

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

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

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

    I AC'ed that one but failed this one. Was searching for minimum prime factor for one whole hour. Feels bad man

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

hakobdilif must have been practicing really hard since Monday!

»
12 дней назад, # |
  Проголосовать: нравится -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 ;
    }
}
»
12 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve Div2 B2 ? got memory limit exceded

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

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

What was the reason?

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

reveal ...

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

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

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

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

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

      I couldn't find a pattern so I decided to try E instead :P

»
12 дней назад, # |
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?

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

    Yeah

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

      But why? Can you please explain?

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

        hopefully, reason :- actually answer is gcd of all the factors of n

        since proof by contradiction, let's assume the answer is not equal to 1 in that case, the answer is greater than equal to 2 if so then while calculating let's suppose no be 2,6 but still, if 6 is its factor than 3 must be too if gcd(2,3,6) is calculated then it comes out to be one it will not be one if all the numbers are the power of same prime.

»
12 дней назад, # |
  Проголосовать: нравится 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

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

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

»
12 дней назад, # |
  Проголосовать: нравится 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

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

B1 and B2 should have been C and D. I did not even read B1 until the contest was about to end.

»
12 дней назад, # |
  Проголосовать: нравится +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?

»
12 дней назад, # |
  Проголосовать: нравится -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.

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

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

  • »
    »
    11 дней назад, # ^ |
      Проголосовать: нравится +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?

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

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

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

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

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

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

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

What is test case 35 for Div 2 C.

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

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

»
11 дней назад, # |
  Проголосовать: нравится 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

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

    It was in cf round 120

  • »
    »
    11 дней назад, # ^ |
    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).

    • »
      »
      »
      11 дней назад, # ^ |
      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.

      • »
        »
        »
        »
        11 дней назад, # ^ |
          Проголосовать: нравится 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 :)

      • »
        »
        »
        »
        10 дней назад, # ^ |
          Проголосовать: нравится 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?

        • »
          »
          »
          »
          »
          9 дней назад, # ^ |
            Проголосовать: нравится +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.

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

    No this is question opposite of Div2D

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

Can anyone please explain how to solve Div2 B2?

  • »
    »
    11 дней назад, # ^ |
      Проголосовать: нравится +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

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

orz isaf27

»
11 дней назад, # |
  Проголосовать: нравится +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.

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

Please explain solution of Div2 C with a proof.

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

I'm so sad :(

»
11 дней назад, # |
  Проголосовать: нравится 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

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

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

  • »
    »
    11 дней назад, # ^ |
    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 :)

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

OH Benq just had been broken rank 1

»
11 дней назад, # |
  Проголосовать: нравится +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 :(

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

    Even I am facing the same problem.

  • »
    »
    11 дней назад, # ^ |
    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.

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

Congrats @Benq for #1

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

Congratulations @Benq and all hard workers :D

»
11 дней назад, # |
  Проголосовать: нравится 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

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

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

  • »
    »
    11 дней назад, # ^ |
    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.

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

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

    • »
      »
      »
      11 дней назад, # ^ |
        Проголосовать: нравится +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.

      • »
        »
        »
        »
        10 дней назад, # ^ |
        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.

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

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

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

Exactly 1600.

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

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

»
11 дней назад, # |
  Проголосовать: нравится +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

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

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

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

Can someone explain the exact proof for Div1-A

  • »
    »
    11 дней назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      11 дней назад, # ^ |
        Проголосовать: нравится 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.

      • »
        »
        »
        »
        11 дней назад, # ^ |
          Проголосовать: нравится +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.

»
11 дней назад, # |
  Проголосовать: нравится 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.

  • »
    »
    11 дней назад, # ^ |
      Проголосовать: нравится +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

»
11 дней назад, # |
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]

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

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

https://artofproblemsolving.com/community/c7h1171035p5624365

  • »
    »
    11 дней назад, # ^ |
      Проголосовать: нравится 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

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

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

»
11 дней назад, # |
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?

  • »
    »
    11 дней назад, # ^ |
      Проголосовать: нравится 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.

    • »
      »
      »
      11 дней назад, # ^ |
      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.

»
11 дней назад, # |
  Проголосовать: нравится +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)$$$.

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

It seems that the data is so weak.

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

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

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

    • »
      »
      »
      10 дней назад, # ^ |
        Проголосовать: нравится 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
      
»
11 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How come the English version of the post has "bread and circuses" in original Latin while in the Russian version it is translated into Russian? Can't Russians learn Latin? :P

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

Yet another FST round

»
11 дней назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
»
11 дней назад, # |
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?

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

a c c e p t e d

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

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

»
11 дней назад, # |
  Проголосовать: нравится 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

»
11 дней назад, # |
  Проголосовать: нравится 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).

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

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

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

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

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

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

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

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

    raw_input -> input

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

      Странно. Обновил python через brew upgrade, все заработало нормально. Что еще страннее, так это то, что версия у меня как была 3.7.0 так и осталась. Теперь у меня на компьютере он тоже дружит с input().

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

All the best