Блог пользователя chokudai

Автор chokudai, 6 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +60
  • Проголосовать: не нравится

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +6 Проголосовать: не нравится

5 min left to start !

»
6 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится -30 Проголосовать: не нравится

40 seconds left.....

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +14 Проголосовать: не нравится

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

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

How solve F ??

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

How to do E?

  • »
    »
    6 лет назад, скрыть # ^ |
    ← Rev. 3  
    Проголосовать: нравится +11 Проголосовать: не нравится

    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

    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 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    just calculate the edit distance between A and B.

  • »
    »
    6 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +11 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +8 Проголосовать: не нравится

    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 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

How to solve C ??

I solved D but not C

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится

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

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +14 Проголосовать: не нравится

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 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

F — Segment tree Implementation

Can someone help find the mistake ?

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

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

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +11 Проголосовать: не нравится

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

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, скрыть # |
 
Проголосовать: нравится +16 Проголосовать: не нравится

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

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

can someone explain segment tree in PF?

»
6 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

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'| \lt |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 лет назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится

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 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

How to approach D problem? Help me, please!

  • »
    »
    6 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +8 Проголосовать: не нравится

    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 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

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.