flamestorm's blog

By flamestorm, 2 months ago, In English

Thanks for participating!

1692A - Марафон

Idea: mesanu

Tutorial
Solution

1692B - Все различные

Idea: mesanu

Tutorial
Solution

1692C - Где слон?

Idea: flamestorm

Tutorial
Solution

1692D - Часы

Idea: SlavicG

Tutorial
Solution

1692E - Двоичный дек

Idea: flamestorm

Tutorial
Solution

1692F - 3-Сумма

Idea: flamestorm

Tutorial
Solution

1692G - 2^Сортировка

Idea: flamestorm

Tutorial
Solution

1692H - Азартные игры

Idea: mesanu

Tutorial
Solution
 
 
 
 
  • Vote: I like it
  • +48
  • Vote: I do not like it

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

Thanks for the fast editorial

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

Perfect contest for me.

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

tns fr the tutorial

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

Thanks for the fast editorial

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

I loved the contest, especially problems F and G.

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

How to solve H without using trees?

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

    For example using a Kadane's algorithm. My submission that using it is here.

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

      But if we apply Kadane's algorithm for every possible value of a wouldn't the complexity will be O(n^2)?

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

        for each a, store positions of a[i] = a then the complexity is O(nlogn) because use have to compress value of a[i] or store them in map

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

    I used Kadane's algorithm, where I kept track of the indices of each number, and inserted a certain amount of negative 1's between each index.

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

    As explained in the editorial, for a fixed $$$a$$$, you can replace $$$arr[i]=1$$$ if $$$arr[i]==a$$$ else $$$arr[i]=-1$$$.
    Now, you can find max sum subarray in this newly obtained array without using Segment Tree.
    Observe that the max sum subarray will always start and end at indices where $$$arr[i]==1$$$.
    Using this observation you can just iterate over indices where $$$arr[i]==1$$$ and use Kadane's Algorithm to find max sum subarray.
    Since, there are only $$$n$$$ distinct values of $$$a$$$ possible, overall time complexity will be $$$O(n)$$$.

    For more clarification, you can see my submission

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

      I don't understand how you found the constant a in this case

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

        No, I am not saying $$$a$$$ is constant but $$$a$$$ will definitely appear in the given array. So we can just iterate over all the distinct elements of the array and then considering current element as $$$a$$$ calculate the answer. Maximum over all elements will be the final answer.

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

          but wouldn't that be O(n^2) because for every distinct a[i] you need to check the maximum subarray?

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

            For every distinct $$$a_i$$$ we will iterate over indices of its occurrence. Now sum of number of indices for all distinct $$$a_i$$$ will be $$$n$$$(obviously). So inner loop will run only n times for the whole array.
            Time complexity: $$$O(n+n)=O(n)$$$

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

              again, there can be n distinct a[i] numbers, and if you iterate each one that would be n*n?

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

                Think about it. If there are n distinct numbers then number of occurrences of every number will be 1. So inner loop will run only 1 time for every element not n times.

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

      Correct me if I'm wrong, but creating the map $$$m$$$ will require $$$\mathcal O(n\log n)$$$ time.

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

        Yeah, you are right. I always tend to ignore map's complexity, lol. You can also use unordered_map for better complexity but that isn't necessary.

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

    A solution using set Code

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

    A solution using map here 160632225

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

    Then it's just kandene my dear friend.

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

    I used divide and conquer, here is my code

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

    I used DP

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

    I think this is easy solution using map 160604275

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

An elegant solution for G

https://codeforces.cc/contest/1692/submission/160651007

Was very painful as I submitted just a minute after the contest finished...

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

**problem H **, also can be solved useing kadane's algorithm.

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

H can be solved in O(n) just iterating for indexes of each a that is in array. My solution is here

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

    You're inserting into a map, so it's not $$$O(n)$$$

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

      We can utilize the map in a way that it never holds more than two elements, and hence works in O(1), which makes the solution O(n).

      see 160608733

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

        I think for an input like [1,1,1,1,2,2,3,...] the map would have to hold 3 elements. So in the worst case the map holds log(n) elements.

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

    Bro come Atleast do some research before claiming time complexity. It's not O(N) coz you are using map. But i guess the operations are quite low so we can it's O(N) but technically it's not.

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

    why my code gave wa on test case 3 pls check my code and tell the test case where my code fail 160727894 this is my soln link

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

    I tried running this with unordered_map but its fails with timeout error. Why is this the case? Why would iterating over an unordered_map take so much longer than iterating with map?

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

      Because unordered_map has an O(n) complexy for operations in a worst case.

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

        Cool thanks. Where in the documentation can I find this just for future reference?

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

Able to solve only problem A,B.For problem C got the approach but unable to implement it.

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

Problem H can use Kadane in a nice way.

Notice that the sum over frequencies of distinct elements is the size of our input array.

We know any subarray endings should be at two elements that have the same value, otherwise, we are pointlessly reducing our answer and we can fix our boundaries to be on the same boundaries.

say if we have XXXLXXXRXXX where [L, R] is the subarray we are considering then there is no point in having the left or right boundaries on Xs since we could improve the sum by restoring boundaries to L and R.

We can make an array of positions for each distinct element and use the observation that the Xs can be compressed together, therefore for each distinct element, such a compression yields a size of array twice the array of all positions for that element.

So our solution boils down to making a compressed array for each distinct element and then applying kadane to it, finally taking the one which gives the maximum answer.

Time complexity is still the order of n as we are effectively applying kadane on twice the input size.

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

Problem F : O(10^3) preprocessing + O(n) approach Submission

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

https://codeforces.cc/contest/1692/submission/160650500

Here , is my submission for problem G, i didn't get how I am getting wrong answer on testcase 15, can someone please explain fault in my submission?. Thank you.

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

    probably a floating precision error cause you are using v[i]=log2f(x)

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

      is there anyway we can store log base 2 of any number upto say 20 order of precision?

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

        Depends on what you mean by "20 order of precision". If you mean just 20 digits in the number then surely double-precision floating-point can hold that amount of digits. If you mean 20 digits in fractional part, then you can't have a guarantee since it depends on how big your number is

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

        Btw, you can use 63 - __buitin__clzll(x) instead of log2f(x) if you're using gcc/g++. Or you can use something like that (code below), but I'm not sure if it'll resolve your problem

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

Solution of H without trees

Instead of doubling and halving, consider the score of a subarray to be the difference between the frequency of $$$a$$$ and the number of elements in the subarray not equal to $$$a$$$. This is done because we will double our score for $$$freq[a]$$$ times and halve it for the rest elements and hence we want this difference to be maximum. Notice that for the best subarray, $$$a = x_l = x_r$$$. The problem can now be solved with dp. Let $$$dp[i]$$$ be the best score for a subarray with $$$l = i$$$ and $$$a = x_i$$$. Then we can see that $$$dp[i] = 1 + max(0,dp[next[a[i]]] - (next[a[i]]-i-1))$$$, where $$$next[x]$$$ is used to store the next occurence of $$$x$$$ on iterating over the dp. The right end can be maintained similarly(if the dp is maximised then $$$right[i] = right[next[a[i]]]$$$.

Submission at the time of the contest — https://codeforces.cc/contest/1692/submission/160583853

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

how do you find the test cases of a question?????????

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

    some of the test cases are shown in the status i.e your submission but sadly you can't see all of'em as they're truncated if they're too long. although some times what i do is (it's stupid :D) that for some value of test case i print it instead of printing the ans with all values in it but this too doesn't always work.

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

    You can try something like this.' Change the values according to your question and change the "if" value to your testcase-1

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

can any one do the f question using bit manupulation

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

What is wrong with my code?? can anyone check for f question : please https://codeforces.cc/contest/1692/submission/160683383 Link

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

    actually what you're doing is that you're checking for pair i,j,k but if u dont get it ur also removing it from the array by freq--.

    like: 1 2 5 6 you'll check for 1,2,5 = 9 so u remove 1 2 but 2 5 6 actually gives the ans i.e 13

    what you have to do is first check if we take 3 same values (if they're present) and get the ans. then again same if we take 2 same values and one any other value. then all 3 different values.

    in all these check if they're present with the required freq.

    if we want to take 3 same values.

            for(int i = 0;i <= 9;i++){
                if(arr[i] > 2 && ((3*i) % 10) == 3){
                    y = 1;
                    break;
                }
            }
    

    if we want to take 2 same and 1 diff.

            for(int i = 0;i <= 9 && !y;i++){
                if(arr[i] == 0) continue;
                for(int j = 0;j <= 9;j++){
                    if(i == j || arr[j] < 2) continue;
                    if((2*j + i) % 10 == 3){
                        y = 1;
                        break;
                    }
                }
            }
    

    and lastly all different

            for(int i = 0;i <= 9 && !y;i++){
                for(int j = 0;j <= 9 && !y;j++){
                    for(int k = 0;k <= 9;k++){
                        if(i != j && j != k && k != i){
                            if(arr[i] > 0 && arr[j] > 0 && arr[k] > 0){
                                if((i + j + k) % 10 == 3){
                                    y = 1;
                                    break;
                                }
                            }
                        }
                    }
                }
            }
    
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      got it.. Thanks man..

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it
      bool helper(vector<int> freq, int target){
          for(int i = 0; i<10; i++){
              if(freq[i]<=0)continue;
              freq[i]--;
              for(int j = 0; j<10; j++){
                  if(freq[j]<=0)continue;
                  freq[j]--;
                  for(int k = 0; k<10; k++){
                      if(freq[k]<=0)continue;
                      if((i+j+k)%10 == 3)return true;
                  }
                  freq[j]++;
              }
              freq[i]++;
          }
          return false;
      }
      Your code here...
      

      changed a little bit and got accepted thanks

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

Can we use sliding window for E by searching total sum minus reqd target in the sliding window?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it
    for(int i = 0; i<8; i++){
        int c = 0;
        int k;
        string s = arr[i];
        for(int j = 0; j<8; j++){
            if(s[j] == '#'){
                c++;
                k = j;
            }
        }
        if(c == 1 && i !=0 && k != 0){
            cout<<i+1<<" "<<k+1;
            break;
        }
    }
Your code here...

For question 3 where is bishop, what's wrong with this logic :: Please check my code once https://codeforces.cc/contest/1692/submission/160574089

if possible let me know how can i check testcase which are not failing only i can 7 out of 36 testcases. Thanks

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

    _ _ _ _ _ _ # _

    _ _ _ _ _ # _ _

    _ _ _ _ # _ _ _

    _ _ _ # _ _ _ _

    # _ # _ _ _ _ _

    _ # _ _ _ _ _ _

    # _ # _ _ _ _ _

    _ _ _ # _ _ _ _

    consider this example i think so it's self explainatory.

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

For problem D, A brute force approach I used — 160599689.

I just kept adding the minutes to the time until the time was the same as starting and kept checking for palindrome.

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

can someone tell me what's wrong with this https://codeforces.cc/contest/1692/submission/160689162 ??

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

Please add the proper tags for the problem and not the unnecessary one. Thanks.

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

Solution of H without using segment trees: https://codeforces.cc/contest/1692/submission/160692781

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

Could anyone help me with problem E: Binary Deque? My solution is kind of greedy. I create an array with distances (in numbers of zero entries) between two conseсutive ones. For example, for the sequence: 0 0 1 0 0 0 1 1 0 1, my array is [2 3 0 1 0] (last zero means that we have tail of zeros with length 0). Next, I use two iterators for decreasing the sum of the array choosing at every step iether the head or the tail with zeros and errasing it from my array. I cannot find the mistake and 1st test is OK, but I get WA for the second. If this idea is correct then the solution is O(n). Here the link: 160692840

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

    I have a solution of E:

    You can define an array $$$k$$$, It is prefix sum of $$$a$$$, so $$$k_i$$$ is "How many ones in [1,i]". The range [l,r]'s sum is S when $$$k_r-k_{l-1}=S$$$, you can define an array $$$m$$$. $$$m_i$$$ is "The max index j that k[j]=i". Then enumerate $$$l$$$, and the max of $$$r$$$ is $$$m_{s+k[l-1]}$$$, the answer is the minimum of $$$n-(r-l+1)$$$. If every $$$r$$$ is $$$0$$$ ($$$s+k[l-1]>n$$$), Then output -1. My code: 160569001

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

    I think this logic is incorrect as this only accounts for the head or the tail. If the sum we needed was 5 and your array was [5 0 0 0 0 4 4 4 4 4], it would incorrectly assume that it should take from the tail every time instead of realizing that the 5 is better in the long run.

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

Can anyone explain the Kadane algorithm approach for the H problem? I am unable to understand what one is exactly trying to do.

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

    I've done something very similar to kadanes (with an early break when the sum reaches 0):

    For each position (starting from left) iterate through the array adding +1 for matches and -1 for other values. If the sum gets to 0 break. Any start positions that have previously added a +1 are skipped (as you've already calculated the sum from that position starting from at least 1).

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

Thank you for fast editorial and interesting tasks.

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

Pretty sure we can do a O(n) solution for E right? I did this. Doesn't use map stl. https://codeforces.cc/contest/1692/submission/160607428

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

    I did an O(n) with 2-pointers technique

    https://codeforces.cc/contest/1692/submission/160604366

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

      can you explain the logic behind this? I also tried a 2-pointers technique but I don't think my solution works. Also, how is your solution O(n) if it has nested loops?

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

        Ok I'll try.

        We're moving right pointer while sum in segment [l, r] is less/equal to s. If our sum is larger than s, we're moving the left pointer to reduce it. When sum is equal to s, update the answer. Thus, we'll find all subsegments with sum equal to s.

        Complexity is O(n) because we're moving the right pointer N times and left pointer no more than N times.

        Actually, my code is almost a copypaste of edu`s one (first block), there's a detailed explanation as well.

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

The tutorial is very good, I can understand it very clearly.

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

Two pointers Contest :)

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

I recently read a blog that said "Stop making Div4 contests". All I can say is, please DON'T stop making them, they are very helpful for people like me, and I'm sure a lot of others. I learnt a lot from this contest. Thank you..!!

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

Can we do E by 2 pointers, and a greedy approach? I thought of this — https://codeforces.cc/contest/1692/submission/160617363 but it is giving a wrong answer :')

Can anyone think where can it be wrong? because I am unable to find any case...

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

The hacking phase is done why isn’t my rating updated?

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

anyone please tell me where am i wrong 160716728 problem D

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

    I think line 74 should be "checkhour>=24" instead of "checkhour>24"

    Also line 41~44 is not correct because the clock never shows 24:00.

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

thanks for the editorial!

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

Good Contest for me

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

I'm not too fond of the author's solution to problem H, though the problem was great. But no divisional 4 rounds should contain any Data Structure. Here's my solution —

The basic observation is that the problem simply asks us to find, for each element(x) of the given array, the maximum subarray sum on another array(b) where b[i] = 1 if a[i] == x, -1 otherwise.

We can apply Kadane's algorithm for each element lazily. In Kadane's algorithm, the important variables are current sum, current best, and where the best subarray is. So, as we iterate over the array, we evaluate elements one by one and remember these important variables for each element and their last positions, std::map works fine.

And finally, we can just iterate over the map to find the best answer and the desired segment with the same asymptotic, O(n.log(n)). See my implementation if need be.

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

What is the wrong on my solution Problem E ? im using two pointers to get the best distance from left and right.. 160727889

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

    1
    12 1
    0 0 1 0 0 1 1 1 1 0 0 0
    You answer is 8 , but the correct answer should be 7. It is easy to know that this greed will not work...

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

Can anyone please point out the error in my code/logic (Problem G). I used a sliding window approach by making a window of size k. The variable bad used in my code tells the last index till the current index where the inequality does not hold.

My submission
https://codeforces.cc/contest/1692/submission/160622089

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

can anyone tell whats wrong with this code for problem H? https://codeforces.cc/contest/1692/submission/160731054

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

160731775 : An Elegant solution for Problem H:no segment tree required

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

why my code gave wa on test case 3 pls check my code and tell the test case where my code fail 160727894 this is my soln link

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

why my code gave wa on test case 3 pls check my code and tell the test case where my code fail 160732937

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

Where can I find a tutorial for the standard problem of finding the maximum sum of a subarray?

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

In D, why is the second for loop running for 2022 iterations?

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

    Any number greater than 1440 because after that the numbers will repeat again.

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

When does the rating update?

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

An alternative solution to problem H without segment tree. Notice that if we choose $$$(a,l,r)$$$, the money we will get is $$$2^{x-(r-l+1-x)}\ =2^{2x-(r-l)+1}\ $$$ ($$$x$$$ is the number of times that $$$ a $$$ appears in round $$$l$$$ to round $$$r$$$). Thus our goal is maximizing $$$2x-(r-l)+1$$$. For a certain number $$$a'$$$, we can create an array $$$b$$$, where $$$b[i]=-i+$$$ $$$2\times$$$(the number of times that $$$ a' $$$ appears in round $$$1$$$ to round $$$i$$$). And the money we will get by choosing $$$(a',l,r)$$$ is equal to $$$2^{2x-(r-l)+1}=2^{b[r]-b[l]+1}\ $$$! On the other hand, it's obviously that if the answer is $$$(a,l,r)$$$, then the dice must show $$$a$$$ in both round $$$l$$$ and round $$$r$$$. Therefore, we only need to consider the rounds where dice show $$$a'$$$ for a certain number $$$a'$$$. Based on the above, the problem can now be solved with time complexity $$$ \mathcal{O}(nlogn)$$$ by using maps and arrays. Checks this code for better comprehension:https://codeforces.cc/contest/1692/submission/160769341

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

when div5 begins to be held? I want a more easier division!

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

    kidding ?

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

      not kidding, i want a more happy contest, during which I can ak very fast

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

        But when sol hard prob, you feel happy more than it is easy

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

Great round!

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

In binary deque we can use deque to save index of 1s but it's giving WA can anyone help

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

    The problem is that you do not know what the order of 1s is after you remove the i-th one. So for example;

    0 0 1 1 0 1 0 1 0 0

    There is a 1 equally distanced on each end of the string, but the 1 that is after it, is closer on the left than on the right. So this "greedy" approach doesn't work, since you would have to also consider all other 1s up to the next one, but that is too long. Try a different approach.

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

Why does binary search work in E? Doesn't the array need to be sorted for that?

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

    It's already sorted since we bs on the prefix sum array

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

mesanu For Problem H, can you explain how you are updating and calculating the maximum sum subarray having elements -1, 1, and like how you are updating it in log(N). Like in your code what does pref, suf, Val, and sum store, and how your modify function is working as I'm having trouble with these parts. Thank you.

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

Can someone tell me what am I doing wrong ?

https://codeforces.cc/contest/1692/submission/160812969

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

For Problem E, the tutorial says we need the "smallest" value of r. Shouldn't it say the "largest" value of r instead?

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

can i use mod when multiplying with a big power of 2 (G-2^sort) ?

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

https://codeforces.cc/contest/1692/submission/160699527

Can Some help me to find the the error in my code. Why my code fails.

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

Here's another approach to problem H which is very surprising for me. We can just make store all positions of each distinct value. Then apply the Kadane's algorithm to find the leftmost and the rightmost of each local maximum power of 2. Lastly, just find the maximum of them. Here's the code to what I'm saying: https://codeforces.cc/contest/1692/submission/161122830

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

for Find Bishop why doesn't this code work void solve() { act vector<vector> a(9); for (int i = 0; i < 8; ++i) { for (int j = 0; j < 8; ++j) { cin>>a[i][j]; } } int r(0),c(0);

for (int i = 1; i < 7; ++i)
{
    for (int j = 1; j < 7; ++j)
    {
        if(a[i][j] == '#'){
            if(a[i-1][j-1] == '#' and a[i+1][j-1] == '#' and a[i+1][j-1] == '#' and a[i+1][j+1] == '#'){
                r = i+1,c = j+1;
                break;
            }
        }
    }
}
cout<<r<<' '<<c<<ml;

}

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

Tutorial for 1692E - Двоичный дек should be to "binary search on the largest value of $$$r$$$", and sum is "non-decreasing"?

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

for G, just apply log to all the array elements and then sum with each index. i.e [2^x . Ax ] will become x + log(Ax). then just iterate.

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

I love Div.4 very much

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

Thanks for the fast editorial

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

[Deleted]

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

Greedy Approach for last question : Gambling ->

Suppose we have this example :

10 
8 8 8 9 9 6 6 9 6 6

First make map< long long , vector> and insert key : [with vector of indexes]

8 : [0,1,2]
9 : [3,4,7]
6 : [5,6,8,9]

then iterate over vector of indexes of each element Initialize res = 1 ( represent power of 2. Initially 1 because for one occurrence we have 1*2)

for 8 : res = 1 ( index 0 )
start iterating from : index 1 
   if gap>0
   subtract gap ( res -= gap (here gap is 0) )
   and add +1 ( for current occurrence )

   index 2 : gap is zero
   so just add +1

   we get res = 3
   this means final money is pow(2,3) = 8

   if at any moment res become <= 0 then set res =1 again (as this is minimum value possible)
Do this for all and record max res

CODE

#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
#define ll              long long
#define pb              push_back
#define For(i,n)        for(int i=0; i<n; i++)
#define Fora(i,a,b)     for(int i=a; i<b; i++)

void solve(){

   ll n;cin>>n;
   vector<ll>v(n);
   For(i,n)cin>>v[i];
   map<ll,vli>m;
   For(i,n){
        m[ v[i] ].pb(i);
   }
   ll a = v[0] , l = 1, r = 1;
   double sum = 1;

   for(auto itr : m){
        vli temp = itr.second;    
        ll siz = temp.size();        
        double res = 1;
        ll start = temp[0];
        Fora(i,1,siz){
            ll gap = (temp[i]-(temp[i-1]))-1 ;
            res -= gap;
            res ++ ;
            if(res>sum){            
                sum = res;
                a = itr.first;
                l = start+1;
                r = temp[i]+1;
            }            
            if(res<1){
                start = temp[i];
                res = 1;
            }            
        }        
   }
   cout<<a<<" "<<l<<" "<<r;

}
int main() {
    int t; 
    cin>>t;
    while(t--){
       solve();
      cout<<endl;
    }
    return 0;}
»
6 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

hi

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

I want to share my program of task D-The Clock to other ones.

Click here to see my program
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Another div4 is coming soon

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

Ban div 4 contests.

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

pls someone give a hint for problem e unable to understand.

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

how are the questions new everytime in contests ?How do the setters bring new ideas everytime?

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

Will participate in next div4

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

how can we find sum of each subarray of an array separately without getting tle of O(n^2) and also the length of that subarray whose sum equals a particular given sum??

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

https://codeforces.cc/problemset/submission/1692/165121580

My submission for problem H, i don't understand how I am getting wrong answer on testcase 15, can someone please explain fault in my submission?. Thank you.

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

With two pointers E will take only o(n) why does the editorial say nlogn? My approach is to use two pointers to find the maximum window with sum==k and the answer will be a length-maxWindow. got Accepted but am not sure about the time complexity. Is it actually o(n)?

Kindly help.