Vladithur's blog

By Vladithur, history, 2 months 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. GamineImAPussy
  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

»
7 weeks ago, # |
  Vote: I like it +77 Vote: I do not like it

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

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

    As a competitive programmer I never even think about SKIPPING A ROUND.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    sure won't

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i think skiping a round is not a good practice

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

    As a tester, I can confirn this round is great.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    Codeforce is very good and interesting, isn't it? Who agrees with me? I really like him.

»
7 weeks 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.

»
7 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

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

Hope to expert!

»
7 weeks ago, # |
  Vote: I like it +115 Vote: I do not like it

As a tester I tested this round

»
7 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

I hope I can solve ABC!

»
7 weeks ago, # |
  Vote: I like it +25 Vote: I do not like it

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

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

    Hope I become an Expert and you become CM.

    Good luck :)

»
7 weeks 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," ✍(◔◡◔)

»
7 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Looking forward to it !

»
7 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

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

  • »
    »
    7 weeks 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...

»
7 weeks ago, # |
  Vote: I like it +205 Vote: I do not like it

Screenshot-2022-08-10-133824

»
7 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

Hope to specialist

»
7 weeks 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

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

As a tester, this round is gud

-QuangBuiCP

»
7 weeks 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

  • »
    »
    7 weeks 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.

»
7 weeks 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

»
7 weeks 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!!!

»
7 weeks ago, # |
  Vote: I like it +51 Vote: I do not like it

As a tester give me GF contribution

»
7 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Problems are great! It was interesting to solve them.

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

this contest seems suspect, I will participate from alt account

»
7 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
7 weeks 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!

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck to everyone!

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

hope i will become specialist after this round

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

As a beginner, I never even think to Skip... It will be the great one .

»
7 weeks 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.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Hope to specialist!

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the "hidden reference" thing??

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I guess it's something hidden in the problem that you can guess to get some score:)

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it's the module they use to mess with the rankings after the end. how do you think some people add more ranking to themselves? :)

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

So I should guess to get the rest of the scores?

»
7 weeks ago, # |
  Vote: I like it +222 Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

As a specialist, I hope I can reach expert.

»
7 weeks 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!

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I wish you all success so that you can solve many problems

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Good. I also wish you to solve many problems. I will try to do everything in my power. And I wish everyone that.

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Hope to get to Master.

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

I hope i can reach pupil, in sah allah

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Looks like a fun round, will be participating

»
7 weeks 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.

»
7 weeks 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"

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck to all of you. And wish I could become specialist.

»
7 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

as a noob coder i am not going to skip rounds

»
7 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Hope I become specialist this time!

»
7 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

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

»
7 weeks 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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone please explain to me the hidden reference thing?

  • »
    »
    7 weeks 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.

»
7 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

as a participant, i am going to participate

»
7 weeks 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?

  • »
    »
    7 weeks 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).

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

    I think E1 is easier than D.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

it will be an intersting contest

»
7 weeks 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. :_)

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

Trying to reach Expert ;-)

»
7 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

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

»
7 weeks 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...

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

All the Best Guys!!!

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

As a nebiw,I just want to solve two questions

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

this contest looks interesting, doesn't it...

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck to everyone participating!

»
7 weeks ago, # |
Rev. 2   Vote: I like it -15 Vote: I do not like it

.

  • »
    »
    7 weeks 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.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to get to Master.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

i think i will become pupil after this round

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

ig i will just solve A and B...hope i solve atleast A

»
7 weeks ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

This round is so NICE :3

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

first contest lessgo.........

»
7 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Permutation Forces!

»
7 weeks ago, # |
  Vote: I like it +41 Vote: I do not like it

  • »
    »
    7 weeks 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 !

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Is osu a dedicated meme for speedforces?

      Sounds interesting.

      • »
        »
        »
        »
        7 weeks 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. :)

»
7 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

I like the style very much

»
7 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

SPEEDFORCES

»
7 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

spermutation forces

»
7 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

difficulty difference between C and D is high

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 weeks 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.

    • »
      »
      »
      7 weeks 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

»
7 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

WrongAnswerOnPretest2Forces

»
7 weeks 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

  • »
    »
    7 weeks 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

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

      Congratulations for being pupil ❤

      • »
        »
        »
        »
        7 weeks 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.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

amazing thanks for good samples for problem c its really a life saver xD

»
7 weeks ago, # |
  Vote: I like it -24 Vote: I do not like it

Another unbalanced round !!

»
7 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

D>>>>>>C

  • »
    »
    7 weeks 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).

»
7 weeks 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

  • »
    »
    7 weeks 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}}$$$

    • »
      »
      »
      7 weeks 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$$$.

»
7 weeks 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

»
7 weeks 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)?

  • »
    »
    7 weeks 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.

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

    yes, the second fact:

    Hint 2
»
7 weeks 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...

»
7 weeks 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

  • »
    »
    7 weeks 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.

    • »
      »
      »
      7 weeks 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

  • »
    »
    7 weeks 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)$$$.

»
7 weeks 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?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is

  • »
    »
    7 weeks 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...

    • »
      »
      »
      7 weeks 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).

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

LCM contest!

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

as a newbie, best round everrrr <3 make more rounds!

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 weeks 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.com/contest/1712/submission/168164434 Wrong answer pretest 6.

»
7 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

When I try to understand the problem C and D:

»
7 weeks 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.

  • »
    »
    7 weeks 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

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh this also seems relatively easy to implement!

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yes I first came up with binary search messed that up didn't even pass pretests

  • »
    »
    7 weeks 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

»
7 weeks 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.com/contest/1712/submission/168166282

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

10 minutes too late for D:/

»
7 weeks 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?

  • »
    »
    7 weeks 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.

  • »
    »
    7 weeks 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.

  • »
    »
    7 weeks 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.

  • »
    »
    7 weeks 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.

    • »
      »
      »
      7 weeks 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

  • »
    »
    7 weeks 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.

»
7 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

guessforces

»
7 weeks 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

»
7 weeks ago, # |
  Vote: I like it +42 Vote: I do not like it

  • »
    »
    7 weeks 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

»
7 weeks 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

  • »
    »
    7 weeks 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. :(

  • »
    »
    7 weeks 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.

  • »
    »
    7 weeks 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)

    • »
      »
      »
      7 weeks 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?

      • »
        »
        »
        »
        7 weeks 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.

        • »
          »
          »
          »
          »
          7 weeks 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)

          • »
            »
            »
            »
            »
            »
            7 weeks 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).

        • »
          »
          »
          »
          »
          7 weeks 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!

»
7 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Such STRONG sample testcases :)

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

welp, misreadeded D, solved the $#!% out of something besides what was being asked...

I guess that's the risk with such synthetic problems...? For sanity's sake, if someone could supply a motivating example of an edge weight determined by its minimum over a range...? I guess I just mentally rejected it into being the minimum of the endpoints out of spite (and that passed samples).

»
7 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

LCMforces.

»
7 weeks 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.

»
7 weeks 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?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 weeks 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.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Guys, why would this solution 168154805 fail for C ?

The idea here is that if there is a gap greater than 1 between the same number, i.e. the count of this number is greater than 1 and the difference between its consecutive occurence is greater than 1, then this number must be turned 0. And finally, we reach a point where all such numbers whose count is greater than 1 and also has a gap greater than 1 is turned 0. Take the rightmost 0's position, say it's $$$p$$$, so we start from $$$p + 1$$$, and each time there occurs a point $$$i$$$ such that $$$p_{i} > p_{i + 1}$$$, that's the new point, $$$i$$$ till which we remove distinct integers.

Thanks for helping.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I chocked =(

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me why my code is failing in pretest 2 for question c my submission.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

nice contest!

»
7 weeks 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

»
7 weeks 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.

  • »
    »
    7 weeks 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]$$$.

    • »
      »
      »
      7 weeks 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.

  • »
    »
    7 weeks 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) ?

    • »
      »
      »
      7 weeks 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.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah I got my mistake.I was not maximizing my prev counter value at the end of for loop.

  • »
    »
    7 weeks 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".

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it worth it to solve all problems after contest?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I mean i could try to solve till D and for E(s) i have to look into editorials.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        7 weeks 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.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I wasted so much time looking for observation in C. Turns out it can be solved with a brute force method.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Me too, except I got the observation but screwed the implementation big time and suffered from correct logic but incorrect output XD.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

»
7 weeks 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...

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

WOW!! FAST Editorial and FAST rating

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

  • »
    »
    7 weeks 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

»
7 weeks 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? :(

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

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
7 weeks 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!

»
7 weeks ago, # |
Rev. 2   Vote: I like it -27 Vote: I do not like it

I bear witness that none is worthy of worship but Allah, the One alone, without partner, and I bear witness that Muhammad(may Allah bless and greet him) is His Servant and Messenger.

»
7 weeks ago, # |
  Vote: I like it -31 Vote: I do not like it

rating changes occurred fairly quickly, satisfactorily)

»
7 weeks ago, # |
Rev. 2   Vote: I like it -31 Vote: I do not like it

lā ʾilāha ʾillā llāhu muḥammadun rasūlu llāhi.

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

  • »
    »
    7 weeks 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

    • »
      »
      »
      7 weeks 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

»
7 weeks 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

»
7 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

The score of E2 is too low. :)

»
7 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Nice contest!

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

great blog.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The problem C,i want to ask a question. If change the question "change x to 0" to "choose a x and delete it" how can solve it? for exmple: i have 4 3 3 3 4 3 4 and choose 3 then i have 4 4 4 not 4 0 0 0 4 0 4 so how to solve this problem?

»
7 weeks 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.

  • »
    »
    7 weeks 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.

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

problem D was very interesting and nice.

»
7 weeks 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.

»
7 weeks 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?

»
7 weeks 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.

  • »
    »
    7 weeks 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.

  • »
    »
    7 weeks 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.

    • »
      »
      »
      7 weeks 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.

    • »
      »
      »
      7 weeks 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.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      is this round became unrated???

»
7 weeks 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.com/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.

»
7 weeks 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.

  • »
    »
    7 weeks 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.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I enjoyed solving Problems B and C :)

»
7 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Is this round unrated?!

»
7 weeks ago, # |
  Vote: I like it +28 Vote: I do not like it

Still waiting for rating change.

»
7 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

where is my rating?

»
7 weeks 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 -=_=-

»
7 weeks 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.

»
7 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Where is my +76 rating points?

»
7 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

So I got flagged on a pattern based question on code forces round 813 about finding the maximum lcm of n permutations . Can anyone help me solve this issue ?? I am linking my code link below . question b https://codeforces.com/contest/1712/submission/168138244 question a https://codeforces.com/contest/1712/submission/168128883 i dont even copy anyones snippet . please help .