vovuh's blog

By vovuh, history, 4 years ago, translation, In English

<almost-copy-pasted-part>

Hello! Codeforces Round 636 (Div. 3) will start at Apr/21/2020 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

  • take part in at least two rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Daria nooinenoojno Stepanova, Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round. Also thanks to Artem Rox Plotkin and Dmitrii _overrated_ Umnov for the discussion of ideas and testing the round!

Good luck!

</almost-copy-pasted-part>

UPD: Also thanks to Sakhiya07, infinitepro and ma_da_fa_ka for testing the round!

UPD2: Editorial is published!

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

| Write comment?
»
4 years ago, # |
Rev. 3   Vote: I like it +11 Vote: I do not like it

GL to all :D vovuh orz

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

GLHF to all, xD

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

is vovuh the only user who can make div3 contest ? i mean why every div3 contest in the past 5 or so are made by him?

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

    He is coordinator for div3 rounds .While Pikmike is coordinator for educational rounds series!

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

      what is the difference in educational rounds vs DIV rounds?

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

        THe differnce is that Educational rounds are rated for div2 (rating below 2100) and Div3 ones are rated for rating below 1600 thus their is differnce in problems and their difficulty. Educational Round is an Harbour Space University Initiative and they pick problems that are really meant for teaching new things to newbies like us and Div3 rounds are practice rounds for us for honing our skills of accuracy and implementing problems in a better way.

        Both of the rounds are similar in terms of hacking if we see as both allows hackers to hack others solution after the contests and also all problems have equal weight in both the type of rounds.

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

          Are you kidding me. It was supposed to like that. Div3 and educational div2 are fine. No doubt. But, if you think about teaching of new things, then normal div2 rounds also do this and some setters do this better like errichto.

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

            By the way the original question doesn't talk of normal rounds. Thus I didn't talk of it!

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

1

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

IMG_20200420_211652.jpg ..

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

When anyone else tries to make Div3 contests:

Vovuh:

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

I had a doubt: does 12 hour hacking phase mean that solutions can be hacked during this phase after the contest? Till now I used to think that we have to lock our problems and look at solutions in our room and hack them during the contest.

So which one is correct? Thanks in advance

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

    It means you will have an access to all solutions in a text form. You won't be limited to your room only.

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

      Thanks for the clarification

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

I think 12 hours of open hacking phase is too much. It could be reduced to 4-5 hours while adding successful hacks to system testing. If it is for 12hrs for some reason, It is just a humble request to please help me know the reason.

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

    Contest timings are usually not favourable for everyone around the world. Yet, those who manage to participate might be participating at like midnight or something. Most people would prefer to sleep after the late night contest. To provide a good window and opportunity for hacking to such people, hacking phase seems to be 12 hours.

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

    What about people in other countries? For example, in China, the contests usually starts around 10 p.m. so we can only hack the next day.

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

I have started making video solutions on mostly D based problems of every codeforces round. The videos can be found here.

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

We want more contest in this quarantine :(

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

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

Pics-Art-04-21-07-20-28 ..

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

How can I make problems in a Div.3 round? I see that le.mur(he/she hadn't participated in any contests) was one of the authors of Codeforces Round 552 (Div. 3). My rating is 1591 now so can I make problems in Div.3 rounds?

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

Why are there "6 or 7 (or 8)" problems? Am I allowed to know how many problems there are?

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

Good Luck to everyone!!

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

looking forward to increasing my rating ..as always.. :)

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

![ ](img)

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

I think the problems will be more like implementation type! So, Be ready with your implementation skill @ 20.05!!

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

I wish the penalty was less(like the contests in Atcoder).

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

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

Good luck to you all and have lots of fun, coders!

As you got used to it, we will upsolve the most interesting problems of the round live at 8PM:

https://youtu.be/ppk9pXL9rR4

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

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

Thanks vovuh!We hope more Div.3 contests for our beginner )

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

I know u guys are already at it... but we need more contests in lesser time interval...upvote this comment if that's what u want too...so much hatred in this community :(why downvote???

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

    Nope. We want good quality contests.I don't mind if it takes more time because we always have the option of doing virtual contests.

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

    Always remember, we want good quality contests. A single bad contest can make people complain for a long time

    Good contests usually require more preparation.If you want to have more contests, you can do virtual ones(Since there are more than 600 rounds in the past, you will have a lot of work to do)

    See this contest for an example:AIM Tech Poorly Prepared Contest (unrated, funny, Div. 1 preferred)

    Although is a funny unrated round, do you want to have rated contest like this?

    View the past contest list, choose a contest and click "virtual participation" button to do virtual contests.

    By the way, if you want more upvotes, you can submit useful comments(for example, answer questions), but not asking for upvotes. People usually won't do things they are forcely asked to do if they don't want.

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

It would be great if you add contests more frequently like alternate days or one in 3 days. Happy Coding :)

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

This is vovuh's 37th Div-3 contest.

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

    In my opinion it is 36th contest. It is named "Div3 round 36" in polygon.

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

      You are right. Mike held one Div.3 contest without me (I don't remember its number)

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

this contest has become now as contest with most number of participants ...wow

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

26K+ participants. Simply WoW.

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

27k+ Registrants for this contest!!!

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

I hope this contest would be good unlike the previous one.

»
4 years ago, # |
  Vote: I like it -20 Vote: I do not like it
The comment removed because of Codeforces rules violation
  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    What was your Comment ??

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

      I had told that I think the first condition in problem D is not necessary because with the given definition of "replacement" it's impossible that we violate the first condition.

      I'd told this in a nice way and I thought it doesn't spoil anything about the problem so it doesn't violate the rules. But maybe it did. :D

      However... It wasn't such an important thing. The fun part is about downvoters who have never seen what I'd said. :))

»
4 years ago, # |
Rev. 2   Vote: I like it +52 Vote: I do not like it
D, E, F though

»
4 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it
The comment removed because of Codeforces rules violation
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

 Such a difficult D.

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

    I am suprised so few people solved it, thought there would be 2-3 times more lucky solvers. I am 1300 elo and I did it! And I was even disappointed it took me so long. Seems my training worked out :D

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

      what's your idea?

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

        I go over each (a_i, a_n-i) pair and find for which sum x I would have to make 0, 1 or 2 replacements. They form ranges so I mark their starts and ends in an array, that lets me solve in linear time.

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

          i agree with you. my solution was same

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

            Congrats!

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

            I have used the same solution as yours. Look like there's a silly mistake.

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

          Did (tried actually) same thing but got WA (Test 2) :D

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

            This happended with me too

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

      "I'm 1300 elo and I did it"- very poor reference. Remember Gennady was once a 1500 too.

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

        Maybe we all can become Gennady ;)

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

      Training always works out. Sometimes you just need a bit more of it with some consistency.

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

        Yes, I think the key to improvement is consistency and challenging yourself. I have a habit of solving one 1600-1800 problem everyday and it helps much.

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

    IMO it wasn't that bad.

    My solution I think is the most natural one arising from simply understanding the contribution of every index depending on the value of forced sum.

    You do some case analysis for $$$ u, v > k $$$, $$$ u, v \leq k $$$ and $$$ \mathrm{max}(u, v) > k, \mathrm{min}(u, v) \leq k $$$ and just make an interval tree, in which $$$ s $$$-th position corresponds to penalty for choosing the forced sum to be $$$ s $$$. Then a minimum query on the whole $$$ [0, 2k] $$$ gets you the answer.

    You need lazy propagation to build such a segment tree, though, but if you know that, it's pretty straightforward. The only pitfall here is debugging for an hour, like I did.

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

      Since you only have one query, isn't it much easier to only do offline prefix sums instead of the segment tree?

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

        It's not obvious to me how to do that actually. The core of my solution 77566384 is processing elements of the prefix one-by-one and adding on the interval and I don't know how to do that without segment trees or treaps.

        I think this can be unwrapped into some scanline approach to get rid of LP but again no idea how to do it in other ways. Could you elaborate?

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

          Yeah. You're somewhere close to the idea with a scanline. Though, I am a bit surprised as to how you know about segment trees but are unaware of the prefix sum approach to query.

          Let's say you have an array A of size N with elements a[i], i = 1 to N.

          You're given Q queries in each of which you need to count number of values less than(or equal) a given value Y and strictly greater than a given value X.

          So, build an array(or map), say freq. freq[X] denotes how many times X appears in array A.

          Now, create a new array(or map) pref where pref[i] is sum of freq[0] to freq[i].

          So, for each query (X,Y] your answer is pref[Y] — pref[X].

          Note: Time complexity becomes O(N + Q). This isn't recommended when there are update queries for array A too since that leads time complexity to O(N*Q) as you will have to rebuiled the pref array(or map). Note that space issues might also arise for large values if you use array.

          In the concerned question, the values don't go beyond 2*K at any point of time, and hence there won't be space issues.

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

          The scanline approach will efficiently find, for each point, the sum of values of all segments that overlap it. Consider any segment $$$[l, r]$$$ of value $$$v$$$. In the scanline, for this segment, you want all indices $$$< l$$$ to be worth $$$0$$$, all indices $$$l \leq i \leq r$$$ to be worth $$$v$$$, and all indices $$$> r$$$ to be worth $$$0$$$.

          The scanline will keep a running prefix sum of the values at each array element. To increase this prefix sum by $$$v$$$, simply increment the value at $$$l$$$ by $$$v$$$. This increments all values on $$$[l, n]$$$ by $$$v$$$. To make our range exactly $$$[l, r]$$$, add $$$-v$$$ to $$$r + 1$$$. Doing this for all segments before doing the scanline, the scanline's value at each point represents the sum over all segments overlapping that point, and you can take the minimum of the values at all points.

          An image that may be helpful
»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

What is test 2 of D? Please.

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

What was WA29 in Problem E?

My logic was: Do a BFS from B. Find the node with max depth (say V) such that V to A and to V to C shortest paths exist — I basically conjecture that the common path will be a prefix, and once the paths bifurcate, they will never meet.

Then the answer can be calculated appropriately, by giving the smallest edge weights to the common path and the remaining smallest to others.

What's the countercase? I saw many people failing on WA29

Link to code: https://codeforces.com/contest/1343/submission/77543873

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

    Same solution here. WA on 29.

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

    Try this:

    6 6 1 4 6

    1 1 1 1 5000 5000

    1 2

    2 3

    3 4

    4 5

    5 6

    2 6

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

    for me i was just considering nodes on shortest path from a to b. when i removed that condition i.e checked for every node, I got AC.

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

      Your name :D, I'm dreaming to learn dp too :(

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

    While your conjecture is correct, it is not necessary that the sum of lengths of paths ab and bc in the optimal answer is equal to the sum of lengths of shortest paths ab and bc.

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

    Issue with that approach is, the paths doesn't have to be shortest for both nodes individually, there can be a case that, individually path for A and C is not shortest from B, but because of common prefix being longer, total cost can be lesser.

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

    the first thing, ans must be long long, not int

    the second, i think you must try all v and the and is sum(1,BV) + sum(1,AV+BV+CV) (only if AV +BV +CV <= M )and get min

    because sum(1,BV) + sum(1,AV+BV+CV) not depend on p[i] or BV, it depend on both, so u want to try all

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

    You solution was wrong in a special case. You need check it can be the answer. Just BFS in the Edge 3 times,From A,From C,and the last From B To check it can be the answer.The total of V must <= M,and then to update the answer You should update the answer in every possible point. Hope it will help you.Good luck!

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

Great Round! Problems were very interesting. Just feel bad because I started around 20 mins late due to personal issues....

Solved ABC. Couldn't solve D (failed Test-2). Any ideas?

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

    Fix some $$$s$$$, which will be intended common sum of all pairs.

    1) Show that you can always change the sum of any pair to $$$s$$$ in 2 changes

    2) When can you change the sum to $$$s$$$ in 0 changes?

    3) When can you change the sum to $$$s$$$ in 1 change?

    Then, use some kind of data structure so that you can answer for all $$$s$$$ in $$$1 \leq s \leq 2k$$$ and get the min over all of them as your answer.

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

    Construct intervals for each pair as follows:
    Each interval corresponds to choices of $$$x$$$ where this pair can be shifted by changing atmost one element of the pair. For example: if $$$k = 4$$$, and the pair is $$$(2, 3)$$$, the interval is $$$[3, 7]$$$. Then, sweep through all intervals by moving one step at a time, from $$$2$$$ to $$$2k$$$. At each step, you can compute the current score by seeing how many intervals overlap at this point (the depth). You will also need to consider those intervals contributing $$$0$$$ at this point, which occurs exactly when $$$x$$$ matches the sum of the pair corresponding to that interval. All those intervals not covering the current $$$x$$$ must contribute $$$2$$$ to the score.

    https://codeforces.com/contest/1343/submission/77572280

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

      Seems like a great approach. Mine was too complex that I spent too much time and ended up not being able to solve it within contest time. Haha. Nonetheless, solved it with my approach.

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

    Thank you Shisuko and ameya! Understood both your solutions.

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

what is the greedy solution of D?

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

    I think, D is DP question. For each pair, calculate the maximum and minimum value, you can get in 1 change. Also calculate the number of pairs adding up to some x.

    min=min(a,b) + 1 max=max(a,b) + k

    Then maintain segments, and iterate from 2 to 2k, counting how many need less than one change. you know the ones needing no changes, so you can calculate the numbers needing one change, and the rest need two changes. Find the minimum of that.

    https://codeforces.com/contest/1343/submission/77536701

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

    Not sure if this counts as greedy or not, but anyways:

    Calculate how many pairs exist with this or that sum using a map. Enumerate all possible target per-pair sums. From each of them, the number of steps needed is n / 2 — — <number of pairs such that you can't reach the sum by changing one number>. The former is already in the map, the later can be computed if you notice that for pair <x, y> (WLOG assume that x <= y) the minimum that you can reach with one operation is x + 1, and the maximum is y + k (two binary searches can be used here). Then just select the best target sum and output the answer for it.

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

Great round, guys!

We are going live now:

https://youtu.be/ppk9pXL9rR4

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

People with rank between 2300 and 11100 all solved 3 prob, so you have 9000 person solved 3 problem, bad choice of difficulty of the problems IMO.

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

Wow, hardest problem A I have seen, I was able to solve B and C easily. But I got stuck on A. :(. Could anyone shared how they approached it? Thank you

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

    You have to find any a $$$P=2^K-1$$$, starting from $$$K = 2$$$, that divides N. Then print $$$\frac{N}{P}$$$.

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

      Can you explain why 2^k -1? I only know a(r^n -1)/r-1 to be the summation of geometric progression.

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

        Let us look at the numbers in binary form-

        $$$2^0 = 1$$$

        $$$2^1 = 10$$$

        $$$2^2 = 100$$$

        $$$2^3 = 1000$$$

        $$$2^4 = 10000$$$

        Now, $$$2^0 + 2^1 + 2^2 + 2^3 = 2^4-1$$$ (i.e. 1111 in binary from)

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

    The trick is to know that x+2x+4x+...+2^kx=x(1+2+4+...+2^k)=x(2^(k+1)-1) because it is a geometric progression. So you could precompute the first 32 numbers 2^n-1, and look if any of them divides n

    You can find out more information about that in here

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

[Deleted]

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

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
  • For D my solution is probably incorrect but approach seems fine
  • We have to do something like find range of sum of both elements such that only 1 element is changed. like for the test case of: 6 6 5 2 6 1 3 4
  • the ranges be like [5:11] for arr[0] and arr[n-1-0] and [3:9] for arr[1] and arr[n-1-1] and so on
  • Then do something like psum[left]+=1 and psum[right]+=-1 for each pair of elements as stated in the problem.
  • Then do the prefix sum across it.
  • Then add the actual sum of these pair of elements as in that case we won't need to change even one element as psum[arr[i]+arr[n-1-i]]+=1
  • Then find max value of x which satisfies most ranges.
  • The answer being n-(the above found max val)
  • But I think there is some repetition in it. Can someone explain the issue with this soln??
  • EDIT: The code is: https://ideone.com/sb6eFB
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is very similar to the solution I used to solve D, except that I used a Binary Indexed Tree to quickly process the psum[left] += 1 and psum[right] -= 1 updates.

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

    the range for arr[0] and arr[n-1-0] will be [5:12] , for arr[1] and arr[n-1-1] will be [4:12] and so on if value of k is 6 (seems like from the example)

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

Went for the W by skipping D and trying to solve F since I had an idea...ended up solving none of D, E, F :(

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

in D sample test case 1 :_ part 3 : 8 7 6 1 1 7 6 3 4 6 why is the answer 4 ??

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

    you can always change some a[i] to have x is k+1 so the answer <= n/2

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

Yay. I solved the first 5 with a penalty of 141.

If only I was in competition, and not OOC...

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

There was a mistake in Problem C in the 4th test case explanation during the contest. i.e [1,−1000000000,1,−1000000000](assume all numbers are underlined) due to this I was confused and consumed 5 minutes. but now it's fixed.

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

Do these numbers also include those participants who have rating above 1600?

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

can anyone give a strong test case for problem D?

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

    I've made a strong test case that my programme failed on. 1 8 7 4 7 7 7 6 6 6 5 The answer is 2, we should change the first number and the last number.

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

i sent the answer of d in time and it not counted . can u help me in this .

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

What is the solution for F?

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

    It is basically brute force.

    First, decide what can be put at $$$p_1$$$, and brute all of them. From problem constraints, the number must be contained in a segment with length 2, and it must not appear in more than one length 2 segment. (Why?) Then, you can also decide on $$$p_2$$$ since it is just another element in the segment.

    To decide what $$$p_3$$$ is, you can pick a not-yet-used segment. There is only one valid segment, and it satisfies the following:

    1. It contains exactly 1 unused element.

    2. For the already-used elements that also exist in this segment, they must be put in valid range in the answer array. (e.g. if you are deciding on what $$$p_6$$$ is, and the current segment has length 4, the 3 used elements must be in $$$p_3$$$, $$$p_4$$$, $$$p_5$$$, but in any order)

    Then, the one unused element is $$$p_3$$$. If you cannot find a valid element, you can cut this branch. Follow this approach until $$$p_n$$$.

    I coded it in a $$$O(n^4)$$$ way but I believe $$$O(n^3)$$$ way of this exists.

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

    77550191 $$$O(n^4/32)$$$ using bitset

    77584382 $$$O(n^2)$$$ using the fact that only the last and maybe the first element appears once in the input

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

      Can you explain your O(n^2) solution.

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

        Lemma: Only the last and maybe the first element appears once in the input

        You know that one of them is the last element, fix the last element and remove its segment (it's unique), again the lemma is true, keep doing it while the last element is unique, when it is not, one of the elements is the first, then fix the first element, now the last element must always be unique and you can restore the permutation.

        So summarizing, you have two possible last element this take $$$O(2*n^2)$$$ and each one can return two possible first element, so you need $$$O(4*n^2)$$$

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

Why are the ranks of official standings (not unofficial) ambiguous? some of them,3 questions answered,penalty 100,rank 4501. some others, 3 questions answered,penalty 99, rank 4904. why is it that people with more penalty are ranked better? there are more such ambiguity as well....

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

    Sometimes when you refresh Div3 rounds during the hacking phase it removes unrated contestants, but after the hacking phase it will not be ambiguous

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

excuse me, problem E, is graph connected ?

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

    obviously, when it's stated clearly that there is a path between any two pair of nodes.

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

    Yes, this fact is mentioned in the question at least twice. The second line of the question says — It is guaranteed that there is a path between each pair of vertices (districts). The second last line of the input section says — It is guaranteed that the given graph is connected.

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

Hello! I have two submissions for problem E. The only difference between them is how I read the prices. 77571570 gives me wrong answer on test 22. 77571013 is accepted.  Can you tell me please why the 1st submission encountered a problem despite that the prefix array if declared as long long.

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

How do I give input for hacking in problem A.

I tried giving like

4

1000

10

134

234

but says invalid input. Can someone explain why?

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

    There needs to be a valid answer. There is no valid answer for 134

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

Actually D is not as hard as it seems. I solved it greedy. For each pair a[i] and a[n — 1 — i] we need to count three numbrers: 1) sum of a[i] and a[n — 1 — i] without changing a[i] or a[n — 1 — i] 2) min sum of a[i] and a[n — 1 — i] if we changed a[i] or a[n — 1 — i] 3) max sum of a[i] and a[n — 1 — i] if we changed a[i] or a[n — 1 — i]. First is just a[i] + a[n — 1 — i], second is min(a[i], a[n — 1 — i]) + 1 (we take the min value and make other 1, thus we get the min sum), third is max(a[i], a[n — 1 — i]) + k. Now we need to differ each of them from others. We can do it by matching a number to each value: 0 for first, -1 for second and 1 for third. Then we put this three values in the array and sort it. Not we need to iterate over array and count the answer. Time complexy O(nlogn) because of sorting the array.Sorry for my poor English.

Code.

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

    i calculate three value as you, but i don't sort them, i use prefix for two last value ! 77542245

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

      Oh, nice idea, thanks.So we can reduce time complexy to O(n + k) with your idea. But it works in 300+ seconds, can you please add this to your code to see how fast it will be.

      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
      cout.tie(NULL);
      
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        yes, right ! you can replace false and NULL with 0, it is shorter :v

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

    Same idea. Just make it easier to understand. Code

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

    I calculated the three values but hadn’t sorted it, so I failed on this test case(I made it): 1 8 7 4 7 7 7 6 6 6 5 The correct answer is 2 but my answer is 3. Do anyone know why? Do I have to sort it?

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

Any DP approach for problem D?

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

very good contest ,I love it but i think it is a bit difficult as a Div.3

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

77574862 This is giving wrong answer for fourth test case if someone could help. Thanks :).

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

    My solution: BFS from A, B, C. cal d[0][u] is the shortest length from u to A, 1 for B and 2 for C

    Any move way must have some u which the path is A -> U -> B -> U -> C and then the length is AU+2BU+CU.

    So we use exactly AU+BU+CU p[] of m p[]. and because the weight from U to B is calculated twice, we'll use BU first p[] for them.

    So we can solve problem by for U from 1 to n, each U we call the weigth if we move A -> U -> B -> U -> C and get min.

    Only calculate if AU+BU+CU<=m

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

Misread "district" as "distinct" in qE :/

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

    Thought I was the only one. I was getting WA due to the distinct part lol

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

https://codeforces.com/contest/1343/submission/77576736

wrong answer 39th numbers differ - expected: '1', found: '2'

Is it any chance to see 39th test case?

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

    Sorry ; I couldn't do this in your code itself ; as I am bad at using Python.

    BUT LUCKILY YES ( Click on view to see test cases ) ; and you may also see ; the solve function ; to how I did it ( in case you get into this sort of trouble in future ! )

    I hope this helps !

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

can anyone explain the approach for problem E??

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

    Note that a possible shortest path follows the form of A -> k -> B -> k -> C, where k is any vertex in the graph. Define A[k] as the shortest distance from node A to node k (similar definitions for B[k] and C[k]). Note that we can further break this down into two parts: there should be a total of A[k]+B[k]+C[k] distinct edges visited, with B[k] of those edges being visited twice. We want to take the smallest edges to be repeated, so we sort our prices array and generate prefix sums for fast queries. Now, you can do BFS to calculate the minimum distances for A,B,C and iterate over k. It'll look something like min(psums[B[k]]+psums[A[k]+B[k]+C[k]]) for all k such that A[k]+B[k]+C[k] <= M.

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

      How would you guarantee that paths A[k], B[k],C[k] do not intersect to claim that there are A[k]+B[k]+C[k] distinct edges?

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

        There is no problem if they intersect, it still works. Vertex k can be same as B or C.

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

    I need to go from vertex A to B and then B to C minimizing the cost of travel. I have the flexibility to assign a weight to an edge from given weights.

    Obs 1: If I have to travel Q edges, I will always want to make them the Q smallest edges.

    Obs2: Let's say path from A to B has P edges and path from B to C has Q edges. The max edges I need to traverse is P+Q, but if somehow, I can find overlap between P edges and Q edges, that would be best since, this means, I am reusing smaller edges leading to a lesser sum. This tells us we need to go from A -> V -> B -> V -> C. so that V to B and B to V is reused.

    Let's say A — V is P edges, V to B is Q edges and V to C is R edges. I will assign V to B smallest Q edges. Then assign next P edges to A to V path and then rest R edges to V to C path.

    So iterate for all X from 1 to N and your ans is min of all.

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

Any Suggestion , what can be wrong in my logic for question D .

Mycode D

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

    This will TLE since you're doing T*200000. Note that T*N is passing the TL and not T*20000.

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

      In editorial complexity is O(T*n*logn) ,it still passes

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

        Yes.

        Understand that T*N is different from T*200000.

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

    You spend too much time in the memset! In editorial complexity is O(T*n*logn) ,it still passes,Because the totN<=200000 But you memset 200000 in every Case, So it TLE So you can fill the array to zero in every N just like this for(int i=1;i<=N;i++) Ins[i]=In[i]=0 But not memset(Ins,0,sizeof(Ins))

    Hope it can help you.Good luck!

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

Sir vovuh Can you please explain why I am getting WA on test 2 I think my submission does not have use of unitialised variable but I am getting Wrong Answer and the judge says it uses uninitialised variable Please explain where I am wrong in problem D . Sorry for my poor english and thanks in advance. I hope you will reply This is the submission link
77560252

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

How to solve problem F ????

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

Can anyone explain the solution of D?

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

    Call L=a[i] R=a[n-i+1] (because of my lazy xD)

    So if x=L+R, we use 0 replace, in range[min(L,R)+1,max(L,R)+k] we use 1 and 2 for other

    Call E[i] is the number pair have sum exacly i

    Call Up[i] is the number pair have max(L,R)+k=i (it means if x is more than i, we must use two replace)

    Call Down[i] is the number pair have min(L,R)+1=i

    we can see, if x in range [i,2*k] must use 2 then x in range [j,2*k] j<i also use 2

    And if x in range [2,i] use 2 so x in [2,j] j>i also use 2

    We call prefix for up and down Up[i]=Up[i]+Up[i-1], Down[i]=Down[i]+Down[i+1];

    In fact, we always use most n/2 replace for x=k+1 so the answer<=n/2

    Which x we have n/2 pair, E[x] pair have exactly value, so there is n/2 — E[x] pair wrong which use at less 1, have Down[x-1] + Up[x+1] pair must use two replace, so we must add Down[x-1] and Up[x+1]

    -> ans=min(n/2, n/2-E[x]+Down[x-1]+Up[x+1]) 2<=x<=2*k

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

      Hey I used exactly the same approach but using upper bound and lower bound 77581160 can you see what Ive done wrong

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

        I think upper and lower on X is wrong

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

          Upper Bound will give me index of that element greater than R and if its index is X i can say there are (N-X) elements greater than R

          For Lower Bound Will give me Index of element Greater than equal to L and So this Index-1 will be the index of Number Smaller than L and so this +1 will be Number of Elements Smaller than L

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

            with a[i]+a[n-i+1] you can't know with 1 replace it can be x or not

            example a[i]+a[n-i+1]=12 (k=9)

            with 6 6 you can change to [7,15]

            with 3 9 you can change to [4,18]

            so with only 12 you can't know how much replace to get 6 or 18

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

              With [6,6] I will be stroing (1,15) and for [3,9] I will be storing [1,18] I am assuming initially Answer to be N Then substracting for Exactly similar elements and then Adding 1 for those who will bcome equal (After Changing both of their elements)

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

              Ok Done I got the error and got Accepted though after the contest

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

Can anyone explain the solution of D without the use of fenwick tree?

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

    /*THIS IS ONLY IMPLEMENTATION PART AS LOGIC IS ALREADY DISCUSSED ABOVE*/

    we can obtain the 3 values for every index i 1) min possible min(a[I],a[n-i-1])+1; ==> left most (l) 2) max possible max(a[I],a[n-i-1])+k; ==> right most (r) 3) there sum a[I]+a[n-i-1] ==> its sum (s)

    now create 2 arrays 1) enter array => it will look after range l-s (including both) 2) exit array => it will look after range s-r (including both)

    now we can iterate over all cases by loop like int ans=n;int curr_savings=0; rep(i,1,2*k+1) { curr_savings+=enter[i]; ans=min(ans,n-curr_savings); curr_savings-=exite[i]; }

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

    For each i from 1 to n/2 consider this: L=min(arr[i],arr[n-i+1]) and R=max(arr[i],arr[n-i+1]) .

    -If we make 0 changes we can get sum equal to arr[i]+arr[n-i+1]

    -If we make 1 change we can make the pair sum equal to all the values from L+1 to R+k (except L+R which needs 0 changes).

    -To get all other values as sum you need to change both arr[i] and arr[n-i+1](2 changes).

    Now using this create a partial sum array.Read from here

    Iterate from i=2 to i=2*k on the array and take the minimum value.

    Link to my code: https://codeforces.com/contest/1343/submission/77568588

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

where is editorial

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

One more case of cheating by using forged hacks. See: hack details

MikeMirzayanov vovuh Please check. A particular value of n is hardcoded to print wrong answer intentionally. The hacker and hacked user have similar user name as well.

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

    Nothing new, it happens all the time.

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

      Yes, but I haven't found any solutions like that. (or it's already hacked)

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

77581160 Can someone tell me what Ive done wrong in Problem D getting WA on tc 461 of test 2

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

The server was amazingly smooth today!

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

Hi Codeforcers,

Can anybody give me a hint to solve div 3 candies A problem? I know that it forms a GP of sum of n series but couldn't get my way around to solve the problem?

Help if anybody can. Thanks in advance.

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

    For some valid x and k, n = x*((2^k)-1).

    Hence, check for all k's such that 2<=k<=30, if for some k, n is divisible by (2^k — 1), you got the answer, x = n/(2^k — 1)

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

    n is sum of a geometrical series. Use formula for geometrical series apply the conditions. Hope you will get an idea what to do

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

    Yeah. It is a G.P.

    You need to find (X,K) such that X * (power(2,K-1) — 1) = N

    Start from K = 2 to 50 (why 50 suffices? since N <= 10^9, hence 2^50 will exceed 10^9) and check for value of K, (power(2,K-1) — 1) divides N, whenever it divides, you can print that corresponding X.

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

My Approach for D:

Since array has n elements so there is n/2 pair(a[i],a[n-i+1]) and sum of pair will be x.

Minimum possible sum for a pair is 2 and maximum possible sum for a pair is 2*k. Then x must be between 2 and 2*k

I calculate no of replacement for each x between 2 and 2*K and finally take minimum of all x[i]

Now the challenge is to calculate each x[i] in O(1) complexity

For each x[i] there will be 3 types of pair according to sum of pair

  1. For some pair sum of pair will be exactly x[i], for such pair no replacement is needed.

  2. If x[i] is range (min of pair + 1 , max of pair + k) then this x[i] can be achieved changing one element of the pair.

  3. If value is out of that range then two value of pair will be changed to achieve x[i] as sum of pair.

I calculate range for 1 change for each pair, then i take an array ar and ar[i] indicate how many pair can reach i changing one element.

Finally for each x[i] I check how many pair reach x[i] making 0 change(t), 1 change(y) and 2 change(z)

minimum of all y+2*z is answer.

MY Submission

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

[Deleted]

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

    you have pairs:

    1+6 = 7
    3+1 = 4
    8+7 = 15
    5+6 = 11
    

    let x=11 then:

    5+6 = 11 (replace 1 with 5)
    3+8 = 11 (replace 1 with 8)
    8+3 = 11 (replace 7 with 3)
    5+6 = 11 (stays same)
    

    result is 3 because there are only 3 replaces

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

    5 3 8 5 6 3 8 6

    3 changes and sum of all pairs is 11

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

    Yes 5 3 8 5 6 3 8 6 One of the example with 3 changes.

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

Solution for D

Reference

Problem recap

Given an array with n elements (where n is even), find the least number of operations such that the sum of each number with its mirror element is the same (i.e. a[i] + a[n-1-i] = x for all i)

Observations

  • The key observation here is to realize that there are 3 options for any pair a[i] and a[n-1-i]. These are: make no changes, make 1 change (only one of the element changes) and make 2 changes (both elements change).
  • Consider two mirror elements, a[i] (lets call this x) and a[n-1-i) (lets call this y)
  • If (x > y) then swap them such that x is always smaller or equal to y
  • If you were to make zero changes to either element, their sum would be exactly one number (i.e. x + y)
  • With one change, their sum could range from (x + 1) to (k + y). This is because you could make y=1 (set y to the smallest possible positive number per the problem constraints), or you could make x=k (set x to the largest possible number per the problem constraints)
  • With two changes, you could cover the entire range of possible sums (i.e. 2 through 2*k — since you could make both x and y either equal to 1 or to k, or anything in between)

Implementation

  • We need a way to mark these possible sums and ranges for each mirror pair of numbers. Use prefix sums.
  • Create an array for tracking frequency of zero changes.
  • Create an array that tracks ranges for one change (this will be a prefix array).
  • For each pair, zero changes are needed when sum = x + y. Increment zeros[x + y].
  • For each pair, mark the range that they can go to with exactly one change. This is the range (x + 1) to (y + k) described above. To do this, increment ones[x + 1] by 1, and decrement ones[y + k + 1] by 1.
  • Compute the prefix sum of ones. Essentially, ones[sum] = number of pairs that can add up to sum with just one change.
  • Then iterate through each possible sum (from 1 through 2*k) and see how many changes are needed to get to that sum. Cost = 1 * (ones[sum] - zeros[sum]) + 2 * (n/2 - ones[sum]). You need to subtract zeros[sum] from ones[sum] to avoid over-counting (as ones[sum] includes zero[sum]). Similarly, you need to subtract ones[sum] from twos[sum] (there's n/2 pairs in total and to find pairs where both elements need to be changed, remove ones[sum] which excludes the pairs that can get to this sum with either one or zero changes)
  • Find the sum with the lowest cost and that's your answer
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Great explanation, Thank you :D

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

    in the cost formula why it is not 1*(ones[sum]-zeros[sum])+ 2*(n/2-(ones[sum]+zeros[sum]))as ones[sum] holds the value of sum we can get with one change but we also need to exlude the sum we got with zero changes,right? Can you please clarify it?

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

      Say you have just two elements: {1, 5} with k=5. So zeros[6] = 1. And ones[2...10]=1. Notice that we have added one to both zeros[6] and ones[6]. So ones[x] is cumulative and includes zeros[x]. The actual definition of ones[x] = exactly_ones[x] + zeros[x]. Hence if you just want to get the twos[x], it's sufficient to just remove ones[x].

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

    Great solution, thanks for sharing!!

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

    seriously thanks broo...greatest explaination so far

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

Can someone please see and tell why my code(attached below) was shown the wrong answer for the second question when submitted, Highly appreciated

import java.util.Scanner;

public class Prob2 {

public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner s=new Scanner(System.in);
    int t=s.nextInt();
    for(int i=0;i<t;i++){
       int n=s.nextInt();
       ans(n);
    }
}
public static void ans(int n) {
    int odd=n/2;
    int six=6;
    int eight=8;

    int ans[]=new int[n];
    if(odd%2!=0) {
       //System.out.println("NO");

    }else {

       for(int i=0;i<n/2;i++) {
         if(i%2==0) {
          ans[i]=six;
          ans[i+n/2]=six-3;
          six=six+4;

         }else {
          ans[i]=eight;
          ans[i+n/2]=eight+3;
          eight=eight+4;
         }

       }


    }
    if(n%4==0) {
       System.out.println("YES");
       for(int i=0;i<n;i++) {
         System.out.print(ans[i]+" ");

       }
       System.out.println();
    }else {
       System.out.println("NO");
    }


}

}

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

    For n=12 it will generate 6 8 10 12 14 16 3 11 7 15 11 19 where 11 is repeated. all the value must be distinct.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Is there someway to extract complete test case as I'm getting this in Problem E
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try printing out the input when current case = 320, add few ifs so that the solution does not fail on cases 1,2 and 3

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

IMO D was difficult for a normal Div #3 contest, wasted a lot of time on D :(

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

Can someone tell whats the issue with my approach to Problem E? Wrong answer on Test Case 4 1. Get the shortest path from a to b then b to c. And store all the edges of the route. 2.sort the edges based on the frequencies in descending order. And then allocate the prices from smallest to largest. The edge repeating the most will have the minimum price and so on.. I am getting wrong answer in test case 4 on 320 line which is not visible and hence don't know what edge case am I missing. Any help would be appreciated

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

    I think shortest path is not optimal always.

    Let a to b has 3 edges

    Shortest path from b to c has 3 edges which is different from a to b

    Total edge 6

    Now consider there is another path from b to c which has 4 edges(not shortest) but two two of them common with a to b

    Then total edge 3+1=4

    So second one will be optimal although shortest path not taken.

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

Here as the virtual Moss for Codeforces, busting cheaters and getting them out of their bills. I hereby present to you the Inter-College Cheat Group(including NITs and HIET). restfulCoder pawangeek ankitkh6842 Yatin_Kwatra saranshgupta1999 sreejit_007 sachinganguly69 bit.ly_cfdiv23boostlive inductor harry_india vknjwnjc rustic_coder

Not to mention their ranks are (18-19-20-21-22) in today's DIV3 If this comment doesn't serve the purpose of un-rating or banning them. I don't what will. here goes the solutions

77562772

77564410

77556321

77565949

77562595

77563089

77564679

77549578

77565649 He thought adding comments will save him

77564027

77558019

77557813

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

Can somebody prove the intuition of problem E? I had the same idea during the contest but i don't have an actual proof why the case when the sum of the distances is greater than m can be excluded.

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

    The sum of the Distances, greater than "m" will always be excluded, because, you don't have a Prefix Sum, for prefix[i], where i>m.

    Since, we are getting only "m" values, we have "m+1" Prefix sums, so, there is no meaning to include the case, where the sum of distances > m.

    I hope, it helps. Thank you!

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

      Yes, i understand this, but why a case when we repeat some edge, and the total number of edges exceeds m is excluded? For example, in the path from node to c, there are some edges identical to the edges from b to node. Isn't this case possible?

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

         We're breaking down the road from A -> N -> B -> N -> C.

        We're also assuming that the number of repeated edges are those from B -> N(Green Edges)

        So Here A -> N = 4

        N -> B = 1

        B -> N = 1

        N -> C = 5

        So total different numbers used = 4(A->N) + 1(N->B) + 5(N->C) = 10

        But the number of different edges are 6, so we should exclude this? Why? Because there's always a path that minimizes the answer and uses less than m edges, And that happens here if we chose A as our N.

        So In our case We're always looking for a node $$$X$$$. Such that There's no repeated edges from A -> N and from N -> C, So only repeated edges happen at B -> N.

        Consider the following 4 cases,

        1-C lies before A, as in the photo, So the best node to choose would be A itself.

        2-C lies between A-B, then the best node to choose would be C

        3-C lies after B, then the best node to choose would be B

        4-C lies on an path that is connected to a node between A-B, then the best node to choose would be that node that connects us to C.

        I guess that explains why it's fine to ignore if the edges > m, Because there's always a path with edges <= m and will produce better answers.

        Forgive the paint skills.

        Edit

        You can also consider if the AN+NB+BC > m, then just keep using the greatest price. It'll produce a correct answer.

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

Damn vovuh this may very well be the best round I ever took part in!!! The problems were extremly cool, especially problem E. Idk but the round just felt very good. Congratulations on doing such a good job!

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

I have made a video which explains the approach used in D along with the code explanation. The link is here.

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

Can anyone give a another solution of F? Here have a O(N^4/32),But it need bitset. I want to get a O(N^3) solution if anyone know. Thanks very much. I think a solution can be check for i from 1 to N and for each ans is a number is can be. At last it got the answer? but I can't prove it! Does anyone have a O(N^3) solution? thanks.

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

My submission does not fail in any of the test cases I made.. Plz check if you could find one https://codeforces.com/contest/1343/submission/77567195

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

I don't understand when the ranking settlement will be completed. It seems that sometimes it will be settled immediately after the hack stage, sometimes it will take longer

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

Oh my goodness, D was easy man. We just missed that during contest. Now, I tried to sketch and finally found it was just a basic prefix sum. Thanks, vovuh. This round was great and educative like the previous one.

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

When do the ratings get published?

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

are the servers down or what?? My submission is in queue for like 15 minutes

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

    During the system test, all the participants' programmes were being tested so it's slow. Now the final standings have come out.

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

When will the rating changes be calculated?

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

when the rankings will be updated??

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

It was a great contest. I really enjoyed the problems. Though, I have some suggestions for future Div. 3 rounds:

  • Although I understand that multiple test case problems make tests stronger, they become quite bothering when it requires careful initialization of several arrays. Problem D and E are the examples, where we need to initialize multiple arrays until certain points (or dynamically allocate them), and things like memset(arr, 0, sizeof arr); have possibility to get TL. Of course, one can argue that being careful about these things is also a part of the problem, but this distracts participants from the core idea of the problem greatly and makes them waste a lot of time getting TL over and over again, not even realizing what went wrong with their code. Also, we can see that a lot of participants got AC with running time very close to the limit because of the initialization, and I'm sure that many others have failed to fit in time with very similar logic, possibly because of bad luck or just a little less optimization. My argue is that it will be better to either decrease the max number of TC, or decrease the max of $$$n$$$ when the time complexity isn't super important (like what I've done in one of my problems), especially when the contest is for beginners.
  • I see problems like A in many 2A's and 3A's, where the implementation is super easy if you know how to simplify the mathematical expressions. But that 'simplification' is not very easy for beginners, as we can see that more people have solved B than A. I'd like to expect more straightforward problems for 3A instead of requiring mathematical knowledge or observation, because it's not the easiest subject for people who want to participate in a programming contest.
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I second this. Ideally, I think the easiest problem of Div2 or Div3 should not use concept higher (or harder to come up) than multiplication and division, let alone powers or GCD/LCM's.

    They are 8th/6th grade subject in Korean curriculum respectively. Not everyone who codes know that (believe me). As long as we are targeting them, it's encouraged to help them solve at least one problems in a contest, so they can figure out how things go on.

    I think this discussion is more relevant to be in here, but anyway.

    OTOH I'm not trying to blame the setter for anything: This is just my suggestion!

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

    In the past few contests, after system testing, I often saw some programmes gotTime limit exceededorRuntime erroron the last test cases(for example,Time limit exceeded on test 84). Here are some examples:

    In Codeforces Round 635 (Div. 1):

    Hazyknight(who got 15th place) gotRuntime error on test 84.

    Rewinding(who got 17th place) gotTime limit exceeded on test 33.

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

      Why do I have lots of downvotes? What did I do wrong?

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

    Global variables are bad habit in programming, so it's totally fine when people fail because of them.

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

Hidden.

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

    What is the point of submitting from two accounts anyways? The score you get is time based. Faster the submission, greater the score.

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

      But he can check if his solution will receive WA or Accepted if he uses two accounts

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

    You are not allowed to use multiple accounts in a contest.

    Read the rules and pay more attention next time.

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

      I haven’t found the rules. Could you please provide me the link.

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

        Click on "register" for the next contest, you'll see this rule

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

    Logging in parallel of one person with two accounts should result in ban of both accounts. Then submitting the same solution twice, on both accounts within a contest does not happen without intention.

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

very easy D solution in linear time using prefix sums https://codeforces.com/contest/1343/submission/77524012

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

what does "trusted participants" in standings page mean?

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

    "trusted participants" means users who will be rated after contest(if contest is rated), I think.

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

I have registered for this course and solved 3 problems but even after final standing i did not get any rating. Profile still shows UNRATED before my name.

This was my first codeforces contest. Please help me. How i will get rating and where to see my ratings.

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

Waiting for Ratings  Waiting for Ratings

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

[user:blee][submission:blee/77566304][problem:1343D]My solution to the problem seems to, unintentionally coincide with another.This might be because a major part of my code has been copied from a GeeksForGeeks code (on how to find if a particular number lies within given ranges): https://www.geeksforgeeks.org/count-the-number-of-intervals-in-which-a-given-value-lies/ This was published before the competetion.My points for this round are now 0. I request you to please look into it.Please don't penalise me, the code is entirely mine. Thanks

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

I was not careful for the submission.

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

Hello codeforces,

I have a question about your giving rank algorithm. I solved three questions in this contest which is 2nd, 3rd and 4th. And other people who also solved three questions but 1st , 2nd and 3rd. So I solved a question with high difficulty so I should have high ranking but it is not the case. Those people have high ranking. This is not fair. Why is your algorithm to give rank doing that? A person who solve high difficulty question, you should give them priority.

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

    I think it should be like the contests in AtCoder. it has both score and penalty. The scores of different problems are different.