By awoo, history, 5 months ago, translation, In English

Hello Codeforces!

On Jan/31/2022 17:35 (Moscow time) Educational Codeforces Round 122 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

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

The problems were invented and prepared by Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

UPD: Editorial is out.

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

»
5 months ago, # |
  Vote: I like it +65 Vote: I do not like it

Hoping for a great contest on Chinese New Year's Eve!

»
5 months ago, # |
  Vote: I like it -36 Vote: I do not like it

Best of luck everyone!

»
5 months ago, # |
Rev. 3   Vote: I like it -16 Vote: I do not like it

~

  • »
    »
    5 months ago, # ^ |
      Vote: I like it -38 Vote: I do not like it

    from the last 6 contests, odds are not being in my favour.

»
5 months ago, # |
  Vote: I like it -36 Vote: I do not like it

Hope this educational round completes without interruption.

»
5 months ago, # |
Rev. 2   Vote: I like it -41 Vote: I do not like it

happy coding

»
5 months ago, # |
  Vote: I like it +25 Vote: I do not like it

Happy luner new year :3 hope this will be a good contest to say good bye this year :3

»
5 months ago, # |
  Vote: I like it -9 Vote: I do not like it

Good luck everyone

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

Good luck and high rating for everyone!

As a competitor in China, I'm quite happy to have something to do one New Year's Eve!

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping this educational Round doesn't goes like last one!

»
5 months ago, # |
  Vote: I like it +42 Vote: I do not like it

Hi, pls upvote I couldnt think of a smart comment this contest

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I wish everyone good luck for the contest!

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope for good luck.

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Sad that last unrated educational round wasn't compensated with a rated one.
But hoping this one goes well, GL & HF.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

first time hope for a great one!

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

Score distribution when?

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

    It will be held on extended ICPC rules. It's like div.3, contestants will be sorted by the number of solved problems,then penalties

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

      Either the questions were easy or I have been evolved from div 3, the contest was really confidence-boosting, thank you

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Best of Luck everyone!!
May you not get WA at the very first problem. LOL

»
5 months ago, # |
  Vote: I like it +32 Vote: I do not like it

Happy Chinese New Year!

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this contest, a negative point is given to every wrong submission? Or it is the penalty-based contest?

»
5 months ago, # |
  Vote: I like it +2 Vote: I do not like it

This is gonna be my first division 2 contest after getting my first rating on a division 3 contest. Contest means full of excitement and inspiration to make me a better version of myself. And hacking phase is awesome and breathtaking. Smile!

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i know that feel) It was my first round ever and frankly speaking it was interesting. Hope you havd fun too )

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

      Hmm. You have solved your first problem! Now wait for 12 hours and you will get your first rating.

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

Do you know why the problem rating information is not shown for recent rounds' problems? (Codeforces Round #767 (Div. 2) and later)

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah! From last 2-3 contest rating information is not show.

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

all awoo's contsts are great

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I always think that is we should solve problems from top to bottom or bottom to top? As I see lots of coders start solving problems from 2 or 3 questions

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think we should start solving from top. Because difficulty is in ascending order that is problem A is easier than B and B is easier than C and so on.

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

    As far as I know, out of all problems you solve finally, each minute you put a problem unsolved is counted as penalty.

    Suppose you solved 2 problems("A" and "B") in a contest:
    Let's assume "A" takes 10 min and "B" takes 20 min to solve.
    - Case 1 : You started with "A" and solved "A" after 10 minutes of the contest and "B" after 30 minutes of the contest. Penalty for these two is (10 + 30) = 40 minutes.
    - Case 2 : You started with "B" and solved "B" after 20 minutes of the contest and "B" after 30 minutes of the contest. Penalty for these two is (20 + 30) = 50 minutes.
    

    So it is good to start with problems that take less time to solve.

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

      yes, this is always optimal for educational and div 3 rounds which have same points for every problem.

      while for normal div2 rounds you may solve B or C first(depends on which you are comfortable) as they can provide you more points if you solve them first

      but still its not always the case that you will benefit every time. though i prefer to start from A

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

Hi. I am new here. Wish me luck !

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

Good Luck to all Coders ! ! ! awoo's contest are fantastic ! ! ! Never give up the CodeForces ! ! !

»
5 months ago, # |
  Vote: I like it +6 Vote: I do not like it

First time on joining any contest. I dont expect anything but to be better. Such a vibe

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

all chinese coder are giving a down vote it seems XD. happy new year to all chinese._|_

»
5 months ago, # |
  Vote: I like it +6 Vote: I do not like it

chuxi forces :)

happy lunar new year to those that celebrate!

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

What's the operation in D? And why in educational round it's not described...

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

Why in Problem D, sample hasn't been explained. :( T_T

»
5 months ago, # |
  Vote: I like it -32 Vote: I do not like it

Omg, it took me 10 minutes to solve the problem A, and 8 minutes to solve problems B and C together, cool

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

    It felt interesting to me, that in rated rounds I try to not even waste a single second, while you also take the time to announce your submit status xD.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it -45 Vote: I do not like it

      I dont solve today's round on this acc

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

        ??? But it is still your time ???

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

        This is even worse because you are publicly admitting to alts.

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it -15 Vote: I do not like it

          It's not mean, that I have alts, its mean that I'm sure my solutions are right

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Lets be real, everyone has alts. I think its fine as long as people don't give rounds from both of them at a single time.

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

            Not everyone has alts. I don't have an alt. And it's not fine if you smurf using your alt.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you tell your approach for C!!

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

Problem E looks interesting but it also seems to 100 Kms above my interesting interval ;_;

»
5 months ago, # |
  Vote: I like it +14 Vote: I do not like it

it was my first round ever and thankfully to authors it was pretty fun. Thanks!

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

solution for D?

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

    calculate the number of operations required to convert ai to bi and then knapsack.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Did same but got Memory Limit Exceeded on Test 12. Value of k given is much larger than 1000 * (maximum steps required for any ai to convert to bi). Took k as minimum of k and steps*1000 after contest. Got AC ;-;

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

        There's a much tighter bound, use steps * 12. You can reach any number less than 1000 in less than or equal to 12 steps.

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          How you come to this conclusion that "we can reach any number less than 1000 in less than or equal to 12 steps"

          • »
            »
            »
            »
            »
            »
            5 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I calculated the steps for all numbers less than 1000 and print the max. This is required as the given constraints for k (<=1e6) is not suitable for knapsack.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How to calculate the number of steps to convert ai to bi?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1633/submission/144748935 [TLE in test 12, problem D] How do i optimize the knapsack dp for choosing the indicies?

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

    Observe that if k is greater than sum of all operations we can skip knapdsack dp. And sum won't be too big.

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

    the maximum number of operation to obtain any number from 1 to 1000 using that operation is 12. So k can be at most 12*n. So if k > 12*n just make k = 12*n

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

      Thanks Eren and Liviu, got AC. Feeling stupid right now!

      Liviu how did you come up with "#ops to obtain any number 1 to 1000 using that operation is 12"?

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

        just printed the maximum element after the calculation was done. I needed that number to be small enough in order to not get TLE.

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        In fact you can write another program to calculate this.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ah, didn't think of this to limit k. Good observation. Thanks!

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      but why it is giving runtime error if we are not limiting k=12*n ?

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How can I calculate the number of steps required to convert ai to bi?

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        DP. You can calculate it for every number from 1 to 1000 cause b[i] <= 1000. Now you know that dp[1] = 0 cause a[1] = 1 already. And now make a for for each number 1 <= j <= i and let dp[i+i/j] = min(dp[i+i/j],dp[i]+1). This means take the minimum number of operation to reach the number (i+i/j) coming from i state (which is already calculated).

        Ex. you know dp[1] = 0 dp[2] = 1 dp[3] = 2 dp[4] = 2 dp[5] = 3 and you want to calculate dp[6].

        dp[6] = min(dp[3]+1,d[4]+1,dp[5]+1) since you can reach 6 for 3 adding 3/1 for 4 adding 4/2 and for 5 adding 5/3 or 5/4 or 5/5.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Real good observation, got AC. The question was really nice. First I calculated moves required in DP and then applied knapsack

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I used dynamic programming for D, can someone show me why it get WA? https://codeforces.com/contest/1633/submission/144729710

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your DP state is incorrect. Use 01 Knapsack DP : Link

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I thought what I'm doing is 0-1 knapsack. I thought that looping in reverse order of the dp state (dp[i] = best total coins given total cost i), makes it so the element of the knapsack can't be re-used. Anyways thanks for the tip.

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

      I compared with the guy who got #1 and saw that my dp state and recursion are exactly the same as his (144679861). After looking at the case I failed on, it's because of this code

              int best_coin = 0;
              for (int i = 1; i < 12 * 1001 && i <= k; ++i) {
                      best_coin = max(best_coin, dp[i]);
              }
      

      Starting from i=1, instead of i=0, breaks for the case

      2 0
      2 1
      4 14
      

      because the optimal solution (take the second coin using zero operations) has zero cost.

»
5 months ago, # |
  Vote: I like it +13 Vote: I do not like it

My opinion about problem E.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For E, is this lemma correct?

  1. There can be atmost 2*n distinct MSTs.
  2. These 2*n MSTs will occur in 2*n non-overlapping ranges from [1, 10^8]
  • »
    »
    5 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    O(m^2) distinct MSTs.

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

      Care to try hacking my code? It should run in $$$O(m ^ 3 \log ^ 2(m) + k (n + \log(m)))$$$ if that is the case which should be too slow to pass, even in 4 seconds.

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Any hints for E?

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

        Lol!!! Have you hacked into the system ? I did the same complexity but still get TLE on Test 8, while your code ran in ~ 100ms. I even removed one log(m) factor by not sorting every time in binary search but just merged the negative weights and positive weights by their abs value. Still I am getting TLE. submission

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I think I calculate optimal MSTs in a different manner from you I think. There is no case in any of the tests (including hacks) that has number of MSTs $$$> m$$$. So my solution actually runs in $$$O(m ^ 2 \log^2(m) + k(n + \log(m))$$$.

          For example, on test 8, my code finds 252 ranges, your code finds 32000.

          aryanc403, any ideas on how to generate a case with number of MSTs $$$> m$$$? I can't seem to either prove this idea or generate such a case.

          • »
            »
            »
            »
            »
            »
            5 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Oh! Cool... Then it seems that about (m^2 — m) swappings of edges are unnecessary. i.e. They dont change anything in the spanning tree. I get that it should be definitely less than m^2 but only m msts are there. Interesting. Anyways thanks for the interesting result. It would be nice to see atleast some intutive proof from aryanc403 or someone.

            • »
              »
              »
              »
              »
              »
              »
              5 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Me neither. I tried hacking his soln but couldn't create a test case with more than O(m) MSTs for his soln.

              Rn, I don't have any proof for O(m) upper_bound on MSTs.

              Spoiler
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hint for problem D

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    NHK bro?

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

    k doesn't need to be 1e6

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you tell me how did you derive that during contest?

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        if you try to calculate how many steps are needed to reach numbers 1 to 1000 (using simple dp) you will notice that there is an upper bound over these numbers (which is 12). So the maximum usable value of k would be 12*1000 and the rest is standard knapsack problem

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    knapsack

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

For problem E which group of x should suffice to check? I tried all edges values and every (edge[i]+edje[j])/2 values but got WA

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Well I fall in love with 4th problem (-.-"). Great Contest!

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, Ceil(log2(bi)) is star I think because this many steps is required to change 1 to the particular number.It's just a theory based on 1 + (1/1) => 2 + (2/2) or 2 + (2/1) etc.. for each number.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No this fails for b[i] = 7

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      well, it think 5,6 can be generated in 3 ops, and 7 can be generated in 4 ops.So ceil(bi/2) I am basically confused between 2. Or else something else I have no clue now after trying some of them.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Video Solutions for A-D for anyone looking

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you all for preparing this round :)

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me what I did wrong to get TLE in problems D ? https://codeforces.com/contest/1633/submission/144751205

My logic- I use a directed Graph to connected numbers that can be visited. After this I use Dijkastra to find shortest distace of each of the numbers from 1. Now when that is found I use qudratic dp to get the answer.

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

D was a nice question. 0-1 Knapsack DP hidden behind a good observation — max operations on any index i can be atmax 12. So if k>=12*n, ans would be sum of array c otherwise apply standard DP for 0-1 knapsack.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is it possible to get the cost to transform a number to b[i] using greedy?

    something like,

    k=1
    while(a<b and k<=a):
       while(a+a/k > b) k+=1
       steps+=1
       a+=a/k
    if(a==b)
       return steps
    
»
5 months ago, # |
  Vote: I like it +11 Vote: I do not like it

problem d approach is as knapsack dp problem ?

»
5 months ago, # |
  Vote: I like it -24 Vote: I do not like it

Knapforces

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

Problem F is nice .

But I wrote the dfs order as index ,and debug for about 40 minute (how can this pass the first 12 tests ???).

And I found this silly mistake in the last 30 seconds ..

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

    Share my solution here :

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

Problem A is exact copy of this TOPCODER ROUND. Even the number 7 is same.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Solution for C ?

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

    Notice that the sum of k<2*10^5.

    That means the solution should be O(n).

    To Check who wins- find number steps needed by both to win (that means if the character kept attacking how many rounds are needed to defeat the monster and vise-versa)

    character_steps = ceil(monster_health/character_damage)

    monster_steps = ceil(character_health/monster_damage)

    if character_steps<=monster_steps then character wins (First chance is of character so <=) Checking who wins is o(1)

    To find all possible combinations in the way we can use the coins- we can go from 1 to coins (i) and use i as the coins used for damage boost and use coins-i as the coins for health boost and add the boost to the damage and armor. We can do this in O(n)

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

It seems that D can be passed in $$$\mathcal{O}(nk)$$$ time

Maybe it will be better if the time limit is changed to 1s ...

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

    It's not actually $$$O(n\cdot k)$$$ where $$$k\approx 10^6$$$.

    Since the number of operations needed for any $$$b_i$$$ to get constructed is at max $$$12$$$, if $$$k\ge 12\cdot n$$$, you can simply print $$$\sum_{i=1}^n c_i$$$. Otherwise you can use a knapsack dp solution so solve the problem in $$$O(n\cdot k)$$$ time where $$$k\lt 12\cdot n$$$.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      why?, if k >= 12*n then we can take all coins?

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

      But in fact,some guys solved this problem in $$$O(n\times k)$$$ and I cannot hack them. Are there any stronger cases than this? QaQ

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I can't open the link you gave, it says "access denied".

        Can you provide me with such a solution?

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Sorry,that is my problem.

          This!

          $$$n=1000,k=10^6,b_i=1,c_i=10^6$$$ cannot hack him. QaQ

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

            Actually the total number of operations is $$$\approx 10^9$$$, so it might be possible for a solution to pass under 2 second time constraint. Plus the operations done inside the test case loop are simple enough. The only thing that user needs to optimize is the space used which cannot be $$$O(n\cdot k)$$$.

            I've tried making test cases with max constraint and the program runs perfectly within 2 second time limit.

            Suffocating,rsgqwq

            • »
              »
              »
              »
              »
              »
              »
              5 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Hey, you stole my comment! Just kidding.. =)

              The time constraint is $$$2$$$ seconds by the way ))

              • »
                »
                »
                »
                »
                »
                »
                »
                5 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Um, I hadn't read your comment until now actually.

                The time constraint is 2 seconds by the way ))

                Thanks fixed!

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes I understand that, but what I want to express is you can pass this problem even if you use the 01-pack dp for every $$$k$$$ but not just when $$$k\le 12 * n$$$

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think K is just for confusing as max operation that can be done will be 12*n so we have to take k=min(k,maxOperation)

    Time=O(12*n*n) and space=O(k)

    Here is my code : (https://codeforces.com/contest/1633/submission/144742657)

»
5 months ago, # |
  Vote: I like it +32 Vote: I do not like it

How to solve E?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the hacking phase??

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There might be some solutions which either shouldn't pass according to the given constraint or are actually wrong but the systems tests don't cover the cases where they fail.

    Codeforces gives the users, an opportunity to identify such solutions and hack them (submit a valid test where they fail). Obviously it does not guarantee $$$100\%$$$ strength to the new test set formed after hacking.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Really nice contest.

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Today is the day I will learn Knapsack, Thanks for the round

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D how do I find the number of operations for each number I tried to do it but got WA here is my code: https://ideone.com/Fm0aPE

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I precompute them using BFS. Find the shortest path from 1 to all nodes

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

    You can write a brute force dp for this. Just make sure you have an idea about dp solutions.
    Consider $$$dp_i$$$ stands for the minimum number of operations required for making the number $$$i$$$ starting from $$$1$$$.

    Then, it can be seen that before forming the number $$$i$$$, we might have had a number $$$j$$$ such that the value of $$$\lfloor \frac{j}{x} \rfloor$$$ was equal to $$$i-j$$$ for some $$$x$$$ (because that's the only way $$$j+\lfloor \frac{j}{x} \rfloor$$$ will become equal to $$$i$$$). Let's iterate on $$$j$$$ too. We will then need to find the value of $$$x$$$ (if it actually exists).

    Finding the value of x
    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      I will understand and try this thanks.

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

In problem D , I assumed x should be a divisor of a[i] out of nowhere, and now I won't reach expert because of this.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well it says ai / x floored (note the floor function brackets) which indicates that x doesn't necessarily divide ai.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, I read it initially, but while implementing missed it completely.

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

    Same Here, but i figured it out after 1 hour and 3 wrong attempts :(

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

    Same thing bro

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

Help needed in Problem D. This is my solution What I did was calculate operations for every b[i] and then select those with best (c[i]/operations) in decreasing order. But this gives WA. Any ideas why?

EDIT: The way I calculate minimum operations is probably wrong. I'll just wait for the editorial.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think you answered your own question. You can't solve 0-1 knapsack with greedy.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am actually taking the entire points and not just a fraction of it. I wrote greedy because I sorted the numbers in decreasing order based on their worth (points divided by operations) and selected them greedily. Maybe I should remove greedy knapsack from the comment if it is confusing.

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What I am understanding from your comment and code is that you are trying to solve this knapsack which is impossible with greedy.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Never be greedy :p

    c — 10, 4 operations — 2, 1 k = 1

    according to you 10/2 is better than 4/1 but we cannot take 10/2 as limit is k=1.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am checking for that as well, if operations are greater than what is allowed I skip it.

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No the point is that you cannot solve the knapsack problem with a greedy approach. Take for example values — 3, 2, 2, 0 and cost — 2, 2, 2, 1 and capacity=4. If we take elements greedily, we will take the first element because 3/2 is more than 2/2. However, the optimal solution is to take the second and third element,so this approach fails.

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh yeah I knew this. How did I overlook it. Thanks.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello, Could anyone point out my code fails at the 12th testcase of 2nd pretest? https://codeforces.com/contest/1633/submission/144752948

Thanks.

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

    I am using a binary search like approach to calculate the cost to convert 1 to the given bi. Please Help!

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, for going through my code. I found that I couldn't mathematically prove my binary search approach is right and as it turns out it indeed was wrong. I then used a regular BFS approach and it worked!

      But still I didn't knew exactly at which num it fails, Thanks for your effort and spending the time. Super helpful my man.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the solution for D? I feel the concept of knapsack can be implemented here.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it can be implemented but first you have to calculate the minmum number of steps required for each number from 1 to 1e3 (range of numbers in array b) and this can be calculated using DP then apply knapsack to get the best items to take but notice you don't need all 1e6 operations

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ohhh.. I missed the step where we have to calculate the minimum number of steps required. Thanks for the explanation.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I've wasted too much time and energy on D thinking b_i<=1e6. Sad

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

I like the idea of E but its implementation is way out of my skillset :(

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

    Klog(m^2) passed for me with maps in 2000ms. Hack it, maybe? :p

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a question, does an unsuccessful hacking attempt on Hacking phase gives us any penalty in some ways?

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

In Problem D, number of operations to convert 1 to x is (index of MSB in x) + (number of set bits in x) - 1

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No need of fancy math. run n*n bfs as {1,1}

    {i, steps} -> {i + (i/j), steps + 1} for all 1<=j<=i

    states = 10^3, TC: 10^6 bfs

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

      No need for fancy BFS. Just run 2 for loops =)

      int w[1001];
      for (int i = 1; i < 1000; i++)
          for (int j = 1; j <= i; j++) {
              const int t = i + i / j;
              if (t <= 1000)
                  w[t] = min(w[t], w[i] + 1);
          }
      
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How do you know this regularity?

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

    Interesting, can you give some detailed proof maybe?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Have u tried? I did the exact same thing first but got 2 WA. Then I switched to BFS.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did this in contest and got wrong answer, brute force implementation after contest gave AC, are you sure this is correct? (maybe I implemented it wrong)

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

    This isn't correct:

    Try for 19: 10011
    Index of msb: 4
    setBits: 3
    Your ans: 4+3-1=6
    Actual answer: 5
    How to reach: 1->2->4->8->16->19 [19 = 16 + 16/5] in total 5 steps

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

    This does not work for n = 23

    number of operations should be 6 and the equation yields 7(4 + 4 — 1).

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did this mistake too.

    15 = 1111 Here ans ≠ (3) + 4 — 1 = 6

    But optimal soln is 5 (1->2->4->8->12->15)

»
5 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Happy Chinese New Year for every Chinese!Hope all of you will get good grades in xcpc(icpc&ccpc) in this year!

»
5 months ago, # |
  Vote: I like it +65 Vote: I do not like it

What happened to rainboy??

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Is standing broken?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hint for problem E?

I got WA on test 7, I mapped all queries, if a query occurs an odd number of times I sort all edges by abs(x — wi) and find MST with Kruskal's algorithm.

My code: https://codeforces.com/contest/1633/submission/144721913

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is problem B solvable with binary search on answer? I know that its possible to solve using a simple observation though.

»
5 months ago, # |
  Vote: I like it +39 Vote: I do not like it

When you get traumatized by interactive binary search problems xd

meme
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

E was too hard to code

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, Why I am getting tle on testcase 12 https://codeforces.com/contest/1633/submission/144763541

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

    $$$k = min(k, 12n)$$$

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      after considering this condition, still got TLE under python3 .... here is my code

      BTW, I found another code, which was accepted during contest, but also TLE now...

      really weird ....

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

        codeforces.ml ? kinda sus

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it +5 Vote: I do not like it
          Spoiler
        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          er... codeforces.ml is just a mirror site for codeforces main-site, since main-site is not stable for visiting here ...

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

      Actually you could solve it even without that optimization =)

      I use the following justification:
      1. Knapsack performs $$$k * n = 10^6 * 10^3 = 10^9$$$ operations.
      2. CPU speed is 2.4Ghz or $$$2.4 * 10^9$$$ operations per second.
      3. If we access the data properly, CPU will utilize it's fast cache and registers instead of waiting for data from RAM (RAM is 10 times slower than CPU cache).
      4. We have 2 seconds limit on the problem, so we have some room for overhead computation and round trips to RAM.

      144830143


      By the way, I like the code that I got after incorporating the idea of short circuiting.
      That is, we don't do $$$dp$$$ if $$$k$$$ is large enough.
      This short circuiting allows us to reuse unoptimized code from above without using magic constants k = min(k, 12 * k). Everything works out by itself and the code would work even if we have a different problem with larger constraints, so we don't need to recalculate new constant for 12 * k.

      Short circuiting

      144830112

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

same code, but different compiler, one gave wrong answer but one got accepted(after contest)

144765410 144698088

Anyone knows the reason ? Help will be appreciated :'(

Upd:My second submission also gave wrong answer later in main tests due to float, so I think

double >>>>>>>> float

  • »
    »
    5 months ago, # ^ |
    Rev. 5   Vote: I like it 0 Vote: I do not like it

    It's because you are using float and float is not accurate, i had the same problem from few days my solution got accepted in c++ 17 but not in c++ 20 and someone told me why this happened you can check the reason float fail sometimes to give AC here
    PS: changing float to double in your code give AC, so when u want a floating number next time use double!

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

It Was a Nice Contest!

»
5 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Can someone clarify this? In E when I used edges as vector of vectors , it gave TLE. In some AC submission I saw they have used structure for edges. When I used structure instead of vector, it passed. Why this behaviour?

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I didn't know there is a space optimized version of solving KnapSack

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

Is O(NK + KlogK) the intended solution for E or is there something better? I am processing the queries in a sorted order and just updating the edges in the MST only when the sorted order of the edges changes in the next query. It is easy to see that the sorted order of the edges won't change more than M * M times.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

for problem D, anyone succeed to get accepted by python3? why I always got TLE? here is my code

BTW, I found another code, which was accepted during contest, but also TLE now... weird ....

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I was able to make it up until 8'th test with Python3: 144836343
    Exactly the same code with PyPy 3.7 (64 bit) passes for 187ms 144836442

    Probably the difference is in the input speed.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yeah, you are right, man. it seems pypy3 is much faster than python3 here ... but to be honest, I don't know why ...

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

In Problem D test case

4 4
1 7 5 2
2 6 5 2

cant we make [1 1 1 1] -> [7 1 1 1] in 4 steps, as conversion from 1 to 7 takes 4 operation and then answers should be 6+2+2+2 = 12. Whats wrong here

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Never Mind, Seems like I have completely misinterpretted the question

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem E. There can be at max e*e event points where we need to re-calculate MST. giving e*e*e*log(n) as preprocessing time.

for given x we need to find y<=x in above event point list and do some calculations.

I did it with y = map.lowerbound(x) -> Gave TLE complexity O(k * log(e * e))

People did it with presorting x and using two pointer to get y for given x- TC: O(k * logk)

SInce log factor of sorting is better than log factor of map, hence i got tle.

I think problem shouldn't have such tight constraint that sorting pass but map.lower_bound() fails. What do you guys say?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You could presort y and lower_bound for every x query (without using two pointers and presorting x), map just has terrible constant factor.

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

Can someone tell why this method of finding the minimum number of operations to convert 1 to b[i] is wrong :-

This is what i've done — Im finding the nearest power of two (call this num) for b[i] and then convert num nearest power to b[i]. To do that first i find the difference between b[i] and num and update num greedily such that num + [num/x] <= b[i] till i get num == b[i].

This is the piece of code for finding this minimum number of operations.

Code
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Greedy doesn't work because you cannot make sure that by incrementing with the largest possible move will lead into minimum possible weight.

    Example

    So apply dp here too (similar to coin change).

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I've met some strange behavior today in this competition with D language (dlang, dmd). In problem C in test 7 in the input was used number "10000100000". This code:

import std;

void main()
{
    long a, b;
    scanf("%ld", &a);
    getchar();
    b = readln.strip.to!(long);
    writeln(a);
    writeln(b);
}

gives different results:

1410165408
10000100000

In current version of Dlang compiler (2.098) scanf works correctly. So @admin maybe you could update the version of compiler?

Everybody else who uses D, I know not so many people, maybe better to use readln :)

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    scanf("%lld", &n);
    

    fixed the issue. Maybe the question was in the 64-bit version of my compiler

»
5 months ago, # |
  Vote: I like it +20 Vote: I do not like it

I usually don't write such stuff, but I must say I'm really disappointed with the pretests for problem C. For such a short mathy problem, You'd expect to give constraints in a way that don't give an overflow with a pretty standard solution. And if there is a standard solution that gets an overflow, it's only right to give a not-so-difficult-to-construct pretest that prevents it.

For educational rounds it's even more important to have strong pretests on the easier problems, due to the fact each problem weighs the same.

Thanks, a CM that instead of getting to master for the first time, gets a -95 :(

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

    Yeah already got a contender for the worst problem of 2022.

    Hey but let's rejoice we can just move ahead with int128 from here onwards and forget about these silly problems the setters come up with.

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

      but longlong is enough here

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Tbh, most of the times there is at least one problem with ridiculously high constraints in Edu rounds.Moreover, almost always the pretests are weak to encourage hacking. Maybe you have been just lucky to not get FSTed before.

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

      I haven't seen that many problems with ridiculously high constraints (that can't be handled by long long) in Edu rounds. Can you give examples? Moreover, it sounds extremely weird to me that the pretests are weak to encourage hacking. After all, the purpose of the pretests is to validate solutions... But I agree that I might have been somewhat lucky to not get FSTed until now.

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

    Yoav What do you mean by "You'd expect to give constraints in a way that don't give an overflow with a pretty standard solution"? Pretty standard solution here is to use long long and it got AC here

    https://codeforces.com/contest/1633/submission/144683828

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Look at my hacked solution. In my opinion my approach is quite standard, and is correct but gets an overflow. After checking again the constraints it is easy to see there can be an overflow. So if the constraints are made in a way that there could be such overflow, there should be pretests that cover it.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Will my rating be affected with this competition?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

C.Kill The Monster Video Tutorial : VIDEO LINK

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

When the rating will update?

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

Good contest and interesting tasks !

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Happy lunar new year

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Are editorials released?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please help me figure out why my solution for D isn't working? 144791596

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try

    1
    1 6
    41 
    1 
    

    The expected output is $$$0$$$ while your code produces $$$1$$$.

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

In my opinion, 2 seconds TL on problem D was too much. It let some unoptimal solutions pass.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, I saw many O(n*k) solutions passing

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey There!

Can someone please tell me what stress testing is and how to use it during the contests?

I received this suggestion from some revered person :"You can try stress-testing to find the test cases you're wrong at" I often apply the right logic in contests but end up with failing a few test cases.

Best, Wandering Brain

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can write naive solution (even exponential one), generate some small test cases and compare your solution against naive on those small cases. To make it efficient you should automate the process of generating random test cases and comparing your solutions.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot!

      Sounds like somethings different. Will try to implement this and see how it works.

      Cheers!

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

I should have done problem C in python :( (Wrong Answer on testcase 13 due to Overflow)

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello guys. I'm new in codeforces and this was my first contest. I solved one problem. Will my rating increase?

»
5 months ago, # |
  Vote: I like it +12 Vote: I do not like it

FSTforces :(

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

    +100 delta to negative delta

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Got FST on both C and D today.
      If this had happened on Topcoder, it would not be unusual because TopCoder emphasizes on proving your solutions with your own edge cases as their questions are usually more about implementation (imho).
      But this is certainly not what I used to expect from Codeforces rounds as the questions are usually more about coming up with the idea and being guided about whether that works or not with pretests.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what is FST?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

fstqwq

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I figured out that in D, knapsack was the way to go, since we can interpret that weights are no. of operations to reach each element. I found the required way to reach all elements in nlogn, and since N was <=10^3, thought knapsack would work, but k was <=10^6. I do not know how to lower this. any hint would be appreciated

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Using DP on the number transitions, you could pre-compute the number of steps required for each of the numbers (1->1000), and because this was kind of logarithmic (max. 12 steps), you could effectively reduce 1e+6 to around 12000, which is manageable.
    My Submission (has FSTed)

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thank you, I'll try again. Why wasn't this came in my head earlier

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    See this: gfg

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The maximum operations required to obtain any b will be logarithm in nature so the actual max value of $$$k$$$ will be $$$nlogn $$$. Hence, the problem becomes knapsack DP with complexity of $$$n*n*logn$$$. Check out my solution, it did not FST

    144759233

»
5 months ago, # |
Rev. 3   Vote: I like it +10 Vote: I do not like it

I suddenly realize that in Educational Rounds solving ABD with more penalty time will be ranked lower than solving ABC with less penalty time. So, in such rounds instead of solving harder problems it's important to guarantee the solved easier problems are correct.

I initially "solved" ABCD but just got FST on C which makes me feel sad. (C makes me realize "long long overflow in C++". Perhaps I should use Python 3 for all such large integer problems.)

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It hurts

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

    C gave another chance to Python users to mock CPP users ;-;

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

IMO, This is one of the worst contests ever. Felt like the tasks as well as the test was created just as a formality. Please don't create this type of contest.

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

    Can't disagree with you, I always highly rate the educational round but this one was far below standard.

»
5 months ago, # |
  Vote: I like it -18 Vote: I do not like it

I'm down-voting this contest and this post , because of weak testcases for problem C and problem D , that causes me negative delta! From ~2800 to ~8000 ! This content damaged my rating a lot. But actually the problems were interesting.Thanks.

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

    Couldn't agree more! Weakforces

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I dunno know why you were downvoted. If the pretests are gonna be this weak they might as well not include them at all and leave participants to make submissions on a gamble.

»
5 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Weak test cases for D!!Even an O(nk) solution passed.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Really Nice Contest. Loved from D. Looking forward to solve more such awesome Dp problems . Kudos to problemSetters!!

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

144799151 Problem C, my submission is failing on TC 13. Can anyone please point out what's wrong?

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

    Its overflowing when you do the operation $$$(attacks - 1)*dm$$$ . Very weak testcases this time

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

Pretests for Problem C were very weak, I had an overflow in my code and it passed, if pretests were strong then I would've gotten a WA but usually codeforces tells us if we have an overflow and I'd have been able to AC.

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

Two Contests back : I might become CM Now : Specialist , I am coming

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain why this submission for D is failing test case 21?
The Submission
Thanks.

»
5 months ago, # |
  Vote: I like it +65 Vote: I do not like it

To not keep you waiting, the ratings are updated preliminarily. In a few hours/days, I will remove cheaters and update the ratings again!

  • »
    »
    5 months ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    Down with codeforces From now on weakforces

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Chill dude, it was just one mediocre contest with weak pretests.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you make a post when this testing is done as well?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is there any update? Are the ratings updated?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The test data in question C makes the variable overflow of "long long" in some incorrect writing, which is nicely designed

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

    'Nicely Designed' can be either sincere or sarcastic based on the result, lol.

»
5 months ago, # |
Rev. 15   Vote: I like it 0 Vote: I do not like it

Can anyone explain why the remaining queries in problem E are defined by the modular arithmetic formula instead of straightaway giving them? Edit : Seems like it was because the number of queries is very large my bad

»
5 months ago, # |
  Vote: I like it +16 Vote: I do not like it

I got accepted in A, B and E. But I FSTed in C, D.

New year, New FST, New -189, New Candidate Master -> Expert.

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

    Take it easy, Maybe it's the Pillar of a future success.

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

    Still better than falling 400 rating into pupil from high expert over the course of several contests.

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

From now, I will check overflows even after using long long. :(

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

In D, I got a TLE just because I created a new function to calculate my ans. Can anyone explain how does that work?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For your D just apply a check that if k >= 12 * n print the sum of all c[i]. Because at max it would take 12 operations to convert 1 to b[i].

    You don't need to go for k = 1e6. Your AC code for D runs in 1996ms, after applying the check it runs in 15ms.

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

please please please, can someone guide me whats's wrong with my solution ?144804903

update -: resolved

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    short int t;
    

    It is the issue. short int has range -32,768 to 32,767 and in constraint number of testcase is upto 50,000, which is greater than 32,767 causing runtime error. Change it to int. You will get AC.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ohhh damn, my stupidity (habit of using short int for test cases), but why is it showing 'Signed Integer Overflow' on line 35 instead of showing on t ? very very thanks for the help !

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

gone from positive delta of 160 to negative delta of 20....XD. D got hacked and C failed in system tests due to overflow. I hope to improve in next round

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

    my 3rd contest ever C failed in test 10 after showing accepted whole night . could have reached 1k rating now stuck at 898 only.\

    python solution with same logic now shows accepted.

»
5 months ago, # |
  Vote: I like it +26 Vote: I do not like it

This was my first round in Codeforces, and I am going to share my ideas while solving the problem A and B.

1a. Problem A — O(1) idea

during the contest phase, I did not come up with the idea to change the last digit only (which was, I think, the expected solution). Instead I focused on the fact that the input is 3 digits maximum, and the divisor is 7. 1 (mod 7) = 1, 10 (mod 7) = 3, 100 (mod 7) = 2. Therefore I thought it would be possible to make up every difference in 0~6 with these 3 digits. However I decided that this is not the correct solution as it would be impossible to find all the cases in 2 hours for me.

1b. Problem A — BFS idea ( O(27^steps)? ) (My final solution)

This time I found that the input is only of the two cases, TWO DIGITS or THREE DIGITS. I thought BFS would finish relatively early. (This speculation turned out to be correct, and it all ended in one step.) So I did a BFS on changing each digit to 0~9 (non-leading digits) or 1~9 (leading digit), and the runtime was only 15ms. Sounds good enough to me.

2a. Problem B — O(n^3) idea

I only had this idea for a very brief amount of time, and I knew this idea would always TLE out on even the weakest cases. and you probably guessed what it is. Yes, the good old "counting every substring we could find". Good thing I didn't have to try this.

2b. Problem B — O(n) idea

I really hesitated on this idea, and I could not easily prove that this would always work. I did focus on the fact that we have to maximize the amount, and later on it turned out to be the correct approach but I had the suspicion of DOES THIS REALLY WORK for probably 20 minutes or so. It's the classic answer of (cnt0==cnt1)?cnt0-1:min(cnt0,cnt1) where cnt0 and cnt1 is the amount of 0's and 1's after counting the whole string. I submitted the answer as a gamble to myself, and I am still amused that this turned out to be the correct answer.

So yes, this is a list of my ideas in my first Codeforces round. I really hope I have a better performance next round or so, but I would really appreciate learning new ideas from Educational Rounds and Div.3/Div.4 Rounds.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Will you update changes of rating and ban cheaters?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

video Editorial For problem C : VIDEO-LINK

»
5 months ago, # |
  Vote: I like it +28 Vote: I do not like it

In educational codeforces rounds, I personally think that each problem should be given points as given in other Div2 and Div1 contests. Because if some person was not able to solve C due to some small error but was able to solve E. Still, he/she will be having less rating than others because time taken to solve E was more than C.

»
5 months ago, # |