gen's blog

By gen, 4 years ago, In English

Hi guys!

Glad to invite you to Codeforces Round #599 to be held this Nov/06/2019 18:05 (Moscow time)!

My name is Evgeny Vihrov, this is already my 6th Codeforces contest as an author. To introduce myself, I have participated twice in the ACM ICPC Finals (2012, 2014) and currently I am co-coaching teams for the ICPC at the University of Latvia. This is my first solo round, and it took 3.5 years to make! (the last one was #347 with Alex_2oo8).

In this contest you will have to help Ujan deal with his renovation issues. Hopefully, everyone will find a problem matching their taste!

Huge thanks to arsijo for coordinating the preparation of the contest and for the patience with the frequent delays. :) Thanks to Xellos, Origenes, KAN and _overrated_ for generously testing the round. And as always, thanks to MikeMirzayanov for the panem et circenses Codeforces and Polygon systems!

Wish you an exciting round!

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

UPD2: Scoring:

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

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

UPD3: Thanks for participating! Congratulations to the winners!!!

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: The editorial will be available tomorrow, sorry for the delay. :((

UPD5: The reason behind McDic entering as a coauthor is that one problem was exactly identical to some problem from some Codeforces round. We found out about it only at the last day before the contest, and McDic generously allowed to use his problem.

UPD6: Editorial is posted.

  • Vote: I like it
  • +613
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it -60 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -42 Vote: I do not like it

    good luck :)

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +230 Vote: I do not like it

    I was the fifth person to register for the round.

    I am wondering why the first four didn't comment.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +51 Vote: I do not like it

    Congratulations man, you have achieved a lot at these young age. You can now join avengers

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Its too late for me...

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +169 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +40 Vote: I do not like it

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

No chance of giving the round now! ;D

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +52 Vote: I do not like it

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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +41 Vote: I do not like it

      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 :))

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +23 Vote: I do not like it

        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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    :(

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

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

»
4 years ago, # |
Rev. 2   Vote: I like it +58 Vote: I do not like it

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.

»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
4 years ago, # |
Rev. 16   Vote: I like it +55 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

Looking forward to my first div.1!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
4 years ago, # |
  Vote: I like it +49 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

Hoping that the problem statements will be short and clear!

»
4 years ago, # |
  Vote: I like it -31 Vote: I do not like it

Is it rated?do not rate me

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How many problems will be in the round?

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Will be there multiple-task problems?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How many problems? And what scoring?

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I can already smell mathforces XD

»
4 years ago, # |
  Vote: I like it -10 Vote: I do not like it

I will come back whenever I will become pupil

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Expecting speedoforces after seeing the score distribution.

»
4 years ago, # |
  Vote: I like it -14 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    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.

»
4 years ago, # |
  Vote: I like it +20 Vote: I do not like it

That was a great contest!

»
4 years ago, # |
Rev. 4   Vote: I like it +5 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
4 years ago, # |
Rev. 2   Vote: I like it +80 Vote: I do not like it

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.

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

»
4 years ago, # |
Rev. 2   Vote: I like it +44 Vote: I do not like it

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".

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    rip

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    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.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +18 Vote: I do not like it

        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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    Yeah, it could've been clearer, sorry.

»
4 years ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it
»
4 years ago, # |
  Vote: I like it -22 Vote: I do not like it

Unbalanced round ;__;

»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

How to solve Div1 C?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -48 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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 :/

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +31 Vote: I do not like it

    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).

»
4 years ago, # |
Rev. 7   Vote: I like it +19 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
    Rev. 4   Vote: I like it +47 Vote: I do not like it

    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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
Rev. 3   Vote: I like it +32 Vote: I do not like it

hakobdilif must have been practicing really hard since Monday!

»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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 ;
    }
}
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    check at n = 6 the answer should be 1

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    for 6 answer is 1. your solution prints 2.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

What was the reason?

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

reveal ...

»
4 years ago, # |
  Vote: I like it +105 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +82 Vote: I do not like it

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

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It relates but I am not sure how.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is exactly the same thing.

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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?

»
4 years ago, # |
  Vote: I like it -36 Vote: I do not like it

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.

»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +31 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it -15 Vote: I do not like it

What is test case 35 for Div 2 C.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    It was in cf round 120

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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).

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it +7 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 :)

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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?

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No this is question opposite of Div2D

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain how to solve Div2 B2?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

orz isaf27

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Please explain solution of Div2 C with a proof.

»
4 years ago, # |
  Vote: I like it +40 Vote: I do not like it

I'm so sad :(

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +29 Vote: I do not like it

    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 :)

»
4 years ago, # |
  Vote: I like it +127 Vote: I do not like it

OH Benq just had been broken rank 1

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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 :(

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Even I am facing the same problem.

  • »
    »
    4 years ago, # ^ |
    Rev. 12   Vote: I like it +14 Vote: I do not like it

    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.

»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Congrats @Benq for #1

»
4 years ago, # |
Rev. 6   Vote: I like it -7 Vote: I do not like it

Congratulations @Benq and all hard workers :D

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it +10 Vote: I do not like it

        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.

»
4 years ago, # |
  Vote: I like it -23 Vote: I do not like it

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

»
4 years ago, # |
Rev. 4   Vote: I like it +14 Vote: I do not like it

Exactly nilesh8757.

»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it -17 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Div1 B is somehow the same as 190E and 920E , well, the code is the same at least.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +55 Vote: I do not like it

      It's funny how each time this problem occurs it requires less and less data in the output (I mean: first all the components, then sizes of comonents and now only the number of them)

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        That's a good thing, it means this problem probably won't occur again :D

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +83 Vote: I do not like it

          there's still "check if it is connected" variation.

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it +15 Vote: I do not like it

            Validate the input.

            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it +25 Vote: I do not like it

              Stand and dance at your desk for AC.

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Can someone explain the exact proof for Div1-A

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +24 Vote: I do not like it

        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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

[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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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]

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    Your algorithm is probably outputing m=10 to a string of size 4.

»
4 years ago, # |
  Vote: I like it +26 Vote: I do not like it

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

https://artofproblemsolving.com/community/c7h1171035p5624365

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      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.

»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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)$$$.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It seems that the data is so weak.

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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
      
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Yet another FST round

»
4 years ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for the reply. Should we include any information about the author and the source or just copy-paste is ok?

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        As far as I know, it depends on the source of the code. You can read about it here

»
4 years ago, # |
  Vote: I like it +29 Vote: I do not like it

a c c e p t e d

»
4 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

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 !

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    change array size to 10000 instead of 1000

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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).

»
4 years ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

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

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

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

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

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

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