AlFlen's blog

By AlFlen, 6 weeks ago, translation, In English

1582A - Luntik and Concerts

Idea: 74TrAkToR

Tutorial
Solution (74TrAkToR)

1582B - Luntik and Subsequences

Idea: AlFlen

Tutorial
Solution (74TrAkToR)

1582C - Grandma Capa Knits a Scarf

Idea: AlFlen

Tutorial
Solution (74TrAkToR)

1582D - Vupsen, Pupsen and 0

Idea: AlFlen

Tutorial
Solution (AlFlen)

1582E - Pchelyonok and Segments

Idea: 74TrAkToR

Tutorial
Solution (74TrAkToR)

1582F2 - Korney Korneevich and XOR (hard version)

Idea: 74TrAkToR

Tutorial
Solution (74TrAkToR)

1582G - Kuzya and Homework

Idea: 74TrAkToR

Tutorial
Solution (74TrAkToR)
 
 
 
 
  • Vote: I like it
  • +189
  • Vote: I do not like it

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

Lighting Fast Editorial and Thanks for the wonderful problems.

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

Thanks for the contest and the lightning fast editorial, but on my computer the tutorial doesn't work, it says


[problem:] Tutorial is not available

it would be great if you could fix

»
6 weeks ago, # |
Rev. 3   Vote: I like it +79 Vote: I do not like it

The editorial is currently not working though it's already written, we're trying to find out why.

UPD: I've added ABC by hand

UPD2: It's working now

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

Can someone tell why my logic is failing in B?? I am getting WA in B. ~~~~~ //My short logic cnt = count of 1; cnt0=count of 0 ; final answer will be - cout<<(cnt*pow(2,cnto))<<"\n"; ~~~~~

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

    pow return answer in floating point format. (so, maybe precision error) I also used it and got a WA. Use a loop or self-defined function to calculate power.

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

      ok ,thanks

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

      I also used the power function which works in O(logy) but this also failed . Can you tell why ?? ~~~~~

      ll power(long long x, long long y) { int res = 1; // Initialize result

      // Update x if it is more than or // equal to p

      if (x == 0) return 0; // In case x is divisible by p;
      
      while (y > 0)
      {
          // If y is odd, multiply x with result
          if (y & 1)
              res = (res*x) ;
      
          // y must be even now
          y = y>>1; // y = y/2
          x = (x*x) ;
      }
      return res;

      }

      ~~~~~

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

        you declared your result as int. change it to long long

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

        Why do you have the variable res as an int? This will obviously overflow since int can only hold up to 32 bits

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

        Can use 1ll << i in place of pow(2,i)

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

    just use the bit operator << for powers of 2 in general.

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

    A usual double uses only 56 bits of precision, but we can have up to 59 zeros. Consider to use 64-bit integers and shift operation instead of pow().

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

    I'll suggest use bitwise technique to do 2^ like (1ll<<(count0)). And 1ll is the most important because I got wrong on third pretest because of that, here ll is long long

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

    dont forget that you must use long long

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

    2^cnto can go beyond Integer max, maybe use 2ll?

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

    if only has 1,the answer is 1.

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

AlFlen for D for the case where all elememnts are 10000 and n=100000 then the sum of abs(bi) = 1000010000, which is >10^9 Acc to editorial.

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

    it will only happen for odd numbers(when n is odd) since 10^5 is even it is possible to make it in <=10^9. The highest odd number it can go is 10^5 -1. so the sum will go till 10^4*(10^5-1)+10^4... which is 10^9.

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

    When n=1e5, since n is even the overall sum will be sum(abs(ai))<=1e9. And the largest odd value of n is 1e5-1, in that case one of abs(bi)>=1e4 and hence the total sum still remains less than 1e9.

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

Problem B cpp failed sol | Problem B python passed sol any idea why cpp solution failed while python passed? they were the same pseudo-code :/

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

    Because the answer will exceed the range of int. You should use long long instead.

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

      oops should have included the power function with corrected type of long long :( used that elsewhere where number was >10e6

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

Problem — B

Left shift
Logarithimc power method
Pow

Is'nt left shift and logarithimic power method better than pow??

why did my solution with left shift failed and how it is different from one in the editorial

anyone can explain why??

thanks in advance.

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

    I had the very same problem...got 4 WAs before writing the right permutation.

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

    1L is 32-bit, better use 1LL

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

      Adding to this, logarithmic power doesn't make any sense for this question. And the pow works because it is deduced as pow(long long, long long) since zc is long long.

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

    Shift only works till integer max value. Write your own function for computing long power

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

      No, shift works on long longs too. But use 1LL instead of 1 and 1L. Like 1LL<<n

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

    You have to use 1LL<<zc because 1<<zc will overflow the int type.

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

For Problem B,

The suggested solution returns an answer of 4 subsequences for the testcase below:

1

3

0 0 1

When I counted I could only get 3 subsequences:

[empty set]

0

0 0

Could somebody tell me if I had misunderstood? Sorry for bad formatting and thanks in advance.

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

    There are two sets with a single '0', because it is two different positions.

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

      I see... perhaps the question could have been more clear about the definition of a distinct subsequence. It appeared to me that subsequences would be equivalent if they had the same elements in the same order. Thanks for the clarification!

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

    Both 0s are considered different hence total number of sequences will be 4. "0" sequence will be twice. Basically ans=pow(2,zeros)*ones

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

    There are two subsequences which consist of just 0

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

    The subsequences are considered different if they containt elements with different indices, so $$$0$$$ (index $$$1$$$) and $$$0$$$ (index $$$0$$$) are two different subsequences.

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

      Стоит сказать, что при буквальном прочтении русского условия это неправда.

      Напоминаем, что последовательность x является подпоследовательностью y, если x может быть получена из y удалением нескольких (возможно, ни одного или всех) элементов.
      

      Здесь ничего про индексы не говорится, и исходя из условия, у последовательности не может быть две различных подпоследовательности вида [0]

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

        It's unfortunate that the statement missed the definition of different subsequences, but samples could clear up the misunderstandings, since there was a test with equal in elements but different in indices subsequences. My bad there was no clearer explanation in the legend part.

»
6 weeks ago, # |
  Vote: I like it -15 Vote: I do not like it

weak pretests!!! rnm tq!

»
6 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

The editorial is working now

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

1582A - Лунтик и концерты can someone explain what worng in my code its giving WA at 2

int a,b,c;
            cin>>a>>b>>c;
           
            int ans=0;
           
               a%=2;
               b%=2;
               c%=2;
               if(c!=0)
            ans=abs(3*c-a-2*b);
            else
              ans=abs(a-2*b);

[contest:https://codeforces.com/contest/1582]

»
6 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

problem A was really misleading and harder than most div2 A

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

I probably overkilled it, but i tried a fenwick tree solution to F1 but it gives WA on test 7. Could someone help?

https://codeforces.com/contest/1582/submission/132929945

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

Why does my code fail on D?

Spoiler

Please don't downvote, I might be completely wrong

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

    I had the same approach — consider the vector (1,2,2), i.e. where two elements are the same. Your answer outputs a zero for the first coefficient, which is not allowed.

»
6 weeks ago, # |
Rev. 4   Vote: I like it +14 Vote: I do not like it

D is slightly harder if sum of absolute values of $$$b$$$ is restricted to $$$n * max(|a_i|) + 1$$$. I accidentally solved this problem. Anybody interested can try too.

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

    yes, we can let $$$b_i = {-1, 1}$$$ for $$$1 \le i \le n-1$$$, then we've got $$$s = \sum\limits_{i=1}^{n-1}a_i \cdot b_i \le \max(a_i)$$$ and of course $$$a_n \le \max(a_i)$$$. Then we let $$$b_{n} = -s$$$ and multiply every $$$b_i, 1 \le i \le n-1$$$ with $$$a_{n}$$$

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

    How do you solve it?

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

    In fact, we can improve this bound on $$$\sum |b|$$$ to $$$O(n+\sum\limits_{x\in S}|x|)$$$, where $$$S$$$ is the set of values in $$$a$$$ without duplicates. We first process values of $$$a$$$ that are the same by a construction of $$$[1,1,1,\dots,-1,-1,-1,\dots]$$$ or $$$[2,1,1,\dots,-1,-1,-1\dots]$$$, and then process values of $$$a$$$ that only occur once with the original solution.

    I spent so long implementing this before realizing that when $$$n$$$ is odd it is at most $$$10^5-1$$$ :/

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

      its atmost 10^5 know?

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

      also if i use editorial approach when $$$ n=10^5 $$$ and all $$$a[i]= 10^4 $$$,wont the sum of $$$ b[i] $$$ becomes $$$ 10^9+10^4 $$$ ? or am i doing wrong ? :( please anyone clarify

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

    D can be solved using the pigeon hole principle as there exist significantly many repetitions in the extreme case where $$$n=10^5$$$ and $$$a_i$$$ takes at most $$$2\times10^4$$$ values, we can sort and eliminate adjacent identical elements using $$$(-1, 1)$$$ which significantly reduces the absolute sum of $$$b_i$$$'s, remaining cases can be handled similar to the editorial.

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

      my approach was if n is even answer vector would be a[1], -a[0], a[3], -a[2],.. else we can do same for n-3 elements and for first three ans[0] = a[2], ans[1] = a[2] then we calculate for ans[2] = — (ans[0]*a[0] + ans[1]*a[1])/a[2] if ans[2] is zero we give ans[0] = 2*a[2] then ans[2] = -(ans[0]*a[0] + ans[1]*a[1])/a[2]. code

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

Actually Could someone pls tell me why my approach on D failed ? consider a[1] * x + a[2] * y = a[3] + a[4] + ...

let t be the gcd(a[1], a[2]) let v1 = a[1] / t, v2 = a[2] / t

so t1 * x + t2 * y = sum, where sum = a[3] + a[4] + ...

we can solve for x and y using the extended eucledian method for finding the inverse and handling some corner cases. (when t2 * y = sum, ... )

Then we assign b[3] = b[4] = ... = t and a[1] = -x, a[2] = -y

Let g be gcd(-x, -y, t) divide the whole b array by g and print the answer.

But wrong answer on test 3 submission. Any help would be appreciated.

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

EDIT : Ignore this. The hypothesis was wrong.

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

Let's notice that since a,b,c≥1, it is possible to make a concert of any duration from 0 to S

Seems like you are solving a diophantine equation. But can I get more explanation on that statement please?

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

In problem A, Can someone explain why we can make every value from 0 to S?

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

    The way I see it is: for numbers that require less than all the segments of length 3, you can always write as 3k + r, where k is how many 3 length segments you take, and if r is 1 or 2, you use the corresponding length (there's at least one of each). If you need all the ones of length 3, just repeat this for the remaining length with those of length 2 and 1, namely, if it's even you use the 2's and you're done, and if it's odd, just add one of length 1.

»
6 weeks ago, # |
  Vote: I like it +56 Vote: I do not like it

My approach to F2 seems a bit different from the editorial's:

Say $$$dp_i$$$ contains all values $$$(ind_j, v_j)$$$, sorted by $$$ind_j$$$, such that it is possible to get an increasing subsequence with an xor of $$$v_j$$$ and last element at index $$$ind_j$$$, using only elements in the array less than or equal to $$$i$$$. If there are multiple possible values for one $$$v_j$$$, only store the one with the minimum $$$ind_j$$$.

To transition from $$$dp_{i - 1}$$$ to $$$dp_{i}$$$, first, add all elements already in $$$dp_{i-1}$$$ to $$$dp_i$$$. Then, for each $$$(ind_j, v_j)$$$ in $$$dp_{i-1}$$$, take the minimum index $$$k$$$ such that $$$a[k] = i$$$ and $$$k > ind_j$$$. Then, add $$$(k, v_j \oplus i)$$$ to $$$dp_i$$$ (if this $$$k$$$ does not exist, don't do anything). This can be done in linear time with two pointers if you store the occurrences of each $$$i$$$.

Two important details:

  1. To make sure that each $$$dp_i$$$ remains sorted, while transitioning, you can store the values $$$(k, v_j \oplus i)$$$ and $$$(ind_j, v_j)$$$ in two separate vectors, since each of these separately will be sorted. Then, combine the two in linear time (same method used in mergesort).
  2. To make sure you only store the minimum $$$ind_j$$$ for each $$$v_j$$$, you can keep track of the minimum value $$$ind_j$$$ for each $$$v_j$$$ with an array $$$minindex$$$. Then, only add a pair $$$(ind_j, v_j)$$$ to the dp if $$$ind_j = {minindex}_{v_j}$$$.

My code: 132932565

»
6 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Korney Korneevich sounded like gennady korotkevich to me :-)

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

132925114, this is my solution for E, i am getting RE on test 7 with exit code 2147483647, can someone please help.

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

I wonder whether it is possible to solve F2 with python? (python 3.8 or pypy or pypy-64) indeed python is somehow disadvantaged...but indeed it is easier to write-.-

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

Where is the editorial for F1?

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

Problem B was quite easy but punished me a lot. I was almost in tears when I finally got an AC before contest ended. I can't stop thanking you guys for the pain and frustration you caused me during the contest. (◍•ᴗ•◍)❤.

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

Are there any other solutions for D?

except editorial

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

Can you somehow solve D with a Diophantine equation? I tried to, but I failed on the third test.

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

    not needed just make pairs if n is even else make pairs with n-3 elements and for first three give a[2] value for result[0] = a[2] and result[1] = a[2] then calculate result[2] = -( a[0]*result[0] + a[1]*result[1] ) / a[2] if a[2] is zero make result[0] = 2a[2] and then calculate result[2]

    code

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

Could someone plz share the tutorial of problem F1 which has a relatively easier solution? Thx!

  • »
    »
    6 weeks ago, # ^ |
    Rev. 5   Vote: I like it +15 Vote: I do not like it

    Solution for 1582F1 - Корней Корнеевич и XOR (простая версия):
    We want to find all $$$x$$$ such that there exists a strictly increasing subsequence with xor sum equal to $$$x$$$ in the given array. Since $$$0 \le x \le 500$$$, there are about $$$512$$$ possible values of $$$x$$$, and they form a contiguous range — $$$x \in [0, 512]$$$. So let's do some dynamic programming where $$$\it{dp}_x$$$ stores the smallest possible ending value of a subsequence which has a xor sum of $$$x$$$. We store the smallest ending value of a subsequence with xor sum $$$x$$$ because when we want to form a particular xor sum by including an element, our strictly increasing condition must be satisfied and storing the smallest value allows for a greater range of new ending values. We can initially set $$$dp_x$$$ to $$$0$$$ and all the other values to $$$\infty$$$. To transition between states, iterate over the elements in the array and for each value of $$$x$$$ try to find a subsequence which makes that $$$x$$$ possible. Minimise $$$dp_x$$$ with $$$A_i$$$ if $$$A_i > dp_{x \oplus A_i}$$$. Finally, we can form xor sum $$$x$$$ for all $$$x$$$ where $$$dp_x < \infty$$$. This works in $$$O(N\times\it{max}(A_i))$$$ which is $$$10^5 \times 500 = 5 \times 10^7$$$ operations in the worst case.

    Take a look at my submission for more clarity: 132945454.

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

      I am dumb can you explain it like there is an animal in front of you

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

      brother, please briefly explain how it is work?

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

      Hello , can you tell me why did you take ndp and did swap thing and not updated in previous dp itself. Does not taking new dp array leads to WA sometimes?

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

C reference code is written very well!!!It's better than what I wrote.

»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

I have a simmilar solution for C that should have better complexity:

First notice that the center of the palindrome can vary, but the edges don't. Because of this we can check the first with last, second with second to last, ... and stop when we find 2 different chars or we checked all pairs(answer is 0).

When we find some i such that S[i]!=S[N-1-i](with 0 based indexing) there are 2 possibilities:

  1. Deleting either one leaves a palindrome in which case the answer is the minimum of the required removals in the case that they produce a palindrome.
  2. Removing neither one of them will produce a palindrome so the answer is -1.

The reason why there are only 2 cases is that if we remove some other character then we will still have those 2 characters mismatched. So we need one of them to go away.

The complexity would be O(N) with at most 3 passes through the string. The solution presented in the tutorial does a similar thing but doesn't stop when it finds the different characters and so it loses time. With some tighter time limit(Or if we expand the alphabet, maybe with upper case letters or diggits) it might not fit.

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

As always, here are the video solutions for the first 6 problems(A to F1) :

solutions

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

There is an easy solution for F2. Let dp[i] be the first index in which its possible to make an increasing subsequence of xor i. Lets also maintaing a vector of vectors V such that V[i] stores all the occurences of i in the array in order.

We can now iterate through the values x, and for we to update dp[i] we do dp[i] = min(dp[i],V[x].upperbound(dp[i^x])).

This works in $$$O(n+maxa^2*log(n))$$$: https://codeforces.com/contest/1582/submission/132952152

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

    could you explain how this solution ensure subsequence is increasing ?

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

      You are iterating through the values in increasing order, so you just worry about the index. If youre worried about repeating one of the values in the answer, notice that in that case you cant lower the value of the dp when we try to do that, so it wont count in the answer

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

    the concept is still not clear. Could you please elaborate more?

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

      What exactly wasnt clear?

      Also try checking the code and locate where im doing what im saying.

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

Proof for problem A solution

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

Can someone explain if this solution to problem G works? I was confident that I had a simple $$$\Theta(n)$$$ solution, but it's failing on test case 18 for some reason so now I'm feeling doubtful. I don't know if the problem is my code or my proof though.

Here is the proof:

We scan the array $$$a$$$ of size $$$n$$$ from left to right. For any integer $$$r$$$, we define $$$S_r$$$ to be the set of possible starting points $$$l$$$ such that the segment $$$[l;r]$$$ is simple. Then it follows from the definition that the solution to the problem is $$$\sum_{r\in [0,n)} |S_r|.$$$ Now, we consider how to compute $$$S_r$$$ from $$$S_{r-1}$$$. If $$$b_r$$$ is '*' or $$$a_r$$$ is 1, then $$$S_{r} = S_{r-1}\cup {r}$$$, since any path that worked before will still work, and the path starting at $$$r$$$ will also work.

Now, if $$$b_r$$$ is '/' and $$$a_r$$$ is not 1, then to get $$$S_r$$$, it suffices to take $$$S_{r-1}$$$ and remove invalid starting positions. (Namely, we remove any element $$$l\in S_{r-1}$$$ such that the segment $$$[l;r-1]$$$ ends with a number that does not divide $$$a_{r}$$$.) Observe that for any two elements $$$l_1 < l_2 \in S_{r-1}$$$, if the segment $$$[l_2;r]$$$ is simple, then the segment $$$[l_1;r]$$$ is also simple. To see this, first note that the segment $$$[l_1, l_2]$$$ must be simple, since otherwise, $$$[l_1, r-1]$$$ would not be simple, contradicting the fact that $$$l_1\in S_{r-1}.$$$ Thus we just need to remove the largest few elements of $$$S_{r-1}$$$ to compute $$$S_r$$$.

For any two consecutive elements $$$l_i, l_{i+1} \in sorted(S_{r-1} \cup r)$$$, we can say that the value of the path $$$[l_i;l_{i+1}]$$$ is the value remaining after traversing this path. To compute $$$S_r$$$, we continuously pop the largest-indexed element from $$$S_{r-1}$$$ and divide $$$a[r]$$$ by that element's value until $$$a[r]$$$ is 1. Some caution is needed to maintain the invariant — you need to update the last value you popped out from being the value of a path $$$[l_i;l_{i+1}]$$$ to the value of the path $$$[l_i, r]$$$.

Here is the code: https://codeforces.com/contest/1582/submission/132953817

In the code, V is a stack of the value of paths $$$l_i, l_{i+1} \in sorted(S_{r-1} \cup r)$$$.

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

    It doesn't work, check this simple counter example:

    4
    3 2 3 2
    **//
    

    I think you will be able to understand why it doesn't work by yourself.

    *I tried the same :)

»
6 weeks ago, # |
Rev. 4   Vote: I like it +16 Vote: I do not like it

Maybe maintests of F2 are a bit weak.
My sulotion to F2 has only considered the first and last three times of occurrences for each different elements.
So can somebody hack me or prove that it's correct.
Here it is

Anyway,There is also a sulotion has passed maintests but hacked by me. this one
Perhaps we need stronger maintests

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

I want to understand F1!

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

Why I couldn't do problem C:(

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

I have another solution for E that works in $$$O(NlogN)$$$. Maybe it is hackable because I am not good at proving.
Here is the submission: 132984246
Reverse the array first. Let $$$dp_{i,j}$$$ be the maximum sum on the segment of length $$$j$$$ considering all elements on the prefix $$$i$$$.
Then the transition should be like:

for(int i = 1; i <= n; i++) {
	for(int j = 1; j <= n; j++) {
		dp[i][j] = max(dp[i][j], dp[i - 1][j]);
	}
	long long sum = 0;
	for(int j = 1; i + j <= n; j++) {
		sum += a[i + j - 1];
		if(sum >= dp[i - 1][j] && sum < dp[i - 1][j - 1])
			dp[i + j - 1][j] = max(dp[i + j - 1][j], sum);
	}
}

I added sum >=dp[i-1][j] to the condition because if sum<dp[i-1][j] then sum>=dp[i+j-1][j] will not holds.
It can be noticed that $$$dp_{i,j} \ge dp_{i,k}$$$ if $$$j \le k$$$ (Like LIS) and sum is increasing, so the condition sum>=dp[i-1][j] holds for monotonicity. Also, sum<dp[i-1][j-1] must hold, too.
Therefore, the if condition will be triggered at most once for every $$$i$$$: when the first $$$j$$$ such that $$$sum(i..(i+j-1))\ge dp_{i-1,j}$$$. And we can use Binary Search to find such $$$j$$$.

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

I request proof of 1582C - Баба Капа вяжет шарф. Why this approach indeed find optimal removal for fixed letter? AlFlen can you explain?

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

    Think of the greedy algorithm as of a forming a palindrome from the beginning and from the end. If the symbols are equal, there is no need to erase them, and if they are not, the palindrome can't be formed without the erasure (we can't choose which symbol to erase since only one can be equal to the chosen letter).

    Why us not erasing one of equal symbols will not lead to a wrong answer: since they are equal, it's either we can erase both or we can't erase any, and we won't break any future pairs in palindrome (both current symbols are equal to $$$c$$$) because if one of them could be paired (in palindrome) with another symbol (equal to $$$c$$$ since we have the ability to erase current symbols) but it didn't, it's no matter what to erase: current symbol or the future one, but with not erasing the current one we don't break our palindrome sequence and don't disturb further formation.

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

      it's no matter what to erase: current symbol or the future one, but with not erasing the current one we don't break our palindrome sequence and don't disturb further formation.

      It's easy to say, but why it doesn't break? I'm starting to understand. If we remove pair — obviously better to keep pair. But if we remove one when we could keep pair, then $$$c$$$ will remain at one side, and we either finally keep it, then it will be paired with other $$$c$$$, so we could pair it in the first place, or it will be removed, so we could remove it in the first place. Not sure if it's rigorous.

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

Can Anyone Explain or prove point 1 of 1582F2 — Korney Korneevich and XOR (hard version) Tutorial (using a test case would be very helpful) . example test case is:

12

4 2 6 5 2 4 5 6 4 2 5 6

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

Why are we taking maximum of the two choices in the div2E and not minimum?

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

I did Problem C in O(N) if anyone is interested in knowing my approach. It's long but easy to understand.

Explanation — We can only form palindrome if we remove the first nonmatching character either from the left or from the right. Thus, the answer is the minimum of the number of similar characters to be removed to make it a palindrome. In further testing of indices if both the nonmatching characters are not the ones we are changing, then it is not possible to form a palindrome.

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

Hello guys,

So, in problem E I tried implementations with 2D array as well as vector<vector >. However, only vector implementation passes and the array implementation gives runtime error on test 8. Can somebody explain this? Besides, the vector implementation needed 1900 ms to pass which either means that the 2s bound was tight or I have implementation issues. Can anyone suggest improvements for vector implementation?

vector impl: 133108745 array impl: 133108661

»
6 weeks ago, # |
Rev. 2   Vote: I like it -18 Vote: I do not like it

It's my solution for problem B

include<bits/stdc++.h>

define ll long long int

using namespace std; ll n,k,t,a[100000],b,c,d,e,f,g; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> t; while(t--){ b = 0; c = 0; cin >> n; for(ll i = 1;i <= n;i++){ cin >> a[i]; if(a[i] == 1) b++; if(a[i] == 0) c++; } b *= pow(2,c); cout << b << "\n"; } }

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

can anyone pls explain the last line of editorial of B cout << (1ll << cnt0) * (ll)cnt1 << '\n';

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

    (1ll << cnt0) * (ll)cnt1 =( 2^(cnt0) ) * cnt1, where cnt0 = # of 0's and cnt = # of 1's in the array a.

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

I am getting TLE for Problem E but I think my solution is O(nk), k = sqrt(n). Not sure why. could anybody please help me with this. Solution link : https://codeforces.com/contest/1582/submission/133125904.

Although I am looping for j=1 to k and then calling memo(), but according to me, the total dp state calculation time is O(nk) only.

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

In problem D in the case of n being odd

isn't the sum of the array b going to be 1e9+1e4 which exceeds the required constraints?

Can someone please explain it to me?

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

    TL;DR No because the max value for $$$n$$$ where $$$n$$$ is odd is $$$n=10^5-1$$$.

    The worst case where $$$n$$$ is odd is $$$n=10^5-1$$$ and $$$a_i=10^4$$$ for all $$$i$$$. So our $$$b$$$ array has $$$10^5-2$$$ elements where $$$|b_i|=10^4$$$ and one where $$$|b_i|=2*10^4$$$. And the sum is $$$(10^5-2)*10^4+2*10^4=10^5*10^4=10^9$$$.

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

In editorial for G, can someone please explain what next_i is really calculating?

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

Can someone please explain the intuition behind the problem C, i did get the logic of it but not getting why its working

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

D can have more than one possible answer in some cases (1,-1 can have 1,1 and -1,-1). It is saying that my output is wrong.

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

For problem C, the answer can probably be obtained by using either the first or the last character in the original string. There is no need to run the algo for all the 26 characters :p