Noobish_Monk's blog

By Noobish_Monk, 4 months ago, translation, In English

Thanks K1o0n for being the mvp of this round.

1992A - Only Pluses

Idea: Vladosiya

Preparation: K1o0n

Tutorial
Solution (Python)

1992B - Angry Monk

Idea: Noobish_Monk

Preparation: K1o0n

Tutorial
Solution (C++)
Solution (Python)

1992C - Gorilla and Permutation

Idea: K1o0n

Preparation: K1o0n

Tutorial
Solution (Python)

1992D - Test of Love

Idea: ArSarapkin

Preparation: K1o0n

Tutorial
Solution (greedy)
Solution (DP)

1992E - Novice's Mistake

Idea: Noobish_Monk, K1o0n

Preparation: K1o0n

Tutorial
Solution (Python)

1992F - Valuable Cards

Idea: Noobish_Monk

Preparation: Noobish_Monk

Tutorial
Solution (C++)

1992G - Ultra-Meow

Idea: Noobish_Monk, K1o0n

Preparation: K1o0n

Tutorial
Solution (C++)
  • Vote: I like it
  • +45
  • Vote: I do not like it

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

Thanks for the fast text editorial!

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

Thanks for the fast text editorial! :D

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

Thanks for editorial

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

tks for the tutorial :D

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

Could you also solve problem D by using game theory logic and designing an array that will mark spots that are winning and others that are losing, so an array w[d+1] for which w[d] is winning, for every i that path[i]=='C' w[i]=losing ... I tried to solve it during the contest with this approach, but failed on implementation so I want to know if the approach is valid to polish the implementation or to try a different approach.

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

    just simulate the game + greedy :)

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

      ok tnx

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

      Sounds like what I did but since I'm noob so test 2 failed, unfortunately

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

    Seems like you are looking for a dp solution, one of which is described in the tutorial. However it turns out you need to keep more information than a binary value in that array because of the swimming constraint

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

      Yes, but in an implementation with a vector<tuple<....>> I could keep winning state, if 1 a char('c',...), and swimming or jumping constraint, which I could update correctly so the game conditions are satisfied.

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

        I think my submission can help you understand the implementation details. I keep in each index a $$$pair$$$ indicating whether we can reach that cell or not, and $$$min$$$ water cells swam till now.

        Transitions are the same as editorial

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

          i just simulate his optimal moves (greedy). i am him.

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

            Ah yes I see what he meant now.

            small advice: try to adjust your indentation to $$$4$$$ spaces instead of $$$8$$$ as it's more readable, and name your variables for easier idea understanding (It took me much to understand your code) and also to help you in debugging matters

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

          Thank you :)

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

    I did it with graphs XD

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

Notice that n∗a−b is strictly less than 10^6 , i.e., it has no more than 5 digits.

Please edit that to 6 digits. Thanks!

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

A simpler implementation for F

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

    Could you please explain your solution?

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

      let $$$x$$$ be the number that will make our current segment good, means that if there is numbers in our segment such that $$$a_i \cdot a_j \cdot \cdot \cdot a_l = x $$$, the segment will be counted as good, however the problem wants only bad segments so we need to make sure that we can't have $$$x$$$

      notice that in order to have $$$x$$$ all of $$$a_i \cdot a_j \cdot \cdot \cdot a_l $$$ need to be divisors of $$$x$$$

      let $$$s$$$ be a set that contains any number that will make our segment good so initially it will be $$$s =$$$ { $$$x$$$ }

      now we iterate over the numbers, and check if this number is in $$$s$$$, if it's in $$$s$$$ then this number will make our segment good if we contain it with our current segment, we don't want that as we only want bad segments, so we need start a new segment and increase our $$$ans$$$ by $$$1$$$ and reset $$$s$$$

      if the number is not in $$$s$$$, we need to work with it because lets say or $$$s = $$$ { $$$4$$$ , $$$8$$$ }, and we find $$$a_i = $$$ $$$2$$$ , that means we need $$$4$$$ or $$$8$$$ but we got $$$2$$$, what if we got another $$$2$$$ after some time ?

      that would be $$$2$$$ $$$\cdot$$$ $$$2 = $$$ $$$4$$$ which is a number that we are looking for, so we need to iterate over $$$s$$$ and check if ($$$s_i \mod a_i == 0$$$ ) then we add $$$s_i \div a_i$$$ to $$$s$$$

      so $$$s$$$ will be $$$s =$$$ { $$$2$$$ , $$$4$$$ , $$$8$$$ } and then when we get to the second $$$2$$$ we will check if its in $$$s$$$ and so on ...

      the lower bound is to fast things up as we may not need to iterate over all $$$s$$$ but to start from a number thats $$$ a_i \le s_i$$$

      if its still not clear please copy my code and try to work with it and test it with samples

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

        Understood perfectly, Thanks for your nice explanation.

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

        How? i've been trying to understand how this approach doesn't exceed the time limits for hours. isn't its complexity O(n x number of divisors of x)? In that case doesn't it exceed 10^7 as no. of divisors of x can go uptil 100 and n can go up till 10^5?

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

          As I know, $$$10^7$$$ fits within even 1s

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

Is it possible for ~9k+ people to solve D in DIV 3 ?

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

F solution should contain 17 lines of code.

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

    I agree. F seems easier than E, although I couldn't reach either of them during the contest. Afterwards, it took me about 10min to figure out a solution for F, while E required a fair amount of mathematical reasoning.

    The hardest part of F was understanding the problem statement. xD

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

A simpler solution to F: 270026683 with a time complexity $$$O(n d(x) log(d(x)))$$$

The set avoid stores values that should not occur in the current segment. For example, let x = 12, a = [2, 3, 2, ...]. Initially the set contains 12. When encountering 2, we put 6 into set, because 6*2=12; encountering 3, we put 4 and 2 into set, because 4*3=12 and 2*3*2=12. After that when encountering another 2, we find that it is already in set, so we need to split here, and reset the set with {12, 6}.

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

    My solution complexity is just $$$O(n d(x))$$$

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

      Sorry for misreading the tutorial. Then it's a shorter but less efficient solution lol (but I think mine can also be optimized with the same trick or by using unordered_set

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

    oh yeahhhhhhhhh. i should've think simpler

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

E can be solved in constant time just iterating over the number of digits of n*a-b 270038095

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

    Your solution is mind-blowing to me. Great Job! Can you give some idea behind the proof, that, no other solutions would exist besides these for the cases?

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

      If you have the number of digits of n*a-b, then you can have the difference between a and b, then you can replace b in function of a, and calculate a from n*a-b.

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

This is my First Contest.. And I'm able to solve only A, and try B after the contest and i solved B.Is I'm the Only one who solve A with recursion?

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

    Many people are not able to solve a single question in your first contest. You did well for your first. Also, recursion is not needed in the first one. So you might be the only one:)

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

Pretests were too weak. My solution of F got an FST with TL but passed pretests with time of 200ms, and in B there wasn't a pretest with big enough a

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

what are the conditions to get MLE like if we make a vector of 10^10 or if we make a 2-3 vectors of 10^5 like which type of dps can we make what is make value of n for an 2DP and 3DP if anyone can tell or refer me to a post telling these

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

    umm, can you restate? hard to read.

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

      He's asking how much memory you can allocate before MLE. A vector of size 10e10 would definitely MLE, 2-3 vectors of 10^5 would be fine, 2DP would be around max 5000, and 3DP would be around max 500.

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

I solved D using 0-1 BFS. Each cell can go to no more than 10 cells next to it ( except if it contains a crocodile). So if the next cell is water the cost is 1 otherwise the cost is 0. Then after calculating the shortest path from cell 0 , the answer is YES if the cost is less than or equal k and NO otherwise.

Here is my submission:

https://codeforces.net/contest/1992/submission/269951020

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

oops i had G left with 30 minutes to spare but was too lazy to read it im math main so coudlve (maybe?) reached pupil :(

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

I WANT JUSTICE.

My contest submission : 269977715

Same code submission: 270045857

My submission getting runtime error but other submission accepted, this whole thing ruined my contest rating.

Please do something about this.

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

    Same Code submission: 270185546

    Accepted Again.

    Please rejudge my contest solution, and change my standings in leaderboard.

    PLEASE AUTHORS.

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

    I wouldn't tunnelvision on rating. You can see here https://leetcode.com/u/echen5503/ that I had a contest with negative delta(submitted solution 2 min after contest end), then the next contest where I did well was unrated. If you are skilled enough to do it once, you can probably do it again in a later contest. GL on expert.

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

In problem C, numbers between $$$m$$$ and $$$k$$$ affect neither $$$f$$$ nor $$$g$$$, so their permutation is irrelevant. In fact, you don't even need $$$k$$$ to solve the problem: just iterate from $$$n$$$ down to $$$m+1$$$, then from $$$1$$$ to $$$m$$$.

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

    In fact, test case 3 of problem C has bad input format (maybe extra spaces in somewhere), which causes my submission 269935508 got a wrong WA in fst. If reading tokens one by one, it (270282247) gots a AC.

    Even little probability, if Noobish_Monk, K1o0n can take a look and rejudge, I will give much appreciate for that.

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

      I looked in my generator, in fact there are no extra spaces, but there is a newline character in the end of file as it is in all the problems if it matters to you. Sadly I/we can't rejudge your submission. Sorry. Fun fact, I submitted your solution myself with no changes , it got OK. xD. I guess you're just unlucky...

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

        Thanks for your reply. It's the most sad story during my cf life. 2 problems got fst. C is mysterious wrong verdict, and F is tle due to Node.js.

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

Can anyone please help me correct this solution to problem D

Got WA on 845th test of test case 2.

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

    answer is "YES". Your code gives "NO".

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

      I think It's because you're changing k in the dp state but not storing in the dp array.

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

    it is not enough to set dp[i] = true/false .

    it should be the minimum distance he can swim to reach n+1 from i

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

Can Someone explain me why this submission of mine (For problem F) does not give a TLE , i mean while implementing i was considering some sort of a test case which could break this algo , maybe the set runs out of overflow , or traversing the set takes too long , or something like that Here is the Link to the submission. Link

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

good contest , thanks for fast editorial !

the problem D was bit different !

here is my solution to the problem ( greedy , c++ ) — 269977837

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

prblm D with iterative DP:`` Your text to link here...

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

My alternate approach for E:

Let $$$ans = n\cdot a-b$$$ for some pair of integers $$$(a, b)$$$. We know the number of digits in $$$ans$$$ is equal to $$$|ans| = |n|\cdot a-b$$$ and for all $$$n > 1$$$, $$$n > |n|$$$ (here again $$$|n|$$$ is the number of digits in n). Now, $$$ans$$$ can be reformulated as:
$$$ans = (n-|n|)\cdot a + |n|\cdot a-b$$$

Simplifying this we get;
$$$a = \frac{ans - |ans|}{n - |n|}$$$

$$$b$$$ can be computed in $$$O(1)$$$ once we calculate $$$a$$$. So traversing over all possible $$$ans$$$ gives the answer in practically $$$O(1)$$$ (not sure about the complexity).

My implementation

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

    The complexity is actually $$$O(log^2(n*a - b))$$$ for $$$a\neq 1$$$. I also did the same thing.

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

      I got the $$$O(\log n)$$$ part in my calculations, which I decided to report as practically $$$O(1)$$$ because of the bounds on $$$n$$$ in the task. How did you get the $$$O(\log a)$$$ part though?

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

        I just looped through all possible values of $$$n*a-b$$$ which take $$$O(log(n*a-b))$$$ time. Then, the process of computing the number of digits also take that time. (can be optimized a bit though)

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

My solution for problem F is very similar to the tutorial logic but still I'm getting TLE. Can anyone point out the reason. 270213270

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

Could someone please explain that how 270218105 gets accepted but 270217104 got TLE ?

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

    I figured out the problem in the TLE submission. I had assumed that the products of 2 divisors of x such that the product < x will still be a divisor of x. This is clearly wrong (consider x to be 24, the divisors to be 2 and 8, 16<24 but 16 is not a divisor of 24). Thus, my curr vector contains unnecessary numbers increasing its size outside of the permissible bound.

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

      You saved me! I had worked for many hours to find where mine went wrong.

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

anyone please explain r array here in G solution

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

    It's for reverse factorials. They are calculated this way:

    $$$r_n = inv(f_n)$$$

    $$$r_i = r_{i+1} \cdot (i+1)$$$

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

I'm not getting it how the greedy is working in problem D?? As if everytime we get the log and try to jump as further as possible then in O(N) how can we be sure that we will not get any crocodile in such jump?? And if we do get the crocodile or we get the water but we have spent all the k's then how we'll make the informed decision about that in just O(N) time ??

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

    The thing is, with a jump you can get past any crocodile, as long as you land in either a log or water. If there is such a log, then it is best to land at the farthest possible one; otherwise, if there is water at the end of the jump, then it is best to land there, so long as there is available $$$k$$$ at that moment.

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

      Thank you for your suggestion but it's still confusing to me. I found another approach using BFS which is also in order of O(N) which is less than DP.

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

        A better way to look at this is, let's say you have many logs that you can jump on:

        -L--L-LL......
        

        lets call last log as F If you choose any log but the last one, then any of these logs will eventually, after some jumps, have to surpass that last log (F). They can't surpass it by more than (m-1) steps. So picking the final log from the start would have granted you these (m-1) steps plus an extra one.

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

    if we have two logs that you can jump on one at index 1 and the other at index 8 it's always better to jump at index 8 lets say m is equal to 8 now when you jump at 1 you have 2 3 4 5 6 7 8 and 9 as options to jump on

    but if you jump at 8 you still have the 9 and you have now more options 10,11 ...

    there is no point in picking the earlier log because picking the farthest will give you more options and It will not make you miss anything

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

could anyone plz help me with my soln 270036296 of problem D . i don't know why i am getting wrong output.

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

In tutorial for F they said

Let's prove that it works. In any optimal division, if we take the first segment of non-maximum length, we will not violate the criteria if we transfer one element from the second segment to the first. Therefore, the given greedy algorithm is correct.

What does this even mean?

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

    It's short for "proof by induction". If we have some split in segments, where the length of the first one isn't maximal, we can move one element from the second and it would still be a correct split, while the number of segments could've only gotten less. Doing this process with every segment is the proof for greedy

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

The editorial for A doesn't prove that incrementing the smallest number is optimal when we repeat the process 5 times. It only proves that it's optimal for 1 time.

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

    Yes, I agree that at the end they should have written: "Let's run this algorithm 5 times and get the answer to the problem.". But they did everything else, because at the beginning they announced that a<=b<=c, which means that the variables must be sorted initially, which means if you just do this algorithm 5 times everything will work.

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

      If my understanding is correct, that's not what he is saying. I think his point is that just because you take the locally optimal choice every time doesn't necessarily mean that you will get the globally optimal result. For this problem, it is true. That's not the case for every problem.

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

        There are only 4 stages of this algorithm which are:

        1. a = b = c (a==b,b==c)
        2. a = b < c (a==b,b<c)
        3. a < b = c (a<b,b==c)
        4. a < b < c (a<b,b<c) 
        

        Where a is lowest number and c is largest of these 3. Let's look at all the options for starting:

        1. We start from a first position, then we alternate between 1 and 2 states and thats it.
        2. We start from the 3rd state, then we just add until we reach the 1st state.
        3. We start from 2nd state , then we add until we reach state 3, and then we already use the second instruction. 
        4. We start from 4th state, then we add until we reach state 2, and then we then use the third instruction. 
        

        This only works if the variables are in the range from 1<=a,b,c<INF.And accordingly, it works in THIS task. Prove me that im wrong instead of downvoting. I really dont care about it.

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

    I came up with some proof but it doesn't sound very easy for D3A. Please tell me if you know a simpler proof. On the positive side, the following proof works for any number of operations and more than three numbers.

    Consider two sequences $$$p$$$ and $$$q$$$ where $$$p$$$ is the result of the greedy algorithm from the editorial and $$$q$$$ is any other sequence obtained via the same process described in the statement. I claim that $$$p' \prec q'$$$ ($$$p'$$$ minorizes $$$q'$$$) where $$$p'$$$ and $$$q'$$$ are versions of $$$p$$$ and $$$q$$$ sorted in non-increasing order. This is rather intuitive because the greedy algorithm from the editorial achieves the minimum possible sum of the first $$$k$$$ elements in sorted order for any $$$k$$$, corresponding to minorization.

    Consider a function $$$f(x) = -\log x$$$ on domain $$$[1, +\infty)$$$. It is convex because its second derivative $$$d^2/dx^2 (-\log x) = 1/x^2 > 0$$$ on our domain. According to Karamata's Inequality we now conclude that $$$\sum_i (-\log p_i) \le \sum_i (-\log q_i)$$$, which is equivalent to $$$\sum_i \log p_i \ge \sum_i \log q_i$$$. Exponentiate both sides to obtain $$$\prod_i p_i \ge \prod_i q_i$$$.

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

      Yeah this is overcomplicated, but the idea to take logs is very good.

      If we generalize to wanting to maximize the product $$$a_1 a_2 \dots a_k$$$ at the end ($$$a_i \ge 0$$$), this is equivalent to maximizing $$$\log a_1 + \log a_2 + \dots + \log a_k$$$ (we can say $$$"\log 0" = -\infty$$$).

      Now if we consider the function $$$d(n) = \log(n + 1) - \log n$$$, this function is strictly decreasing over $$$n$$$. Since $$$d(a_i)$$$ is the benefit we get from incrementing $$$a_i$$$, it's clear that a straightforward greedy approach of always choosing the smallest first is the right way to go.

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

      Can it be proved by AM-GM inequality ? GM<=AM and equality occurs only if all of the numbers are equal , so we should always try to increase the lowest number.

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

    Proof by AC

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

    even without proving, it's still possible to solve in 6^3 * 1,000 time:

    for c1 in range(6):
      for c2 in range(6-c1):
        for c3 in range(6-c2-c1):
          ans = max(ans, (a+c1)*(b*c2)*(c+c3))
    
    • »
      »
      »
      4 months ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      I believe it's possible to solve this problem for any number $$$n$$$ of initial values and any number $$$m$$$ of operations, in $$$O(m + n \log n)$$$ using a greedy approach.

      First, sort the initial values and append some huge number. Let $$$i$$$ denote the index of the current number, modulo $$$k$$$, where $$$k$$$ is the index of the next greater number. While $$$a_i$$$ is less than $$$a_k$$$, increment $$$a_i$$$ and then $$$i$$$. When $$$a_i$$$ becomes equal to $$$a_k$$$, increment $$$k$$$ and keep iterating until all operations are used. Finally, compute the answer.

»
4 months ago, # |
  Vote: I like it -8 Vote: I do not like it

in question D he has to swim k units right? #include

include

include

using namespace std; typedef long long ll;

ll f(vector &ar, int n, int k, int m) { if (n == 0) return k == 0 ? 0 : -1; ll min_steps = LLONG_MAX; bool found = false; for (int i = 1; i <= m; i++) { if (n — i < 0) break; if ((ar[n — i] == 'W' && k > 0) || ar[n — i] != 'W') { int new_k = k; if (ar[n — i] == 'W') new_k--; ll steps = f(ar, n — i, new_k, m); if (steps != -1) { min_steps = min(min_steps, steps + 1); found = true; } } } return found ? min_steps : -1; }

int main() { ll t; cin >> t; while (t--) { ll n, m, k; cin >> n >> m >> k; vector ar(n + 1, '0'); for (ll i = 1; i <= n; i++) { cin >> ar[i]; } ll check = f(ar, n, k, m); if (check == -1) cout << "NO" << endl; else cout << "YES" << endl; } return 0; } this is giving worng on test 2 idk why...the k is 2 but available only 1 W so how can k be equal ?so it shud be no ryt?

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

can someone tell me what is problem in my code

https://codeforces.net/contest/1992/submission/270266835

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

Is a segment always a continuous array(subarray)?

for F,

input :

4 8

4 2 2 4

optimal division should be 4 4, 2 2

as per the editorial its 4, 2 2, 4.

help please.

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

in problem G's solution, shouldn't m be MEX and not MEOW

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

    I am also confused on the same, I believe m should be MEX

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

The problem D can be solved by just iterating through the string right?

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

Problem: 957E

Can someone explain why is this code taking so long to execute even when I've made some modifications in the range for b ??

#include <bits/stdc++.h>
using namespace std;

int main(){
    int t;
    cin >> t;
    
    while(t--){
        int n;
        cin >> n;
        
        vector<string> str(10001);
        str[1] = to_string(n);
        // concatanate the string n, upto a times
        for(int i=2; i<=10000; i++) str[i] = str[i-1] + str[1];


        vector<pair<int, int> > arr;
        for(int a =1; a<=10000; a++){
            // becuase the value, a*n-b is always upto 6 digits (10^6)
            // As a, b <= 10^4 and n <= 100, so a*n <= 10^6, so a*n-b <= 10^6
            // so, can we also short the loop for b, based on this information ???

            
            // define the minB and maxB based on the value of a*n
            int minB = max(1, a*n - 10000);
            int maxB = min(10000, a*n);


            for(int b =minB; b<= maxB; b++){
                string s = str[a];
                if(b < s.length()){
                    s = s.substr(0, s.length()-b);

                    if(s.length() <= 6){
                        long long k = stoll(s);
                        
                        // now the equation become an - b = k
                        if(a*n - b == k) arr.push_back(make_pair(a, b));
                    }
                }
            }
        }
        
        cout << arr.size() << endl;
        for(int i=0; i<arr.size(); i++) cout << arr[i].first << " " << arr[i].second << endl;
    }
    return 0;
}
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    probably because u r concatenating n a times and each time it may require allocating new memory

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

    don't implicitly generate the string, you are creating a massive array: ['a', 'aa', 'aaa', 'aaaa', 'aaaaa', ......] which has size of A^2. Remember that strings are internally char arrays.

    Instead, only generate the first 6 characters. Here's my solution for reference: https://codeforces.net/contest/1992/submission/270266899

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

Problem F was really good, given the combination of the use of the greedy idea and the $$$dp$$$ approach to find subsequence products. Learnt something new!

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

    can u explain the dp approach of problem f?

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

      I was referring to the same approach mentioned in the editorial. Let me elaborate it here for you.

      The greedy idea is to always extend our segment to the right as long as possible until it remains "bad" that is, no subsequence in the segment multiplies to $$$x$$$. This was proved in the editorial that it works, but to know when to stop extending the segment, we need to perform a dynamic programming that will tell us what all factors of $$$x$$$ have been produced by some subsequence in our current segment.

      Now, we maintain a set of numbers $$$\text{products}$$$ that can be obtained by multiplying the numbers of some subsequence in the segment that we are currently extending. Now, to know if we can include the current element $$$a[i]$$$ or not in the segment, we need to check if this can create a product of $$$x$$$. This can simply be done by checking if $$$a[i] \mid x$$$ i.e. $$$x$$$ is divisible by $$$a[i]$$$; and the product $$$\frac{x}{a[i]}$$$ exists in $$$\text{products}$$$. If both of the above conditions are true, then we need to end the current segment here and start a new segment from $$$i$$$ (thus making the set empty)

      Otherwise, we will update our set of products by iterating through it and for each product $$$p$$$ in it, we will insert the new product $$$p\cdot a[i]$$$ into the set. Note that this might involve duplication of products, so we must update the set using another temporary new set. Details can be found in this submission, which runs in approx. $$$1$$$ s.

      The complexity of the solution is $$$O(n\sqrt[3]{x})$$$ as $$$x$$$ has at most $$$\sqrt[3]{x}$$$ divisors.

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

Can anyone explain the proof of F? Why does this greedy algorithm work. I am stuck in understanding that why taking as much as possible will produce minimum number of bad segments?

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

    Consider the first two segments. If the first one isn't as long as it can be, we can move one element from second segment to the first and both segments are still {bad}. Second segment might become empty, no new segments appear, so by moving element to the first segment we can't mke our answer worse. After we added as many elements to the first segment as possible, we can erase it from the array and use the same logic for next segments. That's why greedy works

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

      Thanks, I was thinking that Segments may not be continuous that's why I couldn't understand.

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

How a Specialist come up with these ideas?

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

Can someone explain why in problem G with $$$2k<n$$$ when we pick m the answer is $$$\mathrm{C}_{m-1}^{m-k-1}.\mathrm{C}_{n-m}^{2k+1-m}.m$$$. I know two first multiplier is the ways we pick elements before and after m but why we need to multiple with m.

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

    Oh forget that we need calculate the sum of MEX so we need to multiply with m.

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

Text editorial is very intuitive..!!!

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

Sorry for late comment, but why doesn't my solution pass? I think I'm missing an edge case.

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

I did problem E using binary searching for finding value of b, and iterated on a from 1 to 1e4.

273309283

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

here is my code https://codeforces.net/contest/1992/submission/273669300 for problem D iam getting wrong answer Yes in case 5 1 1 LLWWW , but iam running this case in local editor its giving No , what iam doing here someone please help .

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

In the tutorial of G , for the case 2k<n , there is a typo, the answer needs to be added with
(m-1)C(m-1-k) * (n-m)C(2k+1-m) * m

Noobish_Monk

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

Hey guys, I had an out-of-the-box solution for problem E. I wanted to know your opinion on the same as the approach might be controversial:

Brute forcing all possible combinations without giving much thought would take O(n*max(a)*max(b)) amount of time. A general thumb rule is that the time for O(1e8) operations is in the order of a second. Therefore iterating over all n,a,b took me around 4-8 minutes, and did not take much effort to code it out. I stored the output into a file (removed the trivial cases of n == 1 and a-b == 1), and copied it into my final submission code, as each of the cases (except for 1) seemed to have not greater than 5 solutions each.

This wasn't during the contest but it seems like a nice way to tackle questions that don't have a humongous output for all test cases combined, and the input range is very limited, and brute force fetches the output quickly(for a human) without much thinking. Obviously this question's solution was not so difficult to think about or implement, but it seems like a good idea nevertheless in general.

Feel free to give your comments on the same, albeit controversial or not. Below is a link to my submission for the same:

https://codeforces.net/contest/1992/submission/284429181