chokudai's blog

By chokudai, 6 weeks ago, In English

We will hold AtCoder Beginner Contest 185.

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

We are looking forward to your participation!

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

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

5 min left to start !

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

40 seconds left.....

37...36...35.........can't write more.... :)

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

susah juga ya

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

Am I the only one who felt C and F were too classical problems? :/

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

    no

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

      Then, I think they should not include these kind of problems because they are just basic.

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

        Then, I think they should not include these kind of problems because they are just basic.

        Then you need to learn the basics.

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

          I mean what's the point if they are only giving problems whose solutions are already known to people? (They don't even need to think) They are pretty standard problems.

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

            I mean what's the point if they are only giving problems whose solutions are already known to people? They are pretty standard problems.

            Do you know all the solutions? If not then it is a good way to learn about the standard problems. It is already mentioned that this is a beginner contest and it is a great opportunity to apply those standard techniques. Then what is the problem?

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

              I'm not talking about all problems but three of them are(C,E,F) and I understand that this is a beginner contest but does that mean that you will give questions which are one google search far from the solution? And if yes, then there is no point of giving such contest because one can practice that stuff at Leetcode, GFG etc. also.

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

                E was a very good standard problem with a twist. Really a very good problem.

                C was good at its place. It needs basic DP or Combinatorics knowledge.

                You can say F was too standard and I also agree with that.

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

                  I can agree with you for E. But for C and F no way man!

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

    Not sure of C but F was for sure

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

    E and F were also classical common problems !!

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

    F was basically editing the merge function in my segment tree template

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

      Or maybe copying the exact same code from gfg ;_;

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

How solve F ??

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

    use segment tree with xor as merge operation of two segments.

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

    classic segment tree problem

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

    You can use Fenwick tree for range based queries. It's standard for range sum.

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

    It's literally this same one.

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

    Using binary indexed tree for each bit independently, you can check if the number of bits in the range from x to y are odd or not.

    Code

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

How to do E?

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

    Problem E can be solved using DP . Following is transition formula (based on if we want to pair index n with m or we want to discard index n or we want to discard index m) :

    transition

    dp[n][m] = min({solve(n-1,m-1)+((long long)(a[n]!=b[m])),solve(n,m-1)+1,solve(n-1,m)+1});

    where n is index of array a and m is index of array b . Base case is when n is equal to 0 or m is equal to 0 . If n=0 then we need to discard prefix of length m in array b .

    submission .

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

    just calculate the edit distance between A and B.

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

    It simply reduces to the classical Edit Distance problem. Try to prove it yourself.

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

    I use dynamic programming for solving E. Starting from the left if both elements are equal then you don't need to do anything otherwise do one of the three:
    1. remove element from first array.
    2. remove element from second array.
    3. don't remove any just count 1 as penalty for element being not equal.

    If reach at the end of any array remove remaining elements from the other array.

    ll solve(ll ar1[],ll ar2[],ll i,ll j,ll n,ll m) {
        if(i == n) {
            return m-j;
        }
        if(j == m) {
            return n-i;
        }
        if(dp[i][j] != -1ll)
            return dp[i][j];
        if(ar1[i] == ar2[j]) {
            return dp[i][j] = solve(ar1,ar2,i+1,j+1,n,m);
        }
        return dp[i][j] = min({solve(ar1,ar2,i+1,j,n,m),solve(ar1,ar2,i,j+1,n,m),solve(ar1,ar2,i+1,j+1,n,m)}) + 1;
    }
    
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C ??

I solved D but not C

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

Does anybody know how to solve the E question? I tried longest common subsequence approach but got WA.

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

Here's an unofficial editorial .

Problem A : Just take the min of given 4 values

Problem B : Just take the difference of consecutive numbers and alternatively subtract and add. Code

Problem C : One of the simple solution is DP.

Let dp(x,y) is number of ways to cut x, into y pieces then our required result is dp(l,12);

The recurrence is

dp(x,y) = dp(x-1,y) + dp(x-1,y-1); // you cut a piece of 1 from prefix or you don't cut

The base cases

if(x==y) dp(x,y) = 1; // all pieces of 1
if(x<y) dp(x,y) = 0; // you can't have cuts
if(y==1) dp(x,y) = 1; // don't cut anywhere 

Code

Problem D : Sort the given array A, if the first element is not 1, or last is not n, append them.

Store the differences between consecutive elements in a vector. 
Pick the smallest as k, and now to paint a length l, you need l/k + (if(l%k!=0)?1:0)

Code

Problem E : This was just a simple variaton of standard LCS.

If we denote dp(x,y) = result for the suffix A[x..n-1] and B[y..m-1] assuming 0 based indexing 
then our required result is dp(0,0)

The recurrence is 
dp(x,y) = min(dp(x+1,y),dp(x,y+1)) + 1;  // delete in A or B
if(a[x] == b[y]) dp(x,y) = min(dp(x,y),dp(x+1,y+1)); // keep both
else dp(x,y) = min(dp(x,y),dp(x+1,y+1)+1); // keep both as a mismatch 

Also, the base case , 
if(x==n or y==m){
	dp(x,y) = (m+n)-(x+y); // if only one array has elements left, you have delete all 
}

Code

Problem F : That's just a standard segment tree with point update queries. Code

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

    C is also l - 1 choose 11 because we have l - 1 choices and have to select 11.

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

    Main problem in E is to get your head arround what the problem statement asks for.

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

    it should be obvious to many, but if someone feel confused by, dp(x,y) = dp(x-1,y) + dp(x-1,y-1); you cut a piece of 1 from prefix or you don't cut

    read this, just ordered the expression as in text

    dp(x,y) = dp(x-1,y-1)+ dp(x-1,y) ; you cut a piece of 1 from prefix or you don't cut

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

    For Problem D, I binary searched over [0, 10^9] to find the maximum stamp width, so as to get the minimum possible operations; but this solution got 'WA' for 14 test cases. Can't find the possible error, any help would be really appreciated.

    Code link- https://atcoder.jp/contests/abc185/submissions/18899870

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

somebody tell me how to solve B. as i m beginner .

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

    Just do what the problem says.

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

      Just do what the problem says.

      ... and check after each step if c<=0.

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

        and see that capacity cannot be more than the maximum capacity

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

    For every cafe calculate time taken from the last cafe and subtract if from n. If n<=0 at any stage we know there's not enough mah left. Also after cafe add (end time-start time) for charging. Also consider special cases like first cafe and last cafe.

    code
    n,m,t = map(int,input().split())
    bank = n
    prev = 0
    flag = 1
    for i in range(m):
        a,b = map(int,input().split())
        bank -= (a-prev)
        if bank<=0:
            flag = 0
        bank += (b-a)
        bank = min(n,bank)
        prev = b
    bank -= (t - b)
    if flag:
        if bank<=0:
            print("No")
        else:
            print("Yes")
    else:
        print("No")
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved A,B,D,E,F but was not able to solve C. Any hint would be appreciated.

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

Can we solve problem F using SQRT decomposition? , although I solved using seg tree, still can we solve it?

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

    With segment tree it is O(nlogn), with SQRT aka Mo it is O(n sqrt(n)), which is more, but still could fit the timebox.

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

This is my code for problem B but it was wrong for few test cases can anybody help me out

include <bits/stdc++.h>

using namespace std; int main(){ #ifndef ONLINE_JUDGE freopen("input.text", "r", stdin); freopen("output.text", "w", stdout); #endif int n,m,t; cin>>n>>m>>t; int item = 0; for ( int i = 1; i<=m*2; i++){ int ele; cin>>ele; if ( i%2 == 0){ n = n + ( ele — item)*2; } else{ n = n — ( ele — item)*2; } if ( n<0){ n = 0; } item = ele;

    }
    n = n-(t-ele)*2;
    if ( n <= 0){
       cout<<"No";

    }
    else{
       cout<<"Yes";
    }
return 0;

}

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

F — Segment tree Implementation

Can someone help find the mistake ?

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

Approach to problem F: goto geeksforgeeks, copy the solution , edith for input and submit. Wooooow, you solve a problem with 600 point. Fuck.........

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

In problem B, the statement was not clear to me although I solved it after looking at the examples. It said that "Determine whether he can return home without the battery charge dropping to 0 on the way.", so it meant that we have to determine battery charge dropping to 0 when he was on his way home after visiting M cafes?

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

    There are two possible interpretions: Drop to 0 at any point of time, or in the end. So that is what the examples for, we have to interpret them if not sure.

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

How to solve E using LCS? My logic is given below

common_elements = lcs(arr, brr, n, m); [calculate number of common elements using LCS]

y = min(n, m) — common_elements; [number of elements in the array which are not equal arr[i] != brr[i]]

x = max(n, m) — min(n, m); [numbers you have to delete to keep the length of both arrays same]

mySolution

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

    For the test case :

    5 5
    1 0 9 2 4
    1 2 8 7 4
    

    According to the question, X would be 0 and Y would be 3. Your code would return 2 whereas the answer should be 3 or am I wrong in understanding this...?

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

I couldn't find the bug in my implementation of segment-tree for F. Please help. Code

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

    I think you have not read the question properly. For every 1 type query, you have to replace a[x-1] with a[x-1]^y, not with y

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

      I did so inside my update function. Inside the else if block Where I updated the tree node as
      t[node]=combine(t[node],val);

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

        finally found the bug. In update you have called left node both times.It should be right in second call

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

My solutions to this contest, along with detailed explanations of the solutions, can be found here :)

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

is there any way to get editorial of this contest as i am not able to solve 3 question and i want a editorial for it is there a way.

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

I have written an unofficial English editorial.you can find it here..

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

can someone explain segment tree in PF?

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

    it is a basic problem of segment tree , xor on segment tree if you ever use segment tree then its ok and if not then go to codeforces edu and watch some video of segment tree in segment tree section after watching it there is a problem of sum on segment tree if you can understand that then you can easily solve that problem, in that problem you have to do some update and queries. and by creating a segment tree you can solve it in O(nlogn). you can see the solution here : https://atcoder.jp/contests/abc185/submissions/18787613 and if it not clear then send a message.

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

Can anybode see what is wrong with my code?

My idea is to first swap the two array to make array $$$a$$$ has less or the same amount of numbers than array $$$b$$$. I observe that it is optimal to not deleting any number from array $$$a$$$, since if $$$|A'|<|A|$$$, we can add a number to the end of each of array $$$a$$$ and $$$b$$$ and $$$x$$$ will decrease by $$$2$$$ while $$$y$$$ will only increase by at most $$$1$$$. Then, I use DP, for which $$$dp[i][j]$$$ is the minimum value of $$$x+y$$$ when we only consider the first $$$i$$$ value of array $$$b$$$ and the first $$$j$$$ value of array $$$a$$$. The answer is $$$dp[m][n]$$$.

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

    Check this test:

    4 3
    1 1 2 3
    2 3 1
    

    It's better to delete $$$A_1$$$, $$$A_2$$$ and $$$B_3$$$ with cost = 3. Your code prints 4.

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

      Got it. Thanks!

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

      I also have a similar kind of problem. Could you please help.

      Code Link

      I understood from your test case, that what I was doing wrong. But, can we not iterate over all the "subsequence sizes", and fix it ?

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

Just my feedback I think this round was way easier than general. Actually the difficulty of all A-F in this round should actually be A-D, and E, F need to be a bit challenging, requiring more thinking for beginners to be challenged. D was also quite easier more like B. Thank you!

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

Can someone help me with this solution of D https://atcoder.jp/contests/abc185/submissions/18768487 ?

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

How to approach D problem? Help me, please!

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

    The idea is that we want to use the biggest k possible, because then we need to use the stamp the minimum number of times.

    On the other hand, k must not be bigger than the smallest consecutive segments of blue cells, because if it is bigger, then we cannot use the stamp on that segment.

    So we choose k as the number of cells in the smallest such segment, and then count foreach segment how often we need to use the stamp.

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

      I got It. Thanks a lot, Mr. SpookyWooky ... God bless you!

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

Hey guys I made a screencast of this contest and also explained the solutions of all the problems except E. You can find that here :https://www.youtube.com/watch?v=ViFutg-bZJM

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

D was a very lame problem.

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

Would anyone be able to find the problem in my code for the segment tree in F? My implementation

It is being accepted on samples but failing in randomized tests. Thanks

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

    You forgot to update arr after 1st type of operation. Just add arr[x-1] ^= y; after updateTree and you'll get AC.

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

      Shouldn't I just be updating my segment tree array tree with the update query? It's being updated at - tree[ind] = val in one of the updateTree cases. Moreover, val ,that I passed was equal to arr[x-1]^y Shouldn't that be enough? Thanks for looking into it...

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

        Consider two update queries for the same index x. You pass arr[x-1]^y, but then never update arr[x-1], so in the next update query with this index, you will XOR with the initial value itself.

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

If anyone is interested, I streamed my virtual participation & explained the solutions after, you can find the upload here: https://youtu.be/PLIm4jYYaHk

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

Why can I post the editorial? Is it a bug or a feature?

I was curious about the "post editorial" button and tried to write one, but it somehow appeared where the official editorial should be.

Should I delete it?

Upd: It seems that all users with a rating more than 2000 have the access.

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

Hi, Why in problem E — sequence matching, the answer = abs(n-m) + min(n,m) — lcs(n,m) isn't correct? lcs(n,m) — longest common sequence of a and b. For example: a = (1, 3, 2, 4), b = (1 5 2 6 4 3). ans = 2 + 4 — 3 = 3. lcs(n,m) = (1 2 4).