Codeforces and Polygon may be unavailable between Aug. 17, 19:00 (UTC) to Aug. 17, 22:00 (UTC) due to planned power outages. ×

huangzirui's blog

By huangzirui, history, 2 months ago, In English

1688A - Cirno's Perfect Bitmasks Classroom

Idea: huangzirui. Solution: huangzirui. Preparation: huangzirui.

Good problem
Average problem
Bad problem
Did not solve

Hint
Solution
Code (C++)
Code (Python)
Apology

1688B - Patchouli's Magical Talisman

Idea: Yakumo_Ran. Solution: Yakumo_Ran. Preparation: SSerxhs.

Good problem
Average problem
Bad problem
Did not solve

Hint1
Hint2
Solution
Code (C++)
Spoiler

1688C - Manipulating History

Idea: Yakumo_Ran. Solution: Yakumo_Ran, SSerxhs. Preparation: SSerxhs.

Good problem
Average problem
Bad problem
Did not solve

Hint1
Hint2
Hint3
Hint4
Hint5
Solution
Code (C++)
Code (Python)

1687A - The Enchanted Forest

Idea: Yakumo_Ran, SSerxhs. Solution: Yakumo_Ran. Preparation: SSerxhs.

Good problem
Average problem
Bad problem
Did not solve

Hint1
Hint2
Hint3
Solution
Code (C++)
Code (Python)

1687B - Railway System

Idea: Yakumo_Ran. Solution: Yakumo_Ran, huangzirui. Preparation: SSerxhs.

Good problem
Average problem
Bad problem
Did not solve

Hint1
Hint2
Hint3
Solution
Code (C++)
Code (Python)

1687C - Sanae and Giant Robot

Idea: Yakumo_Ran. Solution: Yakumo_Ran. Preparation: huangzirui, SSerxhs.

Good problem
Average problem
Bad problem
Did not solve

Hint1
Hint2
Solution
Code (C++)
Spoiler

1687D - Cute number

Idea: Yakumo_Ran. Solution: huangzirui. Preparation: SSerxhs, huangzirui.

Good problem
Average problem
Bad problem
Did not solve

Hint1
Hint2
Solution
Code (C++)

1687E - Become Big For Me

Idea: xiaoziyao. Solution: xiaoziyao, SSerxhs. Preparation: SSerxhs, xiaoziyao.

Good problem
Average problem
Bad problem
Did not solve

Hint
Solution
Code (C++)
Spoiler

1687F - Koishi's Unconscious Permutation

Idea: huangzirui. Solution: Elegia. Preparation: huangzirui, SSerxhs.

Good problem
Average problem
Bad problem
Did not solve

Hint
Solution
Code (C++)
 
 
 
 
  • Vote: I like it
  • +276
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it -25 Vote: I do not like it

div2 C, terrible!

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

    I don't even feel like upsolving it lol

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

    Yes, their solution of C problem in Python is not accept by PyPy3 and PyPy2, but it said that generally it is faster. I have lose many attempts searching in my solution, but it is was correct. But then it was just accepted when I send it by Python2 or Python3 Admins, Please, reconsider solutions, because I solved this problem faster, then it was finally accepted

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

    In Div.2:

    1. Why was the round unbalanced(D had more AC, then C) ?
    2. What was the point of making C so hard ?
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      Because testers with different rating solve C easily, spending less time than D.

      We don't mean to make C hard, it's a fault. On the contrary, we add C to fill the gap between B and D (at first, D was C).

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

        The idea to solve C was so random and guessing, I thought there is a way to construct it by some advance algorithm =((

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

Thanks for the fast editorial, though there had been nightmares in 2C.

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

Weak pretests in Div2A, seriously ?

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

Can anyone please explain Div 2 B less mathematically? I am having hard time understanding the solution.

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

    If you have at least one odd number, you can sum this number with all the evens because even + odd = odd, so in this case ans = amount of even numbers. Otherwise, the optimal strategy is to divide a number until it becomes odd, and then do the strategy for the first case, you can do it iterating over all the numbers and looking for the number that requires less movements to became odd by dividing it by 2.

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

      How does this work in this case: n = 2 a = (1024, 2048) Both are even numbers, the correct solution here should be 1: operation 1 yielding 3072 2: operation 2, 5 times solution: 6 if we follow the strategy of searching for the number that requires the least division by 2 to make it odd, then we try to divide 1024 10 times to make it odd, so the solution becomes 11

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

        If you divide 3072 by 2 five times then you end up with 96 which is not odd.

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

    The optimal solution is to use fusion between an odd and even number as often as possible (this will always get rid of 1 even number per operation whereas reduction can leave you with even number. It's impossible to get rid of more than one even number per operation).

    The problem is if you don't have any odd numbers to start with, in which case you need to calculate which number can be made odd quickest using reduction and then use that odd number with fusion to get rid of all the remaining evens.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    1. If there is at-least one odd number in the array, then you can use this number with operation 1 to make all the even number numbers odd (odd + even = odd). The total number of operations would be the number of even numbers.

    2. If no odd numbers present, then find the even number that takes minimum number of operations (operation 2 divide by 2) to make it odd, then do step 1.

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

      Damn.. How did I missed that!!! Thank you for the nice explanation.

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

Please Explain D in more detail if anyone can ??. I am not getting for k>=n part ??

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

    the optimal strategy is to wait until we have greater than n seconds left and let the mushrooms grow as much as they can. finally when we have n seconds left, we traverse over the array and collect all the mushrooms.

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

      Omg !! Yeah i didn't saw |x-y| <= 1. So just wait for n-k seconds . Then loop through array for n times giving as k*n . and rest part is n*(n-1)/2. so answer will be = sumofarray + (k-n)*n + (n*(n-1)/2). Wrote the same formula and got accepted . Thanks a lot buddy !!

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

    Let me explain how I proved it,

    The main observation is, if a point is visited at times (t1, t2, t3...tp) Then, the "extra" mushroom gained from this point is tp-1. Why? Because, first I gain t1-1 mushrooms, then t2-t1 mushrooms, then t3-t2 mushrooms and so on. So extra mushrooms gained by point simply equals to last time I visited it minus 1.

    Lets say, that I visit exactly r points and I have k seconds (I may visit some points multiple times), how to maximize the number of "extra" mushrooms gained given, for a fixed r? Observe that if I have k seconds, than extra mushrooms gained will be sum of r different numbers from [0 , k-1] (Every number denotes extra mushrooms gained from some point. No number will be repeated in sum, because every point's last visited times MUST be different.).

    An upper bound is sum of last r numbers, i.e [(k-r) + (k-r+1)...+ (k-1)]. This is also possible too! Start from 0th second, keep waiting and collecting mushroom from the first point till, (k-r+1)th second, So that I can get k-r extra mushrooms from it, then jump to remaining r-1 points, giving me (k-r+1) + (k-r+2)...+ (k-1) extra mushrooms!

    Now, for a fixed r we know the strategy. Observe that increasing r is always profitable. (Its really easy to prove, just compare the total mushroom gained using optimal strategy for r and r+1). So we should try to keep r as large as possible.

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

    Video Solution for Div2D

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

    You can use binary search as well, i binary searched on the number of mushrooms that can be collected in k minutes, and I just found the maximum such number You have to handle two cases separately, i.e. when number of k <= n and k > n in the former case just find the maximum sum subarray and then add the extra ballons that may have appeared in k seconds. In the latter case you have to make more than one traversals of array (in concept) to collect the mushrooms , its a little maths you can use pen and paper to understand it .

    Here is my solution:

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

      Your binary-search is not needed, in fact instead of returning boolean value in your function f, u can directly return the value you calculated, that is the final answer. here is your code I modified

      int f(vectorvec, int k){ int n = vec.size(); if(k<n){
      int res = 0; for (int i=0; i<k; i++) res += vec[i];

      int curr_sum = res;
        for (int i=k; i<n; i++)
        {
         curr_sum += vec[i] - vec[i-k];
         res = max(res, curr_sum);
        }
        res += (k*(k-1))/2;
      
         return res;
       }
      
      int sum=0;
      for(auto it: vec)sum += it;
      sum += (n*(n-1))/2;
      k -= n;
      int cnt = k/n;
      int residue = n*n;
      sum += residue*cnt;
      cnt = k%n;
      sum += cnt*n;

      // cout << sum << "\n"; return sum; } void solve(){ int n,k; cin >> n >> k; vectorv(n); for(auto&x: v)cin >> x;

      int ans=f(v,k);
      cout << ans <<nl;

      }

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

Beware of Luogu's problem group invading Codeforces.

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

    It should be "Beware of TouhouProject's problem group invading Codeforces."

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

    Can anybody explain why we should do that? I'm just curious about it.

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

      Because this competition is prepared by one of luogu's (a Chinese cp website) team of problem setters (called WdOI). Of course this comment is just joking, please don't take it seriously.(however for myself Chinese rounds are too terrible I always get negative rating changes :(

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

C, if some letter is in the intial string, it will appear in the input data exactly once. Why?

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

    I made some insights elsewhere: " I guess the answer at the game.

    Let's consider both operations and results as strings.

    Consider the character 'x' at the beginning, if there is only one operation, that is, change the 'x' into 'yyy', then the input data is the 'x' 'yyy' of the operation and the 'yyy' of the result. If we go to the operation again, for example, the next operation is 'yy'-'zzz', then each operation is to delete 'yy' from the result string and join in the operations, and then replaces 'zzz', in the result string and adds' zzz' to the operation string. It is found that the 'zzz'' has increased twice, while the location of the 'yy' has only changed, but the number has not changed. That is to say, the parity of their occurrence remains the same. Therefore, only the initial letters appear odd times, and the others appear even times. " So I think the editorial of the problem only says 'appears exactly once' ,means 'x' that I said above appears only once. If there is an operation 'yy'-'zzz',' that contains'x'or equals to'x', we don't regard it as 'x' appear again. The description may not be accurate, but I think my solution should be correct.

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

those quotes at the starting of question was quite helpful for solving problems ...LOL!

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

    how?

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

      well for that first you have to solve the problem without reading it & then see if it make sense to read the quote first & then solve the problem ;)

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

I think I cheesed problem D.

A "brute force" solution is to iterate over the array, and increase the offset to whatever it has to be to make the current element cute, and repeat until the offset didn't change.

This was as I expected too slow, but then I tried shuffling the input list. That was still to slow. Then I tried on-line shuffling the prefix of the array that is looked at until finding something not cute, and breaking when its found. My intuition for doing this is that this way problematic elements probably end up in the start of the array, so they're found faster.

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

    Online shuffle is a nice trick here!

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

Can anybody please tell me what's wrong with my div2D submission? Cf-stress was not able to find anything wrong...

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

    when k>n, the ans = sum(n)+k*n-(n+1)*n/2. in your code,this part is wrong.

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

      This part is correct actually...

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

        sry,i made a mistake...my math is terrible

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

    and when k<n, your ues of array pref may be wrong. the sum from [i,i+k-1] = pref[i+k-1] — pref[i-1] . Attention please, -1 is important here.

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

      Nvm, my stupid ass thought that the positions are cyclically arranged.

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

    FWIW, here's a tip on how to navigate CF Stress when you don't find a counter example in your first try. The solution is only tested for 60 seconds, so it means that the a counter example on that constraints might've been found if the duration was more.

    A workaround for this is to set $$$t\_low = t\_high = \infty$$$ on the same constraints. If you get "Data too large verdict", it means that you'd be able to get the counter example if you reduced the $$$t$$$ parameter. So then, just use $$$t\_low = t\_high = 10$$$ or $$$100$$$

    For example, your code fails on Ticket 10310

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

I have stopped reading novels & stories since Codeforces has many stories to tell in every question !

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

div 2 c a nightmare

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

    Yes, their solution in Python is not accepted by PyPy3 and PyPy2, but it said that generally it is faster. I have lose many attempts searching in my solution, but it is was correct. But then it was just accepted when I send it by Python2 or Python3

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

When I saw Elegia in the writer's list, I immediately knew that Div.1 F won't be solvable.

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

Harder div1D: You are given $$$100\,000$$$ values of $$$k$$$; for each one say whether $$$a_i+k$$$ is beautiful for all $$$1\le i\le n$$$.

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

    I also reduce problem D to this problem, but then I cannot solve this. How could you solve the problem by this approach?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it
      Solution of the harder div1D
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    How is it harder? Just like in the regular solution, enumerate floor of sqrt of $$$a_1 + k$$$ and do the jumps, you will find the interval of possible $$$k$$$. For $$$k > a_n^2$$$ all the numbers should be in one segment, so you can check one such $$$k$$$ in $$$O(1)$$$. I believe that my submit 159385709 from the contest will solve this harder version if remove return 0, change IO and add this special case for big $$$k$$$.

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

      For your solution (and possibly for the official solution ?) they might be the same problem, but the majority of accepted solutions are not good enough to solve the harder version.

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

I had an alternate solution for problem D that is hard to analyze but runs quite fast on the given tests (maybe hackable?). The basic idea is to combine the naive approach of repeatedly finding a lower bound for $$$k$$$ with grouping elements of the array. The grouping will compress numbers together if we can be certain that $$$f(x+k)=f(y+k)$$$ in the final answer. This is helpful because e.g. if we can group together elements that are $$$10^6$$$ apart, we can skip to a value of $$$k$$$ that will make $$$f(x+k)\geq 10^6$$$.

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

Div1D: Please hack me, this is a simple randomization (with some optimize)
159418821 upd: hacked, thanks

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

this is how i did Div2D — Case 1 : k<=n we take max sum contiguous subarray of length of size k and then add k*(k+1)/2 to it . Case 2 : k>n at first i thought of taking from left to right then right to left then left to right so on till k becomes 0 but it was not able to maximize the answer , so i took 0th element n-k+1 times (till then other n-1 mushrooms grow and this leads to optimal answer) , then take all elements from index 1 to n single time and add initial height and the extra height it grew when u were picking the mushrooms before it here is my submission — https://codeforces.com/contest/1688/submission/159403438

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

"Worth mentioning, with this conclusion (such small set exists), we can solve it much more easier. Just choose a small set by greedy, and enumerate its subset of size 14."

:o

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

Your solution of C problem in Python is not accept by PyPy3 and PyPy2, but it said that generally it is faster. I have lose many attempts searching in my solution, but it is was correct. But then it was just accepted when I send it by Python2 or Python3 Please, reconsider solutions, because I solved this problem faster, then it was finally accepted

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

A, B and D are nice. C not much. Nice contest though

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

Hey, Please tell why my submission on A failed? My submission

It says "wrong output format Expected integer, but "2.68435e+008" found" on test 2

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

    Try (long long) before pow

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

    "Raw" pow function returns a float or a double value. You have to convert it or write a power function for integers only.

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

      @TWNWAKing, @quochung-cyou Thank you so much, though it got accepted, I am not able to understand why the conversion was needed, as he inputs are in int range.. or could you please tell any specific test case where it was failing?

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

        It's just that pow function returns double type, and c++ outputs doubles like this for example 1.531e3, which is not acceptable, so you have to convert it into int or long long so that it outputs in integer form

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

Div 2 problem C — the statement was very confusing and hard to understand!

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

why it's not possible to hack Div2C?

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

    Probably because it's difficult to check whether the input is valid or not.

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

Can A high rated person give their view on problems like Div 2C and how to get better at them, these always seem to appear in Div 1 + Div 2 rounds where we need to make a claim based on observations and hope that its correct. I think all of us could benefit from it.

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

God I absolutely hate div2C kind of problem where you're just trying to find this tiny obscure property that doesn't even look too relevant but turns out to be literally the whole answer

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

    I think that is OK, but the real problem that solution of C problem is not accept by PyPy3 and PyPy2, but accepted when I send it by Python2 or Python3

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

Question C is not correctly explained that things ruined the whole contest

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

Solution: Elegia.

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

Div 2 C. It got TLE in python 3. But when same code is submitted in pypy3 ,it is accepted. Why does this happen?please look into it and re evaluate it.

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

    Codeforces always says that if you submit it in pypy, it almost always works faster

»
2 months ago, # |
  Vote: I like it -13 Vote: I do not like it

I hate yakumo ran

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

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.

Divison 2

Divison 1

If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).

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

I have a question and I will be thankful if someone helped out It is about Div 2 C The question says the answer is unique but I found this sequence for the second test case and it seems right but I do not see where I went wrong so can anyone point it out to me?

initial is "a" pick substring "a" and replace it with "z" so now it is "z". pick substring "z" and replace it with "aa" so now it is "aa". pick the first substring "a" and replace it with "yakumo" so now it is "yakumoa" pick the last substring "a" and replace it with "ran" so now it is "yakumoran"

and then t before shuffled become: t = ["a" , "z" , "aa" , "yakumo" , "a" , "ran"]

so can anyone point out where I went wrong and explain the question more for me? Thanks in advance

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

    This is not possible. Imagine that the initial string was "a" as you told. and t = ["a" , "z" , "aa" , "yakumo" , "a" , "ran"].

    • operation 1: s = "a". choose a substring of s that equals to t[1] which is "a" and change it to t[2] which is "z".

    • operation 2: s = "z". choose a substring of s that equals to t[3] which is "aa" and change it to t[4]. but we don't have any substring "aa" in "z".

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

Div2 C, Hint2, Why the initial string consists of only one letter?

Well, it's obvious, as the authors wrote in the statement: The history of Gensokyo is a string s of length 1 initially.

Anyway, Div2 C and D should've been swapped.

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

    I remember our math prof sometimes saying: "Hint: Look at the definitions"

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

I have thought about problem D for 1 hour and I have also implemented a solution different from the official one. Nonetheless, I cannot understand anything from the editorial. Can someone give a vague idea of what is the official solution?

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

    This may be slightly different, I also cannot fully parse the editorial but I think it's similar.

    Good numbers look like this, starting from 1:

    1 good, 0 bad, 2 good, 1 bad, ..., x good, x - 1 bad, ...

    Let's fix that after shifting, a[1] will be in the good range of size x. It gives us a range [lo, hi] (the numbers which puts a[1] at the beginning and end of the good range of size x respectively) of candidates.

    Consider all elements a[1] ... a[n] are shifted to a[1] + lo, ..., a[n] + lo at first. You can see that only the next ~a[n] / (x - 1) ranges can have any numbers in them (since the range sizes are all at least x - 1.

    For each good relevant range, you need the largest element in this range (this upper bounds hi).

    For each bad relevant range, you need the smallest element in this range (this lower bounds lo).

    If lo <= hi after looking at all ranges you have a valid answer. Smallest / largest in any range can be found be precomputing + shifting.

    Since there are a[n] / (x - 1) relevant ranges for each x, the total cost becomes ~a[n] log(a[n]). (Once you hit the good range of size a[n] you're guaranteed to find an answer).

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

Yet another randomized approach for Div1D, which I tweaked to being accepted after the contest. It is similar to some approaches already mentioned, but still feels different enough for me to write it up.


First, the base solution.

The cuteness means that every number has to be from $$$u^2$$$ to $$$u^2 + u$$$ for some integer $$$u$$$. And some $$$u$$$ on the order of a few million would make each number cute, so, there are not too much $$$u$$$ to check.

Thus we iterate over $$$u$$$ for the first given number, $$$a_1$$$. Inside, we have the answer between two borders, $$$x$$$ and $$$y$$$, where $$$x = u^2 - a_1$$$ and $$$y = u^2 + u - a_1$$$.

Check all other numbers $$$a_i$$$:

  1. if $$$a_i + x$$$ is between some $$$v^2$$$ and $$$v^2 + v$$$, the upper bound $$$y$$$ should be lowered so that $$$a_i + y = v^2 + v$$$;

  2. if $$$a_i + x$$$ is larger than $$$v^2 + v$$$, the lower bound $$$x$$$ should be upped so that $$$a_i + x = (v + 1)^2$$$;

  3. as soon as $$$x > y$$$, the whole check fails.

Note that, on step 2, we can not possibly go to $$$(v + 2)^2$$$ or more, because the initial bounds are for the lowest of our numbers $$$a_1$$$.

If all the checks pass, we have the lower bound $$$x$$$ as our answer.


Now, the base solution is slow.

But if we shuffle $$$a_2, \ldots, a_n$$$ randomly, the intuition is that, when there are $$$p$$$ problematic values and they are distributed randomly, we break after $$$n / p$$$ steps. And if we had, for example, $$$n, n - 1, \ldots, 3, 2, 1$$$ problems in our checks, the sum would be just $$$n \log n$$$.

This is still slow, for example, when we have many small numbers and one or two large — which are not lucky enough to appear at the front of our shuffled array, but still break most of the checks rather late.

A neat solution to this seems to be the following: as soon as $$$a_i$$$ broke the check, shuffle it into a random position of $$$a_2, \ldots, a_i$$$. This way, the values which are usually problematic tend to go to the front of the array. Much like in a splay tree, useful checks gather at the front. This is still far from a formal proof.

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

Why didn't I get a rating change after the contest? It shows no ranking in the contests page in my profile. (don't know why but it is listed in unrated contests)

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

    Something is wrong with the system. I have become pupil and it still shows my name in gray, and in the contests place in profile it says I becamr Newbie

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

Div. 2 Problem C is really difficult for me to understand. The editorial does not make much sense to me. If someone could explain in better terms it would be much appreciated. I am trying to upsolve it.

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

    I guess the answer at the contest.

    Let's consider both operations and results as strings.

    Consider the character 'x' at the beginning, if there is only one operation, that is, change the 'x' into 'yyy', then the input data is the 'x' 'yyy' of the operation and the 'yyy' of the result. If we go to the operation again, for example, the next operation is 'yy'-'zzz', then each operation is to delete 'yy' from the result string and join in the operations, and then replaces 'zzz', in the result string and adds' zzz' to the operation string. It is found that the 'zzz'' has increased twice, while the location of the 'yy' has only changed, but the number has not changed. That is to say, the parity of their occurrence remains the same. Therefore, only the initial letters appear odd times, and the others appear even times.

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

      I think I understand it better, thank you so much. A very strange problem indeed.

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

So, how Elegia's mind works?

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

in problem B(https://codeforces.com/contest/1688/problem/B) if there are only even numbers in the array why we are not using Fusion(Fusion: Patchouli chooses two tokens, removes them, and creates a new token with magical power equal to the sum of the two chosen tokens.)operation?

ex:array[]={26,30,24,50}

26+30=56,now array[]={56,24,50}

56+24=80,now array[]={80,50}

80+50=130,now array={130}

applying reduction operation array={65} here also minimum operations=4

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

    Just like the last case in the sample, it's a special case, but that doesn't mean the best choice is to use Fusion operation. You can find that, if $$$A = 2^i \times a, B = 2^j \times b$$$ and $$$a, b$$$ is odd, if we add first and then try to devide the sum by $$$2$$$, we need at least $$$\min(i, j) + 1$$$ operations. But if we make one of them become odd first, then we need exactly $$$\min(i, j) + 1$$$ operations. When $$$n$$$ becomes larger, the total number of operations required by the second method above seems stable while the first don't.

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

      can you please take a example and explain?

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

        For example, $$$A = 4, B = 12$$$, if we use Fusion first then we need to perform $$$5$$$ operations, while if we first turn $$$A$$$ into $$$1$$$, we only need $$$3$$$ operations in total.

        The question is to consider $$$\texttt{lowbit}(A)$$$ and $$$\texttt{lowbit}(B)$$$, if they are the same, so $$$A + B$$$ will have more zeros in the binary representation's end than both $$$A$$$ and $$$B$$$, so we need to perform more operations to devide them by $$$2$$$ until the sum becomes odd.

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

      Thankyou,i understood now.

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

Very weak sample in 1C, as a consequence I had been debugging a fake algorithm for an hour.

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

Does anyone know any error while using map<char,int>. I wrote a code and it gave me wrong answer and then I edited it to map<int,int>, It worked and when I switched back to map<char,int> I was getting correct again. It has happened with me earlier too.

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

please explain 2A in a bit detailed and a simplified way.

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

    If $$$x = 2^k$$$, then the binary representation of $$$x$$$ only contains one $$$1$$$. To make sure $$$x \texttt{ and } y \neq 0$$$, then at that bit $$$y$$$ contains $$$1$$$ must hold. The same, to make sure $$$x \texttt{ xor } y \neq 0$$$, in order to make $$$y$$$ smallest, you will se we can just replace one $$$0$$$ with $$$1$$$ on any other bit of $$$y$$$. So this bit must on the leftest un-zero bit. So, if $$$y = 1$$$ then $$$y \leftarrow y + 2$$$, or else $$$y \leftarrow y + 1$$$.

    If $$$x \neq 2^k$$$, then just make $$$y = \texttt{lowbit}(x)$$$.

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

It's difficult for me.

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

I solved E with a simple greedy. Can anyone hack me or prove it?

Our goal is to choose a subset that does not change the answer.

Let $$$g$$$ be the final answer. For each prime factor $$$p$$$ of $$$g$$$, it suffices to choose two elements $$$x,y$$$ that $$$f_p(x),f_p(y)$$$ are the smallest and second smallest. (definition of $$$f_p$$$ is same as editorial)

Now we have a set $$$S$$$, but the gcd of pairwise products in $$$S$$$ still might not be $$$g$$$. Let the reduntant prime factors of $$$g$$$ be $$$[p_i]$$$. For each $$$p\in [p_i]$$$, we need to choose two more elements $$$x,y$$$ that $$$f_p(x),f_p(y)$$$ are $$$0$$$.

This directly passes. However I can't prove that it will never take more than $$$14$$$ elements. https://codeforces.com/contest/1687/submission/159458664

upd: hacked

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

    I can not prove it either, but it seems correct.

    Actually there are many strange but correct ways to select the subset. The method in editorial is not the easiest one, but it is easier to prove its correctness.

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

Even though many people may not agree with me I think div2 C is one of the best problems I have ever seen. Congrats to the author of it Yakumo_Ran!

»
2 months ago, # |
Rev. 2   Vote: I like it +43 Vote: I do not like it
//这回只花了45min就打完了。

(in the code of Div.2 B)

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

    To salute Feng Jing Olympic of Imagination.

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

can someone explain me Div2E problem statement

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

    They actually used the full spanning forest definition in the problem statement because the graph is not guaranteed to be connected.

    So we just find the spanning tree (min / max) in the individual connected components. Looking at the samples clears it even more.

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

Howcome Div2E is only 1700 rated though it has only 700s ACs. I am new to MST ,apart from kruskal what else algorithms are used to make a MST from a graph?

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

problem c tutorial is really dedicated to people who already solved it only !!! it's hints is just define the problem and it doesn't make any sense.

So the answer is the only letter appearing odd times in the input data.
why the above statement is correct ? what is its proof ? what is the explanation of the two situations of letter c ?

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

Thanks for the editorial and the round, div2 C is very interesting

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

    thanks for the bad editorial and the round , div2 C is the worst problem ever I seen.

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

Problem C: I get a runtime error on test case 6. Is there anything special about that case? Thanks.

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

Idk about y'all. But from a practice perspective, doing div2 C was the perfect problem to come by and solve quickly after not making progress on a different problem for an hour.

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

Anyone can explain How to tackle observation-based problem as bits related or Number theory related. In which there are some patterns in the output. I usually tack lots of examples but am not able to come up with a solution..

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

Problem E

Please tell why my solution is failing: My Submission

My approach is very similar to that given in the editorial but I have used priority queue instead of sorting the edges by weights. Although it is giving correct output for the sample test case, but giving Wrong Answer verdict on submission.

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

Perhaps a slightly different solution to Div1D.

We know an $$$y$$$ is bad iff there exists an $$$x$$$ and $$$i$$$ where $$$y \in (x^2 + x - a_i, (x + 1)^2 - a_i) = \mathcal{I}(x, i)$$$.

Fix $$$x$$$. If $$$a_i - a_{i - 1} \leq x$$$, $$$\mathcal{I}(x, i) \cup \mathcal{I}(x, i - 1)$$$ is an intervals. Thus, the number of bad intervals (for a fixed $$$x$$$) equals to the number of $$$i$$$ where $$$a_{i} - a_{i - 1} > x$$$ plus 1.

Said another way, for a fixed $$$i$$$, it contributes to a $$$x$$$ if $$$x \leq a_{i} - a_{i - 1}$$$. Therefore, the total number of bad intervals is $$$\sum_{i} (a_i - a_{i - 1}) = a_n$$$.

After finding all bad intervals, the rest can be solved in any way you like.

I note that the solution is different from the official editorial as the harmonic series appears nowhere.

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

    Brilliant solution! And we can use radix sorting to optimize the time complexity to $$$O(n+a_n)$$$ since $$$l\le a_n^2$$$ holds for each interval $$$[l,r]$$$.

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

      However, assuming only the comparison model, I can only achieve $$$O(a_n \log a_n)$$$ as I have no way to avoid sorting.

      If we take a stronger model like the RAM model, sorting $$$n$$$ integers of $$$w$$$-words still takes $$$O(n \frac{w}{\log n})$$$ time. Though there is faster integer sorting algorithm exists, it's not linear after all.

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

Can someone explain for problem B what's the solution for this test case: 2 1 1024 2048

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

    Answer = 3 you can add 2+1 = 3 and the sequence will be 3 1024 2048 then add 3+1024 = 1027 and the sequence will be 1027 2048 and then add 1027+2048 = 3075 an odd number

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

Can anyone kindly elaborate the solution for 1687C Sanae and Giant robot?

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

Can somebody explain me why my submission 159609287 to div2 F fails? I tried stress testing it on cfstress.com with a range of constraints but couldn't find any counterexample. My solution idea is based on the editorial's idea of making all elements of s 0 by repeatedly choosing segments with both ends 0 and making that whole segment 0. To implement this, I kept a segment tree for maintaining number of 0's in any segment of the array s. Now, I sorted all the given m segments according to their l value (stored in a vector of pairs,v) and kept 4 sets offl(segments currently traversed whose both ends are non zero,sorted wrt l value),offr(same as offl but sorted wrt r value),onl(segments whose r end has a 0 but not the l end,sorted acc to l value) and onr(whose l value is 0 but not r,sorted wrt r value). Then I iterated through v. If the current segment is non zero at both ends,then I insert it into offl and offr, else if exactly one end is 0 I insert it into onl or onr accordingly depending on the 0 end. Else if both ends are 0, then I update that segment to all zeros and also repeatedly update offl,offr,onl,onr according to the new updation of the array and also update segments which were initially in onl or onr but after the latest updation of array s,became 0 at both ends. This step repeats until I am not able to update any of the 4 sets or any more segments. You can have a look at my code for better understanding of the approach.

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

    Sure, take a look at Ticket 10982 on CF Stress.

    Remember that, in the free plan, you only get 60 seconds of stress testing time on the server. To best utilize it, you should choose the constraints a bit smartly, for example, instead of keeping $$$t\_low$$$ and $$$t\_high$$$ as 1, you can increase both of them to infinity (while keeping the product less than the limit). This would generate, say, $$$2000$$$ test cases per input, which has a higher chance of finding a counter example. If you get "Data too large" verdict, you can gradually decrease the constraints on $$$t$$$ using binary search, but now you at least know that a counter example does exist for smaller $$$n$$$.

    But if you don't want to decrease the constraints on $$$t$$$, just copy the large testcase, and in your code, print the failing testcase on the error stream. You can get this TC number from the difference highlighter at the bottom.

    For example, I got this TC

    Input
    Expected Output
    Your Output
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot!! Will keep this in mind,the next time.

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

The problem 1688B — Patchouli's Magical Talisman. Same idea with the answer. I wrote quite a few lines and had to use the queue

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

I like this round! Thanks to the Chinese problem-makers!

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

I understand the solution now. Deleted my comments.

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

Maybe there is somebody like me unable to understand the official editorial as a g.f. dummy, I would like to share my personal note here.

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

1687A — The Enchanted Forest. I don't understand, why for k > n additional mushrooms is (2 * k — 1 — n) * n / 2. Please, help me, if you know. Thanks. And, please, don't downvote, because I really don't understand...

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

    I have done in this way:

    if(k>n)

    We know ans= sum(a[i] for all 0 <= i <n ) + some thing (lets say y)

    To calculate this y , we will remain at a[0] for ( k-n ) time so total increment in all a[i] is (k-n). Now we are left with n steps , in each step we will move from i=0 to i=n-1 (assuming 0 based indexing) . So y becomes,

    y = sum of all (k — n + j) , where 0<=j<=n-1.

    eg . for n = 5 , k = 700 y = ( 700-5 ) + ( 700-4 ) + ( 700-3 ) + ( 700-2 ) + ( 700-1 )

    therefore , y= k * n — n * ( n + 1 ) / 2

    simplify this we will get

    y= (2 * k — 1 — n) * n / 2

    my solution

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

C is genius!

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

Auto comment: topic has been updated by huangzirui (previous revision, new revision, compare).