Vladithur's blog

Codeforces Round #813 (Div. 2)
By Vladithur, history, 2 years ago, In English
Hi, Codeforces!

Igorfardoc and I are pleased to invite you to our Codeforces Round 813 (Div. 2), which will be held on Aug/13/2022 17:35 (Moscow time). This round will be rated for participants with rating lower than 2100.

We would like to thank:

You will be served 6 problems, one of which is divided into two subtasks, and you will have 2 hours and 15 minutes to sample them.

Hope you don't choke 😋

The score distribution is 500 — 1000 — 1500 — 2000 — (2000 — 750) — 3500

PS

UPD: Tutorial

UPD2: Congratulations to the winners!

Div. 2:

  1. iztrax
  2. TrungNotChung
  3. Akemi-Homura
  4. bajablast
  5. __NONE__

Div. 1:

  1. tourist
  2. m_99
  3. jiangly
  4. LJC00118
  5. sjc061031
  • Vote: I like it
  • +622
  • Vote: I do not like it

Comments Comments (222)
| Write comment?
»
2 years ago, # |
  Vote: I like it +77 Vote: I do not like it

As a tester, don’t even think of skipping this round…

→ Reply
»
2 years ago, # |
  Vote: I like it +31 Vote: I do not like it

As an author's helper, I think it will be nice PermutationMathCodeforces round.

→ Reply
»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Codeforces Round 813 (Div.2) rp ++ ！！！

Hope to expert！

→ Reply
»
2 years ago, # |
  Vote: I like it +115 Vote: I do not like it

As a tester I tested this round

→ Reply
»
2 years ago, # |
  Vote: I like it +18 Vote: I do not like it

I hope I can solve ABC！

→ Reply
»
2 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Hope I became CM on this round and tasks would be good.

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

    Hope I become an Expert and you become CM.

    Good luck :)

    → Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

What's the meaning of "You will be served 6 problems, one of which is divided into two subtasks," ✍(◔◡◔)

→ Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Looking forward to it !

→ Reply
»
2 years ago, # |
  Vote: I like it +13 Vote: I do not like it

looking forward to [ hidden reference] and [bonus versions]

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +15 Vote: I do not like it

    Most of the references are not very hidden, just some quote in the start of the statement...

    → Reply
»
2 years ago, # |
  Vote: I like it +205 Vote: I do not like it

Screenshot-2022-08-10-133824

→ Reply
»
2 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Hope to specialist

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for releasing the score distribution very early. I liked it

This round looks so balanced. Hope everyone get a positive delta :P

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

    This round looks so balanced.

    My man got the time machine

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

As a tester, this round is gud

-QuangBuiCP

→ Reply
»
2 years ago, # |
  Vote: I like it +7 Vote: I do not like it

and you will have 2 hours and 15 minutes "to sample them"

Do we uniformly pick $$$k$$$ unique problems to solve or what? thinking

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

    There is plenty of time to sample all the problems! But maybe not enough time to complete all of them, since some of the dishes are quite big.

    → Reply
»
2 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

Good luck to all participants of this round, as well as IOI participants. Hope to rating>=1300

→ Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

As a tester of the this round and the recent one, I confirm that both rounds are really great!!!

→ Reply
»
2 years ago, # |
  Vote: I like it +51 Vote: I do not like it

As a tester give me GF contribution

→ Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Problems are great! It was interesting to solve them.

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

this contest seems suspect, I will participate from alt account

→ Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Could anyone tell me what does "a hidden reference" mean?

→ Reply
»
2 years ago, # |
  Vote: I like it -9 Vote: I do not like it

The emoji after "Hope you don't choke" seems sus

Anyways good luck to everyone who is doing the round!

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck to everyone!

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I wish and hope short statements like this post. I like it

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hope i will become specialist after this round

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

As a participant, I never skip any Div. 2's, unless it's bad.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Codeforces Round 813 (Div.2) rp ++ ！！！

Hope to specialist！

→ Reply
»
2 years ago, # |
  Vote: I like it +222 Vote: I do not like it

→ Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

As a specialist, I hope I can reach expert.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck to everyone, don't skip a contest just because you are afraid to lose rating! You got this!

→ Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Hope to get to Master.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Looks like a fun round, will be participating

→ Reply
»
2 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Ah great, Round 813 on 8/13 and my birthday.

Wish everyone good luck and hope I will be well enough to participate.

→ Reply
»
2 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Is there a food theme? "You will be served ...", "you will have 2 hours and 15 minutes to sample them", "Hope you don't choke"

→ Reply
»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Hope I become specialist this time!

→ Reply
»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Vladithur is a giga chad, so I'll have to participate.

→ Reply
»
2 years ago, # |
  Vote: I like it +12 Vote: I do not like it

I am sorry, unable to attend since it is 1:35 am in my timezone. Hope others have fun

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone please explain to me the hidden reference thing?

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

    It just means that each problem has some kind of reference. For example, maybe the problem contains a quote from some particular movie or something. This has no bearing on the actual problem design whatsoever, so you don't have to worry about trying to find these references.

    → Reply
»
2 years ago, # |
  Vote: I like it +15 Vote: I do not like it

as a participant, i am going to participate

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Friends, is E(2000-750) saying it's in that range of difficulty?

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

    Problem E will have two subtasks: the first has a base score of 2000 and the second has a base score of 750.

    Since the first one is scored much higher than the second, my guess is that the second subtask is an extension or improvement to the first subtask, so you would need to be able to complete the first subtask first to be able to solve the second subtask. Solving the first subtask only achieves a base score of 2000, but solving both subtasks is worth a base score of (2000 + 750 = 2750).

    I don't think it would be possible to solve the second subtask before the first (since such problems would generally present the Easy version before the Hard version).

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

    I think E1 is easier than D.

    → Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I have been very lucky in the past few contests, but feel like I would eat a heavy negative delta this round. :_)

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

Trying to reach Expert ;-)

→ Reply
»
2 years ago, # |
  Vote: I like it +21 Vote: I do not like it

today is 8/13 and this is round 813, wow!

→ Reply
»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

The Date is 8.13 and the Round is 813

Wish Everyone non-negative rating changes...

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

All the Best Guys!!!

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck to everyone participating!

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it -15 Vote: I do not like it

.

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +17 Vote: I do not like it

    I think it's completely unreasonable to expect a random user who decided to problemset to have power just because they are high rated. I won't get into the semantics of what you should have done, but expecting a user to know what to do is like walking up to a customer who's looking at bad standards (as another customer) in a shop and asking them where you can report bad standards. At best, you might be referred to a website, and at worst they won't know.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to get to Master.

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

This round is so NICE :3

→ Reply
»
2 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Permutation Forces!

→ Reply
»
2 years ago, # |
  Vote: I like it +41 Vote: I do not like it

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    Well, I'm going to play OSU! instead of stucking on D. Click the circle !

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

      Is osu a dedicated meme for speedforces?

      Sounds interesting.

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

        idk yet, but I always get some idea when I playing osu,

        so I did that then came up with the solution of D. :)

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

I like the style very much

→ Reply
»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

SPEEDFORCES

→ Reply
»
2 years ago, # |
  Vote: I like it -9 Vote: I do not like it

spermutation forces

→ Reply
»
2 years ago, # |
  Vote: I like it +20 Vote: I do not like it

difficulty difference between C and D is high

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am so ridiculously bad at guessforces, its always wrong wtf

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

    Hello fellow bad at guessforces! If you're also like me who insists on finding the pattern instead of actually solving the problem, try running brute-force solutions for smaller cases of $$$n$$$ and watch the pattern like so.

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

      thats what I did after getting the WA, but that problem is too trivial to even require that

      → Reply
»
2 years ago, # |
  Vote: I like it +18 Vote: I do not like it

WrongAnswerOnPretest2Forces

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +19 Vote: I do not like it

I didn't like this round. When I solve anything gets me wrong answer on pretest 2! ◑﹏◐. But actually I liked the clear statements ❤

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

    may be you are missing something small(try thinking of test cases that will fail your code and handle these cases) there is still some time so keep trying the first 3 problems are quite easy

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

      Congratulations for being pupil ❤

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

        thanks ❤. happy to see someone from mansourah here btw. good luck in the upcoming rounds.

        → Reply
»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

D>>>>>>C

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

    actually D is not much harder than C. It is just that... I got WA 5 times (I got the idea tho).

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

this is the solution I thought for E2 but couldn't code in time: (based on solution for E1)

Sort the queries wrt $$$l$$$, and maintain answer for each fixed $$$k$$$ in a segment tree, for $$$1 \leq k \leq MAX$$$.

We can see that each $$$i$$$ belongs to at-most $$$MAX/l$$$ numbers $$$k$$$ such that there exists a triple $$$(i, j, k)$$$ for which $$$lcm(i, j, k) > i+j+k$$$ (those $$$k$$$ are multiples of $$$i$$$). So we need to update only those values of $$$k$$$ in segment tree which stores the number of triples with largest number $$$k$$$.. Hence, summing up over $$$i$$$ from $$$1...MAX$$$, we get $$$O(MAX log(MAX))$$$ complexity for updates in total, and $$$log(N)$$$ for querying over segment tree

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

    Idk if your approach works, but I did a sweepline w.r.t $$$r$$$, and whenever we increase $$$r$$$, we first check the two cases when $$$lcm(i, j, r) = 2r \land i + j > r$$$ which only happens if $$$(i, j) = (\frac{1}{2} k, \frac{2}{3} k),$$$ $$$(\frac{2}{5} k, \frac{2}{3} k)$$$, which we can simply point update on our segment tree, and then, for divisors of $$$r$$$, we first sort them and iterate them from the closest to the furthest from $$$r$$$ and we make the point updates accordingly (we should add 0, 1, 2, ... in this order). Then, we can calculate the total number of bad tuples which we can subtract from the total $$${r-l+1 \choose{3}}$$$

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

      Its essentially the same solution, you look at it from the perspective of the number $$$k$$$, so you update $$$r$$$, while I sweepline on $$$l$$$ because I am updating the divisors and not the number $$$k$$$.

      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i think a few days ago i saw a contest announcement (maybe that one is fake) saying something like "no penalty for wrong submissions" so i just didn't put much effort into checking before submitting. lesson learned: check contest announcement before the contest to make sure nothing is missed

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does solution for D rely on the fact that diameter will be between (x,x+1)?

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

    You still need to consider is there a case both the x and x+1 is 1e9.

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

    yes, the second fact:

    Hint 2
    → Reply
»
2 years ago, # |
  Vote: I like it +16 Vote: I do not like it

D sucks, the observation is easy, but the implementation details are annoying. I spend more than 1.5hour on finding just a small bug...

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

How to solve F? I figured that we could first calculate the closest leaf nodes for each vertex using bfs, and then the answer for the queries is going to be the maximum of $$$min(f_u + f_v + x, depth_u + depth_v - depth_{lca})$$$, where $$$f_u$$$ is the distance to the closest leaf node from $$$u$$$, over all pairs of $$$u, v$$$. I tried to do some centroid decomposition, but it didn't work

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

    This can be done using small to large merging + segment tree but I don't think that it will work under given constraints.

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

      Yeah I first thought I could go for small-to-large with some data structure (BBST/Segtree), but I quickly realized the constant factor, Q = 10, and N = 1e6 would make it impossible, so I gave up

      → Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +38 Vote: I do not like it

    Binary search the answer and brute force through all the nodes.

    Now $$$f_u$$$ is fixed, so the other node should have $$$f_v \geq something $$$ and we want to find the node having the largest distance to $$$u$$$.

    Sort the nodes by $$$f$$$ in increasing order, now the valid nodes form a suffix of the array.

    The key observation is we only need to consider the two nodes that form the diameter (easy to prove).

    So we just maintain these two nodes and use a $$$O(nlogn)-O(1)$$$ LCA to calculate the distance and the complexity is $$$O(nqlogn)$$$.

    → Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

in D, isn't shortest path between 2 points 2 * minimum or edge between them or not?

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

    It is

    → Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 3   Vote: I like it +2 Vote: I do not like it

    yeah, that's what i thought as well. the answer should be min(shortest edge * 2, longest edge) right? but apparently not according to pretest #2...

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

      You can't just greedily get rid of the minimums, you might need to make a longer edge (eg 4 5 7 it's better to get rid of the 5).

      → Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

LCM contest!

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Video Solution for C, will upload D in the morning.

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

Can anyone explain why this is wrong for D: https://codeforces.me/contest/1712/submission/168164434 Wrong answer pretest 6.

→ Reply
»
2 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

When I try to understand the problem C and D:

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone give me hint on how to solve C?? Messed up this contest.

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

    if you want to 0 some point you also 0 its last occurrence, then you need to zero all the points up to the last occurrence, then all their last occurrences, then all the points up to their last occurrences, etc. until the last occurrence is the point itself and the right is sorted

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

    Binary Search over the final answer (lo = 0, hi = N)

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

    one of the solution can be binary search, If you read the bold character correctly, every number is >0 , and we can make some of them 0. So let's find out how many from the prefix, we want to set 0. Rest is implementation.

    168108660

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone give a testcase for which this code will get wa? Code :https://codeforces.me/contest/1712/submission/168166282

→ Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

really bad problem B, but D is interesting. How to solve it?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

10 minutes too late for D:/

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

If there some effective data structure to handle D?

I realized that there are only two candidates for the diameter: 2 * minimum value of array, and the largest single edge (which is always the minimum of two adjacent values in the array). But updating the entire array for each change would be too slow.

I resorted to using TWO maps of type <long long, set <int> >, where map[i] denotes the set of indices whose value/adj-edge is i. I think this should work, in theory, but the implementation was such a pain in the neck that I couldn't get it working even after an hour of starting.

Does anyone have any suggestions for a more effective and cleaner way of updating these values?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    I went for a binary search using just a copy of the original vector for each iteration.

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

    I used only vectors, but I couldn't submit in time; so not sure if my solution is correct.

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

    I used ordered set to maintain numbers other than the adjacent pair I am currently looking at. Helps in retrieving the Kth element fast.

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

    Greedily replace the first k-1 minimums (I used vectors of (idx,value) so you can sort it by value, change the first few and then sort by idx). Then you have to find a position for the last value to replace. It'll either be another minimum or a value next to the maximum.

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

      in general, we do not even need to store indexes, a sorted array is enough, because in short we are only interested in whether there are such standing next to each other in the original that we want to replace them

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

    Just binary search on the diameter $$$d$$$, and for each adjacent elements $$$a_i$$$ and $$$a_{i + 1}$$$, count the number of elements $$$a_j$$$ left of $$$a_i$$$ with $$$2a_j < d$$$ and the number of elements $$$a_k$$$ right of $$$a_{i + 1}$$$ with $$$2a_k < d$$$.

    Then the total number of modifications needed is the count above + $$$(a_i < d)$$$ + $$$(a_{i + 1} < d)$$$. If this count $$$\leq K$$$, diameter $$$d$$$ is feasible.

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

guessforces

→ Reply
»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

As a participant the questions were very good but I (tragically) choked on D

→ Reply
»
2 years ago, # |
  Vote: I like it +42 Vote: I do not like it

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Same as you. By the way, I am the guy claims to be similar as you in Bilibili, In fact, we both submitted D's answer in the last few minutes coincidently

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I stared at my code of D for nearly an hour, which got WA on pretest #2.
Can someone please help me? HERE

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

    After being stupid on B and a long struggle on D, it seems that my rating will drop dramatically. :(

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

    Take a look at Ticket 16024 from CF Stress for a counter example.

    → Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    The diameter isn't necessarily twice the minimum value; it can also be the weight of the single heaviest edge in the graph. consider the following test case:

    4 1
3 100 4 5

    The diameter is 4 here (not 6). By nuking the 4 (replace with 1e9), the new diameter becomes 6. However, your program outputs 8, probably because it only considered twice the minimum and nuked 3 (I didn't actually try understanding your code, FYI)

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

      But isn't the aim is that we should make the diameter bigger, and replacing 3 with 1e9 get a bigger diameter?

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

        Sorry, you're right. The example should've been one where nuking the minimum doesn't change the heaviest edge. Consider this instead:

        4 1
3 4 100 5

        Your program outputs 8, but I don't see how that's achievable. If you nuke the 3, then the longest edge becomes 5, which is the diameter. If you nuke anything else, then you can always use double of 3, which is 6 (optimal answer). It should be impossible to reach a diameter of 8 from just one operation.

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

          if 3 is replaced by 1e9 then what would be the distance between 1st (value = 1e9) and 3rd(value = 100) node. Won't it be 4 + 4?? (sum of path)

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

            The distance between 1 and 3 would be the direct single edge (1, 3), which has weight 4.

            Taking two edges (twice the minimum) isn't always the shortest path between two vertices.

            The diameter is always min (2 * minimum edge weight, maximum edge weight).

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

          Oh you are right. I wrongly sorted the array!!! Thank you so much!

          → Reply
»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Such STRONG sample testcases :)

→ Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

LCMforces.

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

In the face of 100000 level data, I often limit myself to the wrong o (n) solution and ignore the possibility of O (nlogn) level solution.

At present, I have no way to get rid of this thinking dilemma.

I'm sorry for my poor English. I hope you will forgive me.

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

would anybody be able to point out my mistake for D? here's one of my submissions

i ignore the k smallest weights, then find the longest single edge which is always going to be the minimum of some adjacent pair (i think?)

so the answer should simply be min(shortest edge * 2, longest edge) no?

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Because ignoring the k smallest weights doesn't necessarily optimize the longest edge. For example:

    3 1
3 4 5

    Here, the longest edge is 4. If you ignore the 3, the longest edge is still 4, so the diamter hasn't increased. The optimal choice would've been to nuke the 4, thus raising the longest edge to 5.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I chocked =(

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

nice contest!

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Me before the round: I hit guardian on leetcode weekly 295 on 29.5, maybe today is the day, hit expert on round 813 on 8.13 Me after the round: failed miserably

→ Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

So, what is the idea behind Problem E1? I'm not entirely sure, whether my attempt are correct, but what I found (by looking at big amounts of small testcases, so no proof yet):

Let's call a tuple $$$(i,j,k)$$$ valid, if it has to be counted according to the statement. $$$(i,j,k)$$$ is not valid iff $$$lcm(i,j) | k$$$ or the tuple has the form $$$(3x, 4x, 6x)$$$ or $$$(6x, 10x, 15x)$$$.

Counting the tuples with form $$$(3x, 4x, 6x)$$$ or $$$(6x, 10x, 15x)$$$ is rather straight forward, but I couldn't manage counting those with $$$lcm(i,j) | k$$$ during the contest, and right now my head is spinning and I'm taking a break. I guess we can interate over the $$$k$$$ somehow and then find the amount of corresponding $$$i$$$ and $$$j$$$ by some prime factorizations counting? But that won't be enough for E2 I guess.

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

    You can count all divisors greater or equal $$$l$$$ for all integers in $$$[l, r]$$$ using something like Eratosthenes sieve. Let that numbers be $$$d_i$$$.

    Then for each $$$k$$$ the number of pairs $$$(i, j)$$$ satisfying $$$i|k$$$, $$$j|k$$$ and $$$i < j$$$ is $$${d_k \choose 2}$$$ and now obviously you can add it all up (also with number of triples of form $$$(3x, 4x, 6x), (6x, 10x, 15x)$$$) to get the number of triples that don't work among all ordered triples with different elements from $$$[l, r]$$$.

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

      Thanks! That worked out well 168245128. Didn't even need Eratosthenes to solve, checking numbers up to their root was enough. Although it is dangerously close to the timelimit with 2.5s out of 3.5s.

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

    How did u get the idea of form(3x,4x,6x) and(6x,10x,15x) ?

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

      Look at my commented Code in 168245128. I did a testingprogram which could output all invalid tuples with $$$l=1$$$ and $$$r=100$$$.

      I've been looking hard at those tuples and found out: If $$$lcm(i,j)|k$$$ then the tuple is invalid. But not all invalid tuples satisfy $$$lcm(i,j)|k$$$.

      So then I made the program print all invalid tuples which do not satisfy $$$lcm(i,j)|k$$$. Again I looked hard at them and they seemed to be very regular, so I decided to divide them by $$$gcd(i,j,k)$$$ while outputting, and then only tuples $$$(3,4,6)$$$ and $$$(6,10,15)$$$ were left. It was pretty easy to check, that a tuple in that form always will be invalid.

      I guess the parts where I wrote "I looked hard at the numbers" won't help you much. Having dabbled in number theory it came to me after some time, but I can guess that this won't be easy for everyone. But I have no easier way to explain it right now.

      Also at some point I was also looking at $$$lcm(i,j)|2k$$$, because all invalid tuples did satisfy this. But sadly not every tuple that satisfies $$$lcm(i,j)|2k$$$ is invalid, so that helped understand the structure a bit, but did not lead to the solution.

      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.me/contest/1712/submission/168164872 Hello can anybody help me, what is wrong in my solution for C? Maybe some testcase where it is falling?

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

    If we input

    1 4 1 3 2 4

    the expected output is "1", but your program output is "0".

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it worth it to solve all problems after contest?

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

    You mean to copypaste other's solutions or upsolve the problems?

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

      if you're doing that at least keep it to yourself.

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

        I didn't want to insult him, I've seen many newbies that copypaste solution of people in hard problems after the contest, I wanted to know if he means that, to tell him to avoid doing such thing.

        → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

→ Reply
»
2 years ago, # |
  Vote: I like it +77 Vote: I do not like it

I sumbitted E2 in the last 5 seconds successfully but didn't sumbit E1 in time...

→ Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

WOW!! FAST Editorial and FAST rating

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

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    maybe its a four pointer and senary search problem don't know about number theory so maybe a typo

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

What are the odds I'll gain 1 rating point after the cheaters are removed? :(

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

    Limit rating tends to 0, ask Mike to increase 1 xD

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

    Recently after they removed cheaters my rating decreased from 1900 to 1899:)

    → Reply
»
2 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I wasted a Master performance and dropped to newbie performance because of two tiny mistakes in C and D :(

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

    Excuse me if I am naive but how do you judge whether your performance was of Expert level or Master level,Is it just qualitative or is there a quantitative measure to it (rank in contest/No of problems solved). Regards

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

      There is a Chrome extension called carrot which displays the predicted rating change, performance during/after the contest

      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am finally a Specialist // SHAHEEN // after two hard-work year .. Don't give up

→ Reply
»
2 years ago, # |
  Vote: I like it -8 Vote: I do not like it

The score of E2 is too low. :)

→ Reply
»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Nice contest!

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

I am doing virtual participation at the moment, solved ABC in 30 min, but based on what people are saying in the comments I won't even try D...

Good contest overall, even though C felt little easier than usual.

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

    D is really not that scary, especially if you're more relaxed to realize there is a very straightforward way to solve it (which I sadly didn't realize during the intensity and stress of the actual contest). I would definitely recommend at least reading and thinking about D, and then attempt to solve it if your considered approach isn't too crazy.

    → Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

problem D was very interesting and nice.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Giving contest is very important as consistency and patience is necessary for good results.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am constantly getting this message that jangalvijay's answer is matching with you, I dont know how it is possible. How can our answer match ore than 1 times with same person. Is there a gltch?

→ Reply
»
2 years ago, # |
  Vote: I like it -16 Vote: I do not like it

In this game 168170365 and 168165798 two codes were ruled duplicate，but it was just a coincidence that there was only one dichotomous idea in this problem, but it happened to use the same method.168199920,This code has the same idea as mine, but it's written in a similar way. Could it be cheating? How can you cheat when you can find out that my first submission time is the same as the person who sentenced me? I don't like cheating, and there is no cheating. I think this competition is used to improve myself. Cheating means nothing, but I just hope to get a fair answer.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it -19 Vote: I do not like it

    168156899 This code is similar to mine. Is it cheating? This is just to show you that this is just a coincidence.

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    As I see in 4 (four!) rounds before you have been caught with cheating. The stock of trust in you, alas, is exhausted.

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

      However, I have been working hard on the problems in CF these days, and I have no intention of cheating again. This is really an accident.I'm really sorry about what I did.I really have corrected it.

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

      I hope you can give me one last chance, this is really an accident. I'm very sorry.

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

      is this round became unrated???

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

Attention!

Your solution 168165798 for the problem 1712D significantly coincides with solutions ssntt66c/168165798, aruichen/168170365. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.me/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

I can ensure that I don't disclose the code to others during the competition, and according to my judgment, my code submission time is earlier than that of another person. I think this may be a coincidence in thinking that leads to code similarity. I hope to get a fair judgment.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Attention! Your solution 168156932 for the problem 1712E1 significantly coincides with solutions sjc061031/168156932, Hu-Tao/168171393. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation.

This is so ridiculous. I found that this person got the password of mine and copied my code of C,D,E,F. He even got official rank 4 by cheating.

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

    This person also copied my code of C,F in the previous Educational Round without being found. Interesting.

    → Reply
»
2 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Is this round unrated? It is my first round to solve E.

→ Reply
»
2 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Is this round unrated?!

→ Reply
»
2 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Still waiting for rating change.

→ Reply
»
2 years ago, # |
  Vote: I like it +16 Vote: I do not like it

where is my rating?

→ Reply
»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

We shouldn't be the victims of others' cheating. This is my second round after I came back to ACM, so sad -=_=-

→ Reply
»
2 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Where is my +77 rating points :(

Are we going to get back the ratings or not. Please tell.

→ Reply
»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Where is my +76 rating points?

→ Reply
»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Where is my +187 rating points? Is this round unrated? Any reason?

→ Reply