By arsijo, 9 days ago, translation, In English,

Hi all!

This weekend, on Oct/06/2019 18:05 (Moscow time) we will hold Codeforces Round 591. It is based on problems of Technocup 2020 Elimination Round 1 that will be held at the same time.

Technocup is a major olympiad for Russian-speaking high-school students, so if you fall into this category, please register at Technocup 2020 website and take part in the Elimination Round.

Div. 1 and Div.2 editions are open and rated for everyone. Register and enjoy the contests!

The Elimination Round authors are BledDest, MikeMirzayanov, Ne0n25, PikMike, Roms, adedalic and me. This round would also be not possible without the help of our testers: KAN, chemthan, gisp_zjz, Kallaseldor, JeffreyHo, danya.smelskiy, Juve45, thank you so much!

Have fun!

UPD.

Unfortunately, the round is unrated.

Tutorial.

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

»
9 days ago, # |
  Vote: I like it -40 Vote: I do not like it

gisp_zjz Liu HongYang niubi

»
9 days ago, # |
  Vote: I like it -65 Vote: I do not like it

Why arsijo?

»
9 days ago, # |
  Vote: I like it -48 Vote: I do not like it

EZ Queueforces..

»
8 days ago, # |
  Vote: I like it +52 Vote: I do not like it

Oh,come on. Let's enjoy this contest!

»
8 days ago, # |
  Vote: I like it +33 Vote: I do not like it

A worth-joining contest to end my boring week incredibly <3 <3

»
8 days ago, # |
  Vote: I like it +13 Vote: I do not like it

Hope that we are not going to be punished with long queues

Just for not thanking MikeMirzayanov for this awesome platform. XD

»
8 days ago, # |
  Vote: I like it +13 Vote: I do not like it

Let's hope for clear problem statements

»
8 days ago, # |
  Vote: I like it -121 Vote: I do not like it

Kindly, after the contest, up-vote this comment if the contest was good, down-vote if it was bad, do not vote if it was mediocre.

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

    I am from the Future The contest will be good and your comment will have many downvotes.

»
8 days ago, # |
  Vote: I like it -27 Vote: I do not like it

»
8 days ago, # |
Rev. 2   Vote: I like it +39 Vote: I do not like it

.

»
8 days ago, # |
  Vote: I like it +9 Vote: I do not like it

It's going to be my first div.1 contest, so excited for that!

»
8 days ago, # |
  Vote: I like it +3 Vote: I do not like it

what is rule of contest? ICPC or Codeforces?

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Have Fun!!! You will be good.

»
8 days ago, # |
  Vote: I like it -12 Vote: I do not like it

hope arsijo remember the contest he last conducted which was a heck

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

What will be the Scoring Distribution, no of problems etc ?

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

Time to go IM

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

"All you bug are belong to me" — or how to open problems?

»
8 days ago, # |
  Vote: I like it +5 Vote: I do not like it

"Independent" QueryForces!

»
8 days ago, # |
  Vote: I like it -13 Vote: I do not like it

*Me after solving A, B and C

"Let's go to comment section"

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

i guess its an unrated contest because of long queue and not being able to access cf

»
8 days ago, # |
  Vote: I like it +3 Vote: I do not like it

I am not able to submit for last 15 minutes!!

»
8 days ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

Go To Hell DDOS Attacker (The Problems Were really nice )

»
8 days ago, # |
  Vote: I like it +96 Vote: I do not like it

Unfortunately, we had a DDOS attack during the round. Codeforces did not work for a few hours. Obviously, the round will be unrated. Also, there will be an additional Technocup Elimination Round.

»
8 days ago, # |
  Vote: I like it +71 Vote: I do not like it

Seems like Codeforces is working again <3

This DDoS attack is such a shame, because the contest was quite nice in my opinion. Do we have any idea why would someone do that? (Or if it was a DDoS and not some other issue)

»
8 days ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

"Nice round"

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I was doing so well in this contest! :( So angry at the ddos attacker. Hopefully the next round is soon.

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

I would like to submit it quickly. Korea is dawn, but I can't sleep because I wonder the answer is correct. :X

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

F*ck you ddos attacker btw How you solve div2- C ?

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

    Binary search, I guess

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain ? :)

      • »
        »
        »
        »
        8 days ago, # ^ |
        Rev. 6   Vote: I like it 0 Vote: I do not like it

        Basically you binary search for the minimum length you can get

        And to test if a length is ok

        You place the maximum ticket prices at positions where both programs occur i.e. positions divisible by both a and b then the next batch of maximum ticket prices go to positions divisible by a if max(x,y) equals x or b if max(x,y) equals y and the last batch of maximum ticket prices go to positions divisible by a if min(x,y) equals x or b if min(x,y) equals y

        • »
          »
          »
          »
          »
          8 days ago, # ^ |
            Vote: I like it -8 Vote: I do not like it

          It's wrong. Get value sequence from 1 to d such that d minimum. not any value @@

          • »
            »
            »
            »
            »
            »
            8 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            hien2k.hy I don't understand

            Can you explain a little more?

            btw I just submitted and it got accepted

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

          your solution is actually correct

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Binary search on the number of tickets you will use. You can easily see that if the problem is solvable with k tickets, then it must also be solvable with k+1, and if it is unsolvable with k, it will still be unsolvable with k-1.

        To check if the problem is solvable for a given K, you have to use the k/lcm(a,b) most expensive tickets on the lcm(a,b) positions, the next most expensive ones will be used for the remaining a and b positions (if x > y use the a positions first, else use the b positions first). This guarantees a maximal value to help the environment.

      • »
        »
        »
        »
        6 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        you can use binary search. first sort the array the then we assume that we need to sold mid ticket and for valid mid we use binary search and in check function u can implement that if we sold the mid number of ticket than profit is more than we reduce right by mid-1 otherwise we increase left by mid+1. At last our answer is mid. you can see the my solution https://codeforces.com/contest/1241/submission/62071599

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      NO.. It's greedy

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I solved it with greedy we need to maximize sum we first take maximum values for (x + y) after that we take values to maximum of x and y and then to minimum of x and y

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

      btw i solve it with Greedy and my solution complexity is O(N)

      so for my solution i put the 3 possibility of discount into a vector in order to ignore i-th index which has no discount:

      1. x+y

      2. max(x,y)

      3. min(x,y)

      and then i sort the ticket price descending.

      for each iteration i mark where's the ticket price goes (3 possibility of discount) by putting it into queue.

      if at i-th iteration the discount is min(x,y) just add the value and put the index into a queue.

      if at i-th iteration the discount is max(x,y) we move the ticket price at min(x,y)'s queue to max(x,y)'s queue and put the current ticket price in min(x,y)'s queue since the current ticket price is lower than previous ticket price (sort descending)

      if at i-th iteration the discount is x+y we move max(x,y) to x+y and min(x,y) to max(x,y) and current to min(x,y)

      example:

      ticket price : 300 200 100 100

      discount : 1 1 2 3

      and here's how the ticket price move for each iteration

      • 300
      • 300 200
      • 100 200 300
      • 100 100 200 300

      source code: https://codeforces.com/contest/1241/submission/62074247

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

        PS: STL sort is O(n log n) so technically your solution isn't O(n)

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Suppose x > y, and the number of tickets sold (call it L) is known in advance, and we just want to know what the optimal profit will be. Let lcm be the least common multiple of a and b.

    Then the best strategy would be to place your most expensive tickets on multiples of lcm (since this gets you (x+y)%). You can compute how many of those there are in constant time (there are L/lcm of them), and you can use a cumulative sum array to compute the total value of all the tickets in that range (sort the tickets by descending price and sum from 0 to L/lcm). Similarly, place your next most expensive tickets on multiples of a (there are L/a - L/lcm of them), and your least valuable tickets on multiples of b (there are L/b - L/lcm of them), and use the cumulative sum array to get the profit. After you have these quantities, you can compute the total price and compare it to K to see if it satisfies the problem requirements.

    Now you want to know the minimum L. You can binary search for L, or (since the bounds are low) just do linear search. If you didn't implement the previous paragraph in O(1), you probably need binary search for this part.

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

    I had a pretty stupid solution. First sorted the list then used 3 queues for type a and b and both. for each length the sum is updated in O(1) with at most 3 push/pops. 62028584

»
8 days ago, # |
  Vote: I like it -9 Vote: I do not like it

 I submited 4 times. -150 points and get last time @@??? why

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

    If same code is submitted, its not a problem. Why did you keep changing code?

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

      I use to sv 3 and not show after i submit @@.

»
8 days ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve div2-D?

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

    I submitted bottom-up DP. We can show that any element will be moved at most 1 time. So there is exactly 3 options. We either move it to the beggining, move it to the end, or don't touch it. So it's DP[N][3], with DP[i] = minimum amount of turns to sort the first i elements, and [0..2] to denote those 3 options.

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

      Thanks. Nice solution!

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

      can u please explain why dp[i][1]=i in both cases. and why dp[i][2] is same in both cases

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

        Let's say [1] means move ith element to the left and [2] to the right. If we move ith element to the left, then it will become leftmost element in our array. In that case, the only possible way to sort the first i elements (considering we won't move ith element anymore) is to move the first i — 1 elements to the left, using exactly i turns. And if we move ith element to the right, then we don't care about how we sort the first i — 1 elements, because ith will become the rightmost element, thus it will be the same in both cases.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

From Queueforces to DDOSattackforces. I wasn't lucky at all the last 2 contests :(

»
8 days ago, # |
  Vote: I like it +41 Vote: I do not like it

Unlucky arsijo... Why problem occurs (!) always in his round?

»
8 days ago, # |
  Vote: I like it +6 Vote: I do not like it

why the blog doesn't thank MikeMirzayanov to the platform codeforces, maybe this is the issue xD

»
8 days ago, # |
  Vote: I like it +41 Vote: I do not like it

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

the statement of the problem Cdiv2 could be shorter . :)

i know you probably worked on the statements and you may have a purpose .

it was just an advice to shorten the statements as much as you can. :)

»
8 days ago, # |
  Vote: I like it +211 Vote: I do not like it

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

    We need a version of this pic with Mike + CF coordinators. Not just cut+paste in Paint, but some decent work.

»
8 days ago, # |
  Vote: I like it +21 Vote: I do not like it

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

Looks like a few people do not see some of their submissions. We are investigating the issue.

»
8 days ago, # |
  Vote: I like it +68 Vote: I do not like it

»
8 days ago, # |
  Vote: I like it +2 Vote: I do not like it

Hope upcoming educational will have nice problems as well!:)

»
8 days ago, # |
  Vote: I like it +18 Vote: I do not like it

Problem D is very similar to one task from CSAcademy (the only difference is that the given array was a permutation in CSA, but is doesn't really change the solution).

»
8 days ago, # |
  Vote: I like it +3 Vote: I do not like it

It feels like every rounds kinda DDoS attack, but this time bigger.

»
8 days ago, # |
  Vote: I like it +6 Vote: I do not like it

In div 1 F, are these random solutions hackable? 62022214 62023134

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I Was enjoying this round so much that I was reloading every now and then to see the problem getting resolved and never lost hope! Hard Luck arsijo!!

»
8 days ago, # |
  Vote: I like it +37 Vote: I do not like it

arsijo in your last 2 round, you forgot to thank MikeMirzayanov for platform and polygon. then both of this rounds became unrated !

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve div1-D?

»
8 days ago, # |
  Vote: I like it -19 Vote: I do not like it

arsijo's rounds are always unated!

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

Why are submissions and testcases kept hidden??....Or is this something, only I am facing??

»
7 days ago, # |
  Vote: I like it +19 Vote: I do not like it

It's probably the most upvoted unrated round.