chokudai's blog

By chokudai, 13 days ago, In English,

We will hold AtCoder Beginner Contest 174.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

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

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

how many languages will be provided?

»
13 days ago, # |
Rev. 2   Vote: I like it -56 Vote: I do not like it

Question E is really hard to understand imo, couldn't understand it at all. :(

»
13 days ago, # |
  Vote: I like it +16 Vote: I do not like it

It seems like button to copy sample input has disappeared from Tasks for printing page. If I remember correctly, it used to exist before. Please add it back.

»
13 days ago, # |
  Vote: I like it +45 Vote: I do not like it

Whats the point in giving copy pasting problems -_-

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

    It depends on the user if he/she wants to cheat or not. It's their own conscience that'll kill them. No matter how high they score, they'll just end up losing in the end since they didn't played fair.

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

    I agree, problems E and F were very standard this time

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

      Even without copy-pasting thing. Problems are trivial. I learned segment tree yesterday and guess what, solved the problem in 20 minutes.

      • »
        »
        »
        »
        13 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I was also using segment tree but I got TLE by 200ms. How did you do it?

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

        891 people solved all problems, which is way more than average ABC contest.

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

        Dude please can you tell me how to do F with segment tree :)

        • »
          »
          »
          »
          »
          13 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          • »
            »
            »
            »
            »
            »
            12 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I have been getting TLE on F for a while now, even using segment trees. Could anyone tell me as to how to further optimize it? Link to my submission-https://atcoder.jp/contests/abc174/submissions/15638983

            • »
              »
              »
              »
              »
              »
              »
              12 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Maybe it's because of maps. I'm not sure and can't get the approach too. I think your approach is different.

              • »
                »
                »
                »
                »
                »
                »
                »
                12 days ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Okay, so basically for any range [left, right], I am storing the different values in a map, and for merging any two ranges, I am just going through the 2 maps, and storing the number of distinct values. For instance if range 1 has values=>(1, 2, 2, 3), then my map will simply contain {1, 2, 3} and if range 2 has values (3, 4, 4, 4, 4), then the corresponding map will contain {3, 4}

                On merging the above two, the new map will have {1, 2, 3, 4}, and map.size() will be the answer!

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how do you solve F

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

        Link. This code in the first comment, with a direct solution

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

        Solution(Sum segment tree) :
        1. Sort the queries in order of $$$r_i$$$ and process queries offline. I don't know why it works.
        2. let, $$$last_i$$$ be the last appearance of $$$i$$$. Then, do the following. traverse the array.
        (a). $$$last[c[i]] = -1$$$, make $$$last[c[i]] = i$$$ and update position i in the segment tree with $$$1$$$.
        (b). $$$last[c[i]] != -1$$$ update position $$$last[c[i]]$$$ in the segment tree with $$$-1$$$, make $$$last[i] = i$$$ and update position $$$i$$$ with $$$1$$$.
        3. If a query ends in the current index, then query the segment tree.
        And bingo, that's it. I just took a chance sorting the queries in order of $$$r_i$$$ and it worked. I don't know why it worked.

        • »
          »
          »
          »
          »
          13 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Can you please give an intuition for problem E

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

            The idea is that last[val] keeps track of the rightmost index of val so far in the array. As you iterate through the array (let's say you currently see the element val), you replace the previous value of last[val].

            Now, the BIT contains 1 wherever the index is a rightmost element (i,e, BIT[idx] = 1 if there is a val such that last[val] = idx), and is 0 everywhere else.

            Now, when we want to process a query (l,r), we update last and the BIT up to r. Then we query (l, r) in the BIT to get the desired answer.

            • »
              »
              »
              »
              »
              »
              »
              13 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I think you misread E as F...

              • »
                »
                »
                »
                »
                »
                »
                »
                12 days ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                My bad, I thought he was asking about F because the comment he replied to was about F.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 days ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Yes Can you please provide intuition for E (Binary Search) I am not able to get what the question is asking to find

            • »
              »
              »
              »
              »
              »
              »
              12 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              very nice method, thank you WhaleVomit and hossainzarif. May i ask if anything with segment tree or BIT is possible for online queries?

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

                Seems challenging via a usual segtree/BIT. Here is one approach which uses persistent segment trees for online queries.

              • »
                »
                »
                »
                »
                »
                »
                »
                12 days ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                I tried to do this thing after contest to make my code work for updates but in vain. I haven't get any idea.

              • »
                »
                »
                »
                »
                »
                »
                »
                12 days ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                This can be done with a merge sort tree. See here.

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

              Thanks a lot. I had a hard time understanding the BIT code but I understand it now.

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

        Have a look at this blog, it might help same ans the only difference was the size of the array and order of input of query size.

»
13 days ago, # |
  Vote: I like it +92 Vote: I do not like it

I don't think this round is so well-prepared. Problem F has occured many times.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I tried F with segment tree and unordered_set<> but I got TLE by 200ms. I'm pretty sure I could speed up the merge of the segtree by not using unordered_set<>, but I couldn't come up with anything. How do you solve it?

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      solve it offline and using bit instead of segment tree

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

        Segment tree worked for me.

      • »
        »
        »
        »
        13 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        can you share the code please? thanks in advance

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

          You can just see other's codes in atcoder. You can just randomly pick one.

          • »
            »
            »
            »
            »
            »
            13 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            May i know the meaning of "solve offline"

            • »
              »
              »
              »
              »
              »
              »
              13 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              "Solving offline" is when you process the queries in a convenient order that may not correspond to the original one. This is not possible, for example, in interactive problems.

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

      I dont see why this will work, I mean merging or querying of segment tree will be not constant time per level right? Assuming that you are using set as node of segment tree.

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

        aYes the merging isn't constant time (i am using sets node for segment tree) it's O(c) (c is the number of colors). I was hoping I could optimize the merging in some way, but it turns out the solution has a different way of using the segment tree.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    D and C also

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

      Try using two pointers for D. One for the left and one for the right of the string. Count the number of times a W and an R meets until l >= r.

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

    I think E has also occurred many times, although it's not as standard as F. Isn't it common Binary Search?

»
13 days ago, # |
  Vote: I like it -15 Vote: I do not like it

So, I asked if I can do process queries and print after processing or I have to process one query and answer immediately. And I get no comments. I don't know why and certainly don't know if I have done mistake or not. Anyway, solved the task where I needed clarifications.

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

    Well, it seems obvious that you can do whatever you want with the input, it isn't an interactive problem.

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

how to solve problem F . please help???

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

    Mo's algorithm

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

      Did you manage to make your solution pass with Mo? TL is 2s and $$$n, q$$$ are up to $$$5\cdot10^5$$$.

      • »
        »
        »
        »
        13 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I see many people having done so, and it's quite confusing to me. How can Mo's pass such high constraints??

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

        If you use the usual query ordering you will get TLE. But if you use the condition to sort according to the parity of the block (decreasing and then increasing) it was enough to get AC.

        • »
          »
          »
          »
          »
          13 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It was once you get right constant approximating sqrt(n). I tried constants around $$$200$$$ which didn't work. But once you use $$$500$$$ it's enough to pass.

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

            But actually there was only one testcase large enough to have any chance of defeating Mo and it was random, so you can just be lucky to generate order of queries with relatively low total distance between consecutive ones.

          • »
            »
            »
            »
            »
            »
            13 days ago, # ^ |
            Rev. 2   Vote: I like it +21 Vote: I do not like it

            For me using constant as 1000, passed luckily.

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It passed easily (in about 1250ms) with block size $$$\left \lfloor{\sqrt{N}}\right \rfloor$$$ and the parity-based comparator.

        The Settings
      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hilbert curve ordering works pretty fast. My implementation of MO's algo passed in 647 ms.

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

After contest end then please give me some idea on C.

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

    Intitially i thought there must be some pattern, but after struggling for some time solved it using school mathematics. Important observations, 1) if n is even answer is always -1 2) answer cannot exceed the number itself. Check out my solution https://atcoder.jp/contests/abc174/submissions/15619615

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wow! that was easy!! -

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      And also if n if multiple of 5 the answer is -1.

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Man missed the last line. Great solution but.

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

      I am not able to understand why we not need more than K iterations???

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

        You can read the proof here

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          difficult to understand proof for me can you please explain in some easy language

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain why your code works.. I can't understand why k = (k%n)*10+7

  • »
    »
    13 days ago, # ^ |
    Rev. 3   Vote: I like it +2 Vote: I do not like it
    Here is my approach, 
    if n%2==0 OR n%5==0
    print -1;
    else         //( I used dfs to solve the problem)
    ll cnt=1;
    ll dfs(ll a, ll n)    // here a is initially 7
    { 
        if(a%n==0)
        return cnt;
        cnt++;
        return dfs((a*10+7)%n,n);
        
    }
    
    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain why n%5 is -1

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

        Lol, it will always end with either 5 or 0. So we can never get any of the required 7, 77, 777 ...

»
13 days ago, # |
  Vote: I like it +8 Vote: I do not like it

I can't find a difference between today's F and 1188 — Fast Queries . Really disappointed with today's contest :(

»
13 days ago, # |
Rev. 4   Vote: I like it -8 Vote: I do not like it

The problems seemed comparatively easy to me. I solved a SPOJ problem exactly like the problem F. I think the contest was not well prepared.

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

Same Question F from CSES can be found in GFG and other websites

»
13 days ago, # |
  Vote: I like it +93 Vote: I do not like it

Me during contest:

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Toothbrush is new problem setter for ABC contest.. from now onwards..

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

Can anyone give a little bit of hint on C Repsept. Is there any kind of tradition of Atcoder that problem C is more intresting and challenging than D.

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

F is almost similar to Spoj-DQUERY

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

Can someone please help out with Task C?

»
13 days ago, # |
Rev. 3   Vote: I like it +40 Vote: I do not like it

Mini-editorial:

A: if print else print. Code.

B: loop through all points and count where x[i]*x[i] + y[i]*y[i] <= d*d. Code.

C: Notice that "X is a multiple of K" means that x % k == 0. We can use modular arithmetic (modulo K) to find possible remainders. Adding another 7 to the end of X is the same as x * 10 + 7.

I think if after K iterations you don't get a 0, that means there's no answer, because there's only K different remainders modulo K. However, during the contest I wrote a different solution that detected loops in the sequence of remainders. Code.

D: The resulting sequence looks like $$$RRR..RWWW..W$$$, i.e. 0 or more R and then 0 or more W. Note that flipping the color fixes at most 1 stone, whereas swapping two stones can fix two, so we can ignore the color flip operation.

Maintain two pointers: one pointing to the leftmost wrong element (=W) and the other pointing to the rightmost wrong element (=R). Swap the elements until the pointers meet. Code.

E: Use (integer) binary search on the answer. Suppose the answer is X ($$$0 \leq X \leq 10^9$$$). Then go through all logs $$$A_i$$$ and count how many splits $$$K_i$$$ you need to get the length of each of them under X, using the equation $$$A_i / (K_i + 1) = X$$$. There's some funky arithmetic with the rounding, which I'm unsure of, but it works. Code.

F: Mo's algorithm (a type of sqrt optimisation). Note that if you know the answer for a window $$$[L, R]$$$, it's easy to move either side of the window one position to the left or to the right: You can use a vector (don't use map or unordered_map, they are too slow) to store how many elements of each color you have, and keep a counter of unique colors (to get the answer in $$$O(1)$$$.

Then, using the idea of Mo's algorithm, you can sort the queries into $$$\sqrt{Q}$$$ buckets in such a way that the total run time will be $$$O(N\cdot \sqrt{N})$$$ instead of $$$O(N^2)$$$. The trick is to first sort the queries by the bucket of their left edge $$$L$$$, and then within each bucket, sort them by the position of the right edge $$$R$$$. This ensures that you will move the left end of your window $$$O(Q \cdot \sqrt{N})$$$ times, and the right end of the window $$$O(N \cdot \sqrt{Q})$$$ times (and given the constraints, we can assume $$$Q = O(N)$$$).

This can be implemented with a custom comparison function, no explicit buckets needed. Code.

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

    Can you prove it

    I think if after K iterations you don't get a 0, that means there's no answer.
    
    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Pigenhole

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

        how?

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

          At a maximum the modulo value can take $$$k$$$ distinct values. If in $$$k$$$ iteration you did not arrive at $$$0$$$ then you never will because you are stuck in a cycle as said by Norrius

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

        Got it after every k iterations cycles of modulo will repeat as (2*k+1)%k=(k+1)%k=1%k. Thanks , I was not sure of this condition but this one word made everything clear.

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Eliminating corner cases where $$$k$$$ is $$$1$$$, $$$7$$$, or a multiple of $$$2$$$ or $$$5$$$, we can prove the statement.

      Suppose $$$7, 77, ..., \frac{7}{9}*(10^{k-1}-1)$$$ are all not multiples of $$$k$$$. By pigeonhole principle, $$$2$$$ of the numbers will have the same remainder when divided by $$$k$$$.

      We consider an example, say $$$7777777$$$ and $$$777$$$ are $$$x$$$ mod $$$k$$$. Subtracting, we get that $$$7777000$$$ is a multiple of $$$k$$$, which implies that $$$7777$$$ is a multiple of $$$k$$$. However, this gives us a contradiction since we supposed that it couldn't be a multiple.

      Thus, we will have a value which is a multiple of $$$k$$$ after $$$k$$$ iterations.

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

    For E, instead of using doubles, you can use $$$\lfloor(a-1)/b\rfloor$$$. To see why this works, if $$$a$$$ is a multiple of $$$b$$$ you need $$$a/b-1$$$ cuts.

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

    For Question C My Approach was since any such number will be of the form {7/9}∗{10^i−1} so I am iterating from i=1 to 1e6 and taking modulo with k. if at any case my modulo==0 then it's my answer. //Pseudo Code

    for( i=1 to 1e6+7)
        {
            if(((7%k)*(Modular_Exponentiation(10,i,k)%k+k-1)%k*(Modular_Inverse(9,k)))%k==0) 
            {
                cout<<i;
                return; 
            }
        }cout<<"-1";
    

    But I don't know why 5/27 test cases are giving WA. Please Can anyone help where it is getting wrong..

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For modular inverse to exist, gcd(9, k) = 1 should hold. I did the same and got RE.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think that my approach to ABC-D is quite simple.

»
13 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone share his/her approach of solving problem C. I tried it a lot , but was not able to solve it.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Think around long division method. You just need to add a digit 7 in every iteration. Code

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      May I know why only that k % 5 == 0 or k % 2 == 0 must don't have answer?

      • »
        »
        »
        »
        13 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        cause multiple of 2 & 5 always produce even number..but 777... is always odd..

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Byakuya_Kuchiki I have seen your code, may i please know how you came to the conclusion that "when the given number ends with 1,3,7,9 ,the answer exists".

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        2:2,4,6,8,10,12,... it will not generate '7' digit 5:5,10,15,...

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

          That didn't answer my question.

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Number to have a multiple in form of 777... should be co-prime with 10. For more formal explanation you can look at this editorial provided by AnandOza.

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

          Owhh, so thats why only have 2 and 5 doesn't have answer, thanks alot

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

    BFS

    start from 7 modulo n(length = 1) and keep adding next sequences modulo n to the queue until the queue is empty. If dp[0] is defined print that else print -1.

    Code

    Complexity: O(n) because there can atmost n distinct values with modulo as n

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here is my approach ABC-C

»
13 days ago, # |
  Vote: I like it +8 Vote: I do not like it

I've written an unofficial English editorial here: https://codeforces.com/blog/entry/80956

Hope it helps!

»
13 days ago, # |
  Vote: I like it +9 Vote: I do not like it

I think problem writers should read https://codeforces.com/blog/entry/75163 ...

  • »
    »
    13 days ago, # ^ |
    Rev. 2   Vote: I like it +19 Vote: I do not like it

    I think it's (partially) a difference in intended difficulty rather than problem-setting philosophy, Atcoder Beginner Contests feel as though A (and sometimes B) are designed to be solved by everybody, as long as they can write basic code. Whereas on a CF Div2/3, sometimes you don't even solve A or B since they have some tricky observation.

    In general, though, I agree (as I usually can solve Div2 A anyway), I also prefer when A and B have some interesting idea, and recent CF rounds have been really good about this! (And I think the blog post is valuable and worth reading.)

    • »
      »
      »
      13 days ago, # ^ |
      Rev. 7   Vote: I like it +16 Vote: I do not like it

      I think it is not about difficulty levels. Difficulty levels assume some difficulty.

      What is the point of such problems as today's A?

      If you look at the standings there is literally not a single person who tried to solve it (at least made a submission) and failed

      What is the point of a problem that cannot be failed by any participant?

      Moreover, interestingly, there is not a single person who solved only A. They either solve both A and something else or none. Which pretty much means that weak participants also don't think about this problem as existing and just start with more difficult ones to check whether they can solve it and see no reason to solve only A. Also, probably people who persistently can solve only A just don't visit such sites.

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Some participants submitted a wrong solution on A resulting in 5 minutes penalty. In my case that did not really matter, for hitonade it means position 9 instead of first place.

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

          Yes, penalties is pretty much the only way it affected the standings. But I don't think it justifies its existence

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        All of this is true, and I didn't think of it either.

        I was mostly annoyed that F, presumably what the problem writers thought was the most interesting problem, was just a google search for most people. E was a quick think 'okay apply binary search on answer' typing begins.

        The contest was not interesting for beginners, and therefore who was it interesting for lol???

»
13 days ago, # |
  Vote: I like it +14 Vote: I do not like it

Problem F just requires searching "Range Distinct Query". I know this is a Beginner contest so it's educational in nature, but maybe only E and F can be more carefully selected, since it's rated till a rather high bound.

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

    Very true, E and F were easy this time, I didnt solve F because I didn't know about Mo. But it seems like CF Educational round C, D to me.

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

      Educational Round never gives standard problems like F which requires 0 thinking.

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i tried it with mo , but got TLE (block size = 555), any help ?

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

Can someone help with E, I am getting wrong answer on 2 test cases.
Approach is binary search.My solution
UPD: Error found

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

    Maybe use a more reliable ceil function : ceil(a/b) is same as (a+b-1)//b where // stands for integer division

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for the suggestion but it was not a ceiling error. The error was because I took low=0.

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

I tried F using Mo's algo , but got TLE . This was similar to Dquery Spoj , But with higher constraints. Dquery

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

Someone please explain me problem C. How i can solve. What concepts were required.

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

Easiest Contest ever......

»
13 days ago, # |
  Vote: I like it +11 Vote: I do not like it

please upload the editorial in English, because peoples are participating from all over the world...

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

Can someone Plz tell me the process of solving c?I cant understand the google translated english of the editorial...

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    (Brute force) I just iterated over all 7, 77, 777,....(lrg value) and checked condition and got AC.

    7 -> 7+(7*10)->7+70+(7*100)......till 10^6 times , dont forget to take Mod k at each step

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

whats wrong in my approach in E ??```` int n,k; cin >> n >> k; int a[n]; cout << fixed << setprecision(10); multisets; for(int i=0;i<n;i++) { cin >> a[i]; s.insert(1.000000000 * a[i]); } //sort(a, a + n, greater()); for(int i=0;i<k;i++) { double x = *s.rbegin(); double a, b; a = x / 2; b = x / 2; auto itr = s.find(x); s.erase(itr); s.insert(a); s.insert(b); } cout << (int)*s.rbegin() << en;

»
13 days ago, # |
  Vote: I like it +11 Vote: I do not like it

Video solutions to all problems for people who are interested.

»
13 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Please provide english editorials

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

In E why we can't cut longest log in len/2 and len-len/2 two parts greedly and put them in priority queue.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also done the same way. but I am not able to figure out mistake

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

    That's actually what I implemented first -- luckily it got WA on the samples so I stopped and thought more.

    For a small counterexample, consider a single log of length 6 and $$$k=2$$$ cuts allowed. Our priority queue algorithm will cut into [3, 3] and then cut again into [3, 2, 1]. But it's possible to cut into [2, 2, 2].

    For a correct solution, see my English editorial.

    (But I encourage you to think about it more before looking, now that you know why the priority queue doesn't work.)

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for helping sir.Now i understood why priority queue will not work.

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

      Priority queue does work, see submission.

      The problem is that k can be 1e9 in which case it TLEs. Otherwise, it would run fine.

      • »
        »
        »
        »
        13 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Interesting. That looks more complicated than the simple greedy we discussed. Can you explain the algorithm?

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

          It is still greedy. Here, you store the number of cuts made too. Now when you make a new cut, you uniformly cut the whole log instead of the part you did.

          Implementation: Store total length, number of divisions and length of cut. Priority queue compares on basis of length of cut. When you get a new log, cut it into a unit more divisions.

          Taking your example, log is length 6, first cut cuts into [3,3] (storing as Log{total = 6, divisions = 1, length of cut = 3}) and second cut cuts into [2,2,2] (storing as Log{total = 6, divisions = 2, length of cut = 2}).

          • »
            »
            »
            »
            »
            »
            13 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Oh, that's very nice! Thanks for sharing.

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

i use BigInteger class in problem C but didn't get the answer. Can any body tell where i was doing wrong...

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is much to slow because this runs basically $$$O(n^2)$$$

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

Can someone help and explain me why this Solution gives TLE on problem F please? I'm using persistent segment tree

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

Guys can you suggest good resource for number theory for competitive. I found today's C very hard.

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

On Problem E, I got WA. After contest I check some test case in which I got WA. I got this one. 1 4784 450968417 and the answer is 94247. But If I cut the log with 94246.3 interval, I think it take exactly 4784 cut. So why 94246 is not the answer? Can anyone please help me? Sorry. I missed rounding 'Up' word.

»
13 days ago, # |
  Vote: I like it -8 Vote: I do not like it

we want more beginner contest in atcoder. At least 2 biggner contest in a week will be more interesting and enjoyable. we like the biggner contest problem in atcoder so, we want more contest!!!!!!!! i hope we will get more contest soon. and thank you guyes for organizing such a beautiful coding platform!

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

Can someone provide editorial for this in English?

»
13 days ago, # |
  Vote: I like it -26 Vote: I do not like it

chokudai Many people have just copy pasted the solution of F from this: https://www.geeksforgeeks.org/queries-number-distinct-elements-subarray/ Please look into this matter!!!

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

    Searching the web is allowed in the rules. See: AtCoder Rules

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

      Web searching is a different thing but the thing here is cheating, that is why there r so many people with AC

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

I was reading problem F many times to be sure. Because it was too standard and I was thinking it can't be asked.

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

    You haven't still got the worst thing about atcoder. They can do everything. Get an example.
    problem1 problem2
    These are pretty similar, well, fair enough. But, they don't even care to display new testcase.

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Those two problems have totally different solutions, and the samples being the same is probably a joke.

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it -11 Vote: I do not like it

        I needed to just modify the dp a little bit. Obviously these two are different problem. But, let's say someone googled the test cases during contest. That's taking them to the 1st problem. He opened the editorial. Now, he would easily get what's going on in the 2nd problem.

        • »
          »
          »
          »
          »
          12 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Who would google the testcases, during a contest? And then take the time to read the editorial of that other problem.

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

Apparently there's a solution to F for online queries and can even handle updates. It uses 2D range trees with fractional cascading:

https://stackoverflow.com/questions/39787455/is-it-possible-to-query-number-of-distinct-integers-in-a-range-in-olg-n

tl;dr; store 2d points of (currIndex, nextIndex) (default nextIndex is inf). Query the rectangle L <= currIndex <= R && R < nextIndex <= inf to count last occurrences in [L, R]

Can someone point me to a submission implementing it? (I'm mostly interested in the fractional cascading part to shave a log(n) factor)

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

I taught it will be interesting to see how I solved the C problem. I did it in a more complex way then others solutions. I try to make the last digit as a seven, check if the final product is all sevens, if it is not I repeat the process. https://atcoder.jp/contests/abc174/submissions/15630123

»
13 days ago, # |
  Vote: I like it -6 Vote: I do not like it

Can F be solved without specific algorithms and data structures?

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

Can anybody give a easy explanation in problem C as to why loop of i is only required till k and answer of number greater than k is not possible? But why

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe this can help

    • »
      »
      »
      12 days ago, # ^ |
      Rev. 7   Vote: I like it 0 Vote: I do not like it

      bro your explaination is good but i have some other doubt
      `void solve(){ int n;

      cin>>n;
      
      set<int> s;
      
      int x=7%n;
      int i=1;
      
      while(s.count(x)==0){
          if(x%n==0){
             cout<<i<<"\n";
             return;
          }
          s.insert(x);
          x=((x*10)+7)%n;
          i++;
      
      }
      cout<<-1<<"\n";
      

      }` this solution is acceptable but I saw one optimized approach using for(i=1;i<=n;i++) instead of while(s.count(x)==0) but i am not able to understand how is it acceptable.... please give some valid explaination after optimization code is —

      ``void solve(){

      int n;
      
      cin>>n;
      
      int x=7%n;
      
      
      
      for(int i=1;i<=n;i++)
      {
      
          if(x==0){
             cout<<i<<"\n";
             return;
          }
          x=((x*10)+7)%n;
      
      }
      cout<<-1<<"\n";
      

      } ``

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Simply If we mod x , n times there will be at least two same remainder (pigeonhole theorem) . Now in the first code we put remainder in the set and whenever we encounter a repeat in the set aka repeat in the remainder then its not possible (it has form a infinite loop and will never end in mod 0)

        In second code we just tried n times if there is not found mod 0 then it is sure that there will be repeatation of mod number so we break and print -1 (if we found mod 0 then we print number of step needed to get there)

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          but why is the answer guaranteed in less than n steps where n is the number which is given as input.
          for(int i=1;i<=n;i++) how within this loops answer is confirmed ...can you please explain using example

          • »
            »
            »
            »
            »
            »
            10 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            7 8 13 and we have N=3 if we mod 3 of them by N we get 1 2 1 It repeats , why? pigeonhole principle :there can be atmost N-1 mod numbers(boxes) but we have N mod number (pigeon) . So some mod number must be repeated .

            • »
              »
              »
              »
              »
              »
              »
              10 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Thanks that was a quite understandable explaination

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

If anyone need Detail explanation of C Here

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

Please, could anyone help me debugging this code? Thx!

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O2")
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
typedef long long ll;

int n, q, t[500005];
int c[500005];
int l, r;


int maxn(int s[],int m)
{
	int t;
	if (m==1)
	    return s[0];

	t=maxn(s,m-1);
    if (t>=s[m-1])
        return t;
    else
        return s[m-1];
}

int main()
{
	ios::sync_with_stdio(false);
        cin.tie(0);
	cout.tie(0);
	cin >> n >> q;
	t[0] = 0;
	c[0] = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> t[i];
		if (find(t, t + i, t[i]) == t + i) c[i] = c[i - 1] + 1;
		else c[i] = c[i - 1];
	}
	
//	for (int i = 1; i <= n; i++) cout << c[i] << ' ';
	for (int i = 1; i <= q; i++)
	{
		int no_use[500005];
		cin >> l >> r;
		if (l != r)
		{
			for (int j = l; j <= r; j++)
			no_use[j - l + 1] = c[j];
			cout << maxn(no_use, n) << endl; 	
		}
		else cout << 1 << endl;
	} 
	return 0;
}

PS.2AC, 4TLE, 1WA

another PS. I cannot speak English very well, and I can't speak Russian as well. So if some grammer errors exist, just omit it or tell me, thanks!

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is simpler to help if you link your submission instead of copy the code.

    Apart from int no_use[500005]; not beeing initialized that solution runs $$$O(n*q)$$$, which will TLE.

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

When will English editorial be published?

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

Can anyone help me with E-logs? Some people said its a simple binary search. I know binary search but even now I have no clue how it relates. It was my first contest. If anyone could link some articles or some similar problems, it will be very helpful. Thanks.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For E, try to imagine how the number of cuts is related to the maximum height of the chopped logs. If we have less k(suppose 0) then the answer will increase i.e the maximum height of the logs after chopping will be comparitively greater. If the number of cuts allowed is more(suppose 100000) then for a fix number of logs we can cut them more times than when cuts was 0, hence the maximum optimised length of any log will be less. Thus more the number of cuts, lesser will be the maximum length, when chopped optimally. Now, can you apply BS here? Sure you can :)

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

Till when the English editorial would be uploaded?

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

Can anybody help with question C of this contest?