AtCoder Beginner Contest 185 Announcement

3 года назад, # |

+14

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

→ Ответить

_-pratik_shukla-_

3 года назад, # ^ |

→ Ответить

3 года назад, # ^ |

← Rev. 2 →

+10

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

→ Ответить

www.___.com

3 года назад, # ^ |

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

Then you need to learn the basics.

→ Ответить

3 года назад, # ^ |

← Rev. 2 →

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.

→ Ответить

www.___.com

3 года назад, # ^ |

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?

→ Ответить

3 года назад, # ^ |

← Rev. 2 →

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.

→ Ответить

www.___.com

3 года назад, # ^ |

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.

→ Ответить

Makise_Kurisu

3 года назад, # ^ |

Not sure of C but F was for sure

→ Ответить

Dan4Life

3 года назад, # ^ |

+14

C was a standard combinatorics problem

→ Ответить

hackerbhaiya

3 года назад, # ^ |

E and F were also classical common problems !!

→ Ответить

sharath101

3 года назад, # ^ |

+13

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

→ Ответить

nagaraj41

3 года назад, # ^ |

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

→ Ответить

Lazarusx2

3 года назад, # |

How solve F ??

→ Ответить

vineetjai

3 года назад, # ^ |

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

→ Ответить

Makise_Kurisu

3 года назад, # ^ |

classic segment tree problem

→ Ответить

ashu12_chi

3 года назад, # ^ |

+23

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

→ Ответить

dush1729

3 года назад, # ^ |

← Rev. 2 →

-9

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.

→ Ответить

vineetjai

3 года назад, # |

How to do E?

→ Ответить

rananjay23

3 года назад, # ^ |

← 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 .

→ Ответить

qqwrwwv

3 года назад, # ^ |

just calculate the edit distance between A and B.

→ Ответить

_Enigma__

3 года назад, # ^ |

+11

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

→ Ответить

ashu12_chi

3 года назад, # ^ |

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;
}

→ Ответить

palindroam

3 года назад, # ^ |

Thanks for explanation !!

→ Ответить

Sanju_250406

3 года назад, # |

How to solve C ??

I solved D but not C

→ Ответить

upcoming_Expert_in_2021

3 года назад, # ^ |

nCr(n-1,11)

→ Ответить

naturell

3 года назад, # ^ |

Used this formula, but passed only 10/ 16 Test Cases:/

Where am I going wrong? https://atcoder.jp/contests/abc185/submissions/18756020

Appreciate the help.

→ Ответить

NM_Mehedy

3 года назад, # ^ |

naturell

Check this out

ll nCr(ll n , ll r) {

if(n<r)return 0;
if(n==r)return 1;

ll ans=1;
for(ll k=n,p=1;k>(n-r);k--)
{
    ans *= k;
    if(p<=r)
    {
        ans/=p;
        p++;
    }
}
return ans;

}

→ Ответить

lone_star

3 года назад, # |

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

→ Ответить

Suri429

3 года назад, # |

+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

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)

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 
}

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

→ Ответить

dush1729

3 года назад, # ^ |

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

→ Ответить

3 года назад, # ^ |

+14

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

→ Ответить

forcdc

3 года назад, # ^ |

← Rev. 2 →

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

→ Ответить

MARSHALMATHERS

3 года назад, # |

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

→ Ответить

3 года назад, # ^ |

← Rev. 2 →

Just do what the problem says.

→ Ответить

3 года назад, # ^ |

Just do what the problem says.

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

→ Ответить

_whysonew_

3 года назад, # ^ |

and see that capacity cannot be more than the maximum capacity

→ Ответить

Finding_Infinity

3 года назад, # |

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

→ Ответить

Nuwaisir_Rabi

3 года назад, # ^ |

Combinatorics

→ Ответить

RD_TheCoder

3 года назад, # ^ |

I know answer is (n-1)c11 but n! getting overflow..please help.

→ Ответить

FatihSolak

3 года назад, # ^ |

← Rev. 2 →

Check this

→ Ответить

Nuwaisir_Rabi

3 года назад, # ^ |

There is a dynamic programming approach to find the values of $$$n \choose r$$$. The recursive formula is: $$$\binom{n}{r} = \binom{n-1}{r} + \binom{n-1}{r-1}$$$

→ Ответить

RD_TheCoder

3 года назад, # ^ |

can i get the code..please sir

→ Ответить

Nuwaisir_Rabi

3 года назад, # ^ |

It's pretty common. Just google it :)

→ Ответить

Cloud_

3 года назад, # ^ |

Calculate nCr using dp.

→ Ответить

swapnilr

3 года назад, # ^ |

Use __int128 — https://atcoder.jp/contests/abc185/submissions/18738450

→ Ответить

hetp111

3 года назад, # ^ |

← Rev. 2 →

One loop, No __int128: https://atcoder.jp/contests/abc185/submissions/18740485

→ Ответить

rananjay23

3 года назад, # ^ |

You can use dp of 12*200 states where dp[i][j] means ith cut at jth position .

submission

→ Ответить

PR007

3 года назад, # ^ |

it is just simple dp, you can either make a cut at the position you are at or not make a cut, when u have 11 cuts just check if it has made 12 valid cuts and there you go!

→ Ответить

3 года назад, # ^ |

You can type the star and bars formular from head or implement some more or less simple dp. I tried to google the formular but without success then implemented the dp.

→ Ответить

sudipandatta

3 года назад, # ^ |

Number of ways to choose 11 from (L-1). Simple combinatorics.

→ Ответить

FatihSolak

3 года назад, # ^ |

Basic combinatoric problem just be careful about overflows you need to divide numbers while you are able to have integer result when calculating nCr

→ Ответить

hackerbhaiya

3 года назад, # ^ |

ans is l-1C11. We have total l-1 positions to place bar in which we have to choose only 11 of them.

→ Ответить

Yatin_Kwatra

3 года назад, # ^ |

← Rev. 3 →

If there is a rod of length L, we have 0,1,2,3,....,N-1,N positions on rod. So in total we have (n+1) points, but we can't make a cut at the extreme ends, so we just have to choose 11 points from the remaining (n-1) points, so answer is simply (n-1)Cr .

In order to avoid the overflow, I divided the numerator and denominator with their gcd in every iteration.

Spoiler

int ans = 1;
int deno = 1;
fo(i, 1, 11) deno *= i;

rfo(i, n, n - 10)
{
    ans *= i;
    int g = __gcd(ans, deno);
    ans /= g;
    deno /= g;
}

→ Ответить

Finding_Infinity

3 года назад, # ^ |

Infact I tried dp but my transitions were wrong

→ Ответить

chandanagrawal23

3 года назад, # |

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

→ Ответить

3 года назад, # ^ |

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.

→ Ответить

hetp111

3 года назад, # |

F — Segment tree Implementation

Can someone help find the mistake ?

→ Ответить

cjlworld

3 года назад, # ^ |

← Rev. 12 →

if(S<=s && E>=e)return tree[id];

not

if(S>=s && E<=e)return tree[id];

here

→ Ответить

_RAYUGA_

3 года назад, # |

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

→ Ответить

wingman__7

3 года назад, # |

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?

→ Ответить

3 года назад, # ^ |

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.

→ Ответить

wingman__7

3 года назад, # |

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

→ Ответить

xDxDxDxDLoL

3 года назад, # ^ |

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...?

→ Ответить

Nieb_Hasan_077

3 года назад, # |

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

→ Ответить

_whysonew_

3 года назад, # ^ |

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

→ Ответить

Nieb_Hasan_077

3 года назад, # ^ |

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);

→ Ответить

_whysonew_

3 года назад, # ^ |

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

→ Ответить

Nieb_Hasan_077

3 года назад, # ^ |

thanks a lot brother.

→ Ответить

ScarletS

3 года назад, # |

← Rev. 2 →

+11

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

→ Ответить

Storm_Breaker007

3 года назад, # |

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.

→ Ответить

C137

3 года назад, # ^ |

Check this.

→ Ответить

C137

3 года назад, # |

+16

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

→ Ответить

Storm_Breaker007

3 года назад, # ^ |

thnks bro

→ Ответить

guagua0407

3 года назад, # |

can someone explain segment tree in PF?

→ Ответить

ld_minh4354

3 года назад, # |

← Rev. 2 →

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]$$$.

→ Ответить

C137

3 года назад, # ^ |

← Rev. 2 →

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.

→ Ответить

ld_minh4354

3 года назад, # ^ |

Got it. Thanks!

→ Ответить

ritesh1340

3 года назад, # ^ |

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 ?

→ Ответить

lemongrab

3 года назад, # |

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!

→ Ответить

SevenDeadlySins

3 года назад, # |

← Rev. 3 →

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

→ Ответить

CodeTyper

3 года назад, # |

How to approach D problem? Help me, please!

→ Ответить