AtCoder Beginner Contest 165 Announcement

5 years ago, # ^ |

+11

Yep

→ Reply

wingman__7

5 years ago, # |

website crashed ?

→ Reply

sayanmedya

5 years ago, # ^ |

Delayed by 10 minutes.

→ Reply

rocww

5 years ago, # |

site is not loading?

→ Reply

zxcv890

5 years ago, # |

RIP

→ Reply

badriisurmi

5 years ago, # |

Site down?

→ Reply

-emli-

5 years ago, # |

Again 502 Bad Gateway :(

→ Reply

living_in_genjutsu

5 years ago, # ^ |

It's up now

→ Reply

LastThread

5 years ago, # |

504 Gateway Time-out:(

→ Reply

5 years ago, # |

Postponed for 5 minutes.

→ Reply

5 years ago, # ^ |

Now ten minutes.

→ Reply

5 years ago, # |

Start time extended by 10 minutes.

→ Reply

5 years ago, # ^ |

Its good that they acted quickly otherwise this contest also could be unrated :D

→ Reply

_ansh_

5 years ago, # |

← Rev. 2 →

extended by more 5 min :(

→ Reply

PRESS_F_2_PAY_RESPECT

5 years ago, # ^ |

10 mins.

→ Reply

Agnimandur

5 years ago, # |

Will they just postpone the contest by increments of 5 minutes until enough people go away and there is less load on their servers??

→ Reply

pigeon_hole

5 years ago, # |

-9

delayed due to inadequacy in problem

→ Reply

5 years ago, # |

“The start will be delayed for 10 minutes due to an inadequacy discovered in the problem. I'm sorry.“

→ Reply

5 years ago, # |

Here we go

→ Reply

younoknowme

5 years ago, # |

-6

C is too hard for C, imo.

→ Reply

-emli-

5 years ago, # ^ |

easy

→ Reply

younoknowme

5 years ago, # ^ |

yeah, for me it was hard :(

→ Reply

tfr

5 years ago, # ^ |

Solved E, but didn't C...

→ Reply

s_hertelli

5 years ago, # ^ |

10! algorithm would work

take a look at the constraints

→ Reply

Induber

5 years ago, # ^ |

← Rev. 3 →

it would be (n+m-1)C(m-1), so worst case 19C10

→ Reply

Sakhiya07

5 years ago, # ^ |

How could you get this formula?I saw same question in one educational round but i don't know proof behind this formula?

→ Reply

2022OVO

5 years ago, # ^ |

← Rev. 2 →

there's a n*m size rectangle, at the beginning, you are at the bottom-left corner, now that formula is the number of ways to get to the right side of the rectangle only go right or top.

→ Reply

Induber

5 years ago, # ^ |

← Rev. 2 →

You have M distinct numbers you can give each number some frequency and frequency of each number can be between [0, N] (N = length of sequence), since you have to make sequence increasing so for any fix combination of numbers and frequencies there will be only one increasing sequence. So now the problem is reduced to find the number of solutions of equation f1+f2+f3+..+fm = N, where fi is frequency of ith number in the sequence.

→ Reply

vipinkumar17

5 years ago, # ^ |

← Rev. 5 →

total sequences are 92378 in worst case. C(19,10)=92378

→ Reply

ay2306

5 years ago, # ^ |

Solved F but not C and E.

→ Reply

rupav

5 years ago, # ^ |

+10

same. F was easy, if you know O(nlogn) solution for finding LIS.

→ Reply

jam1729

5 years ago, # ^ |

I tried solving F using coordinate compression and range-max segment tree. But i kept getting WA :( . Been trying to figure out the error, but I wasn't able to. Here is my submission WA solution

→ Reply

steinum

5 years ago, # ^ |

It also happened to me.

lets denote some variable: max_val=maximum compressed value

prev_val=query(pos[u],pos[u])[value of the index of pos[u] , before line 45]

1) in line 45:

update(pos[u], val) -> update(pos[u],max(val,prev_val))

2) in line 46:

ans[u] = val -> ans[u] = query(0,max_val)

3) in line 52:

update(pos[u], 0) -> update(pos[u],prev_val)

I suppose this works fine...

→ Reply

jam1729

5 years ago, # ^ |

+11

Thanks a lot. Realized that for considering the LIS for a path from 1 to k, I take the answer as dp(k), instead of max(dp(i)) for i from 1 to k.

→ Reply

keep__calm

5 years ago, # ^ |

+1. Solved rest but couldnt do this.

→ Reply

dush1729

5 years ago, # ^ |

It was too hard for me too. I thought number of combinations will be too large. But turns out there can be at max 92378 for n=10 and m=10. So brute force works.

→ Reply

towhid1zaman

5 years ago, # |

How to solve C !

→ Reply

5 years ago, # ^ |

just try all the state.

→ Reply

5 years ago, # ^ |

Though I doubted whether it will get TLE in the beginning...

→ Reply

5 years ago, # ^ |

How does this work, I came to the conclusion that there are $$$10^{10}/2$$$ possible arrays to check. To much.

→ Reply

5 years ago, # ^ |

No you are wrong ,There are much fewer arrays!! You can write a dfs to count them.

→ Reply

5 years ago, # ^ |

There are 92378 possible arrays for N = 10, M = 10 that have A[i]>=A[i-1] only.

→ Reply

5 years ago, # ^ |

Well, thanks for explanation.

→ Reply

_ansh_

5 years ago, # ^ |

how did you got this ?

→ Reply

5 years ago, # ^ |

Either go with a brute solution and find using code or use P&C and we can say sum of gaps between consecutive numbers is at max m-1 and number of gaps are n-1, so g1+g2+g3... gn-1 + k = m-1, so number of whole number solutions of this equation are m-1+n-1Cn-1

→ Reply

MasterMind

5 years ago, # ^ |

actually the number of array is 10 choose 10 with repetition so that means it is 19 choose 10 which is equal to 92378. I have solved it in the most crazy way. my submission

→ Reply

_Shubho_

5 years ago, # ^ |

I did'nt get it... how is it becoming 19C10?

→ Reply

MasterMind

5 years ago, # ^ |

It is a well known concept called combination with replacement. Imagine you have a pool of numbers from $$$1 - 10$$$, and you want to select $$$10$$$ numbers with replacement (ex you can take the same number multiple times) this can be found using $$$n+k-1 \choose k$$$. If you want to read more about [here](https://en.m.wikipedia.org/wiki/Stars_and_bars_(combinatorics))

→ Reply

MasterMind

5 years ago, # ^ |

Correction: it is $$$n + k - 1 \choose n$$$ which equal to $$$n + k - 1 \choose k - 1$$$

→ Reply

pigeon_hole

5 years ago, # ^ |

we should only consider monotonically increasing sequence

→ Reply

gupta_samarth

5 years ago, # ^ |

+26

Combinatorial way to look at it.

You need to find number of arrays $$$A = \{ A_1, A_2, ..., A_N \} $$$, such that $$$ 1 \le A_1 \le A_2 \le ... \le A_N \le M $$$.

Let $$$ x_i $$$ be the number of occurences of $$$ i $$$ in the array. Then we require number of solutions to $$$ x_1 + x_2 + ... + x_M = N $$$, where $$$ x_i \ge 0 $$$.

This, given by Stars and Bars, is simply $$$ {N+M-1} \choose {M-1} $$$ = $$$ {10+10-1} \choose {10-1} $$$ = $$$ 19 \choose 9 $$$ = $$$92378$$$.

I usually use this website to do quick calculations for combinations, during contests.

→ Reply

Chodermal1

5 years ago, # ^ |

← Rev. 2 →

→ Reply

hetp111

5 years ago, # ^ |

Backtracking

→ Reply

towhid1zaman

5 years ago, # ^ |

would you plese explain!

→ Reply

hetp111

5 years ago, # ^ |

← Rev. 2 →

Look at my code you'll get it: https://atcoder.jp/contests/abc165/submissions/12619964

basically we generated all possible arrays.

→ Reply

ritik_patel05

5 years ago, # ^ |

You can write a recursive brute force, which will include all possible states we can go to.

Consider we want to fill n places. We start from place_id = 1, and num = 1.

Now we have 3 possible cases:

Don't include the current number at this place, so increment the 'num' by +1.
Include the number so now we need to fill next place, so increment 'place_id' by +1 and continue using the same number for further positions.
Include the number at the current position, but we don't want to use the same number for next pos, so increment both 'place_id' and 'num' by +1.

If you are confused, you can take a look at my submission, though it isn't the cleanest. Submission

I hope it helped.

→ Reply

5 years ago, # |

-11

Honestly, I think it is not very wise to give such C and D in abc contest.

I am sure there a thousends(?) of possible participants not submitting any solution because scared by a hard C and a D full of corner cases.

Dont get me wrong, I think these are nice problems, but simply misplaced.

→ Reply

5 years ago, # ^ |

I can solve D by math with no corner cases. https://atcoder.jp/contests/abc165/submissions/12609383 Can not solve C. E. F.

→ Reply

younoknowme

5 years ago, # ^ |

D was just to take x as min(b-1,n).

→ Reply

5 years ago, # ^ |

← Rev. 2 →

F was easy with segment tree i think

→ Reply

5 years ago, # ^ |

Are you serious ?Why you used segment tree for E?

→ Reply

5 years ago, # ^ |

sorry my bad, F

→ Reply

bad__guy

5 years ago, # ^ |

← Rev. 2 →

I think F by set will be more easy

check that

vector < int > v[200005];

int a[200005],ans[200005];

bool vis[200005];

set < int > s;

void dfs (int r )

{

vis[r]=true;

int cc=-1,ff=-1;

set<int>::iterator it;

if (s.insert(a[r]).second) 
{ 

    it= s.find(a[r]); 

    it++;

    if (it!=s.end())
    {

        ff=*it;

         s.erase(it); 
    }

    cc=a[r];
}

 ans[r]=sz(s);

for(auto i : v[r])
    if(!vis[i])
    {
        dfs(i);
    }

if(cc!=-1)
{

    s.erase(s.find(cc));

    if(ff!=-1)
        s.insert(ff);
}

}

→ Reply

towhid1zaman

5 years ago, # ^ |

Would you please simulate your math formula!

→ Reply

rupav

5 years ago, # ^ |

you need to maximize, but if you observe for any x >= b, float[x/b] will always be greater than 0, and then you multiply it with A, but float[Ax/b] can atmost be equal to that. Thus its always optimal to make float[x/b] = 0, so that you answer is float[Ax/b]. To make that equal to 0, just take max x < b, but since x <= N, x = min(n, b-1). Then return the answer.

→ Reply

5 years ago, # ^ |

Explanation for D; If x increased by B, value not change, so we only consider x in range 0 — min(b-1,n); So The second part of the function becomes zero and the first part becomes maximum.

→ Reply

5 years ago, # ^ |

Is C very hard?just try all the state!

→ Reply

5 years ago, # ^ |

I thought about that, just can not believe it will not get TLE. Maybe I evaluate time complexity wrong.

→ Reply

5 years ago, # ^ |

Why not write a simple dfs to count the number of them?

→ Reply

5 years ago, # ^ |

I calculated Combination(20, 10), and ... What the fxxx was I thinking about!!!

→ Reply

5 years ago, # ^ |

Is it $$$C_{m+n-1}^n$$$ ?

→ Reply

5 years ago, # ^ |

Yes, you are right. I do not know how to input formula.

→ Reply

aj54

5 years ago, # |

The English Commentary for Problem C and D is here

→ Reply

5 years ago, # ^ |

← Rev. 2 →

D with binary search... Wait. what? How? What does your check function do? The function isn't strictly increasing nor decreasing as far as I understand..

→ Reply

pigeon_hole

5 years ago, # ^ |

it's not increasing nor decreasing... however if you notice function is increasing in intervals of b. eg. from x = 0,1,2,..b — 1 f(x) is increasing at x = b f(x) again drops and starts increasing same as for previous x

→ Reply

https://atcoder.jp/contests/abc165/submissions/12647186

5 years ago, # ^ |

Exactly, since it drops at B, you can't binary search on interval (0,n). If you are Bsearching on interval (0,B-1), that isn't required, since it is increasing from 0 to B-1...so B-1 is going to give you maximum.

Also, I am not sure if this Bsearch on (O,N) will work always. Since it is repeating maybe that is why it worked.

→ Reply

leetcode07

5 years ago, # ^ |

← Rev. 2 →

Please provide proof of your construction in D

→ Reply

Imperial_Lord

5 years ago, # ^ |

The best idea is to use min(b-1,n). Simple and cute!

→ Reply

sasuke4981

5 years ago, # |

Can someone give a hint on E and F?

→ Reply

dush1729

5 years ago, # ^ |

← Rev. 2 →

For F, Use Cute LIS :P to find lis for every node in dfs. My Submission.

→ Reply

zxcv890

5 years ago, # |

Why is my ternary search failing on one test case for D? :((

→ Reply

ErasedSoul

5 years ago, # ^ |

Why you are using ternary search ... Its just simple math

→ Reply

zxcv890

5 years ago, # ^ |

← Rev. 2 →

I just assumed the function was unimodal and tried ternary search and it almost AC'd. Can you elaborate your solution?

EDIT: unimodal not monotonic

→ Reply

5 years ago, # ^ |

The function is repeating after every B values of X.

Try to express X = qB + r and solve the equation. You will find that, function is max when r = (B-1). Also, in case, b — 1 > N, then N is your answer cause, from 0 to B-1 the answer is increasing.

→ Reply

5 years ago, # ^ |

← Rev. 2 →

No need for ternary search, answer is monotonic with modulo value with B.

→ Reply

5 years ago, # ^ |

When you know it is monotonic between 0 to B-1, when not just return B-1...

→ Reply

MahinChowdhury

5 years ago, # |

Problem statement of C was so confusing.Can anyone explain it?

→ Reply

5 years ago, # ^ |

← Rev. 2 →

You are asked to create an array a, of size N. You should place values in that array from 1 up to M. The array should be not decreasing.

Then you get those quadrupels. If you put at position a and b values, so that the difference is c, you get d points.

Try to find an array with maximum possible points.

→ Reply

-trash123

5 years ago, # |

How to solve F ?

→ Reply

yashbansal4953

5 years ago, # ^ |

Apply the O(nlogn) algorithm for LIS during the dfs while nullifying the changes made by a particular branch of a node when we visit its another branch.

→ Reply

5 years ago, # ^ |

I maintained a segment tree for current root to node path for lis, and as i move down i make updates like in normal lis, and as i move up, i roll-back on the changes i did previously.

→ Reply

AM_I_Learning

5 years ago, # ^ |

With segment trees and coordinate compression was required I think to backtrack.

→ Reply

abhishek_saini

5 years ago, # |

+26

All the people complaining about C being too hard. Is it possible that they didn't notice the constraints that array is in increasing order A[1] <= A[2] <= A[3]..... <= A[N]? Because I skipped it initially and thought for several minutes that total case are $$$10^{10}$$$ which was outside the time limit.

→ Reply

hetp111

5 years ago, # ^ |

← Rev. 2 →

Same happened with me. How many possible combinations are possible ?

a1 <= a2 <= ... <= an , (1<=ai<=m)

Solved it, but I couldn't prove the time complexity.

→ Reply

mip182

5 years ago, # ^ |

+21

Observe, that if you pick set of numbers, there can be only one possible array, so you just need to count number to choose n elements from 1 to m, it is exactly $$$\binom{n+m-1}{n}\le 92378$$$

→ Reply

indiewar

5 years ago, # ^ |

There is a small mistake. I think the time complexity should be $$$C_{n+m-1}^{m-1}$$$.

→ Reply

mip182

5 years ago, # ^ |

It's actually the same because $$$\binom{n}{k}=\binom{n}{n-k}$$$

→ Reply

indiewar

5 years ago, # ^ |

I'm sorry. It's my mistake. I didn’t think twice. So stupid.

→ Reply

5 years ago, # ^ |

-10

And... is 10^10 not outside the time limit?

→ Reply

Not-Afraid

5 years ago, # ^ |

First i wrote a dp solution to count how many such arrays exists. Then used brute force.

Spoiler

#include <bits/stdc++.h>

using namespace std;

int dp[11][11];

int go(int id, int last) {
  if (id == 10) return 1;
  if (~dp[id][last]) {
    return dp[id][last];
  }
  int ans = 0;
  for (int i = last; i <= 10; ++i) {
    ans += go(id + 1, i);
  }
  return dp[id][last] = ans;
}

signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  memset(dp, -1,sizeof dp);
  cout << go(0, 1);

  return 0;
}

→ Reply

5 years ago, # ^ |

In fact there are only $$$C_{m+n-1}^n$$$

→ Reply

gratus907

5 years ago, # |

+39

Solns/Approaches

A. Check every element
B. Observe that answer never exceeds 5000 (use log to check). We can loop until success.
C. Generate every possible combination. In python, we have combinations_with_replacement which generates exactly what we need
D. Observe that for $$$x < b$$$, $$$\lfloor x/b \rfloor$$$ is zero. We want to take $$$x = kb-1$$$. Also observe that taking $$$k > 1$$$ always make the answer worst. We take $$$x$$$ as $$$\min(n, b-1)$$$.
E. What we need is set of $$$(a, b)$$$s such that distance between $$$a, b$$$ never occurs twice. (Considering not only b-a, but we have to consider the other way. e.g, when $$$n = 10$$$, distance between $$$1$$$ and $$$10$$$ is 1 and 9. both should not appear again.)
When $$$n$$$ is odd, take $$$(1, n), (2, n-1), \dots$$$. One can easily show that this is valid.
When $$$n$$$ is even, take those values until we can't. (e.g, when $$$n = 10$$$, we take $$$(1, 10)$$$, $$$(2, 9)$$$ but not $$$(3, 8)$$$ since distance between $$$(3, 8)$$$ is 5 and 5 — repeated.) Then, discard one unused value and proceed. (e.g, after two takes, use $$$(3, 7)$$$ instead of $$$(3, 8)$$$, and $$$(4, 6)$$$.
Submission : https://atcoder.jp/contests/abc165/submissions/12617571
F. Consider computing LIS length in $$$O(n \log n)$$$ time with DP and lower_bound. (without considering the actual values). When we do this, we discard what was in that spot (lower bound). Instead of doing this, keep those values by multiset or stuff like that. We traverse tree in DFS order, pushing values we meet in LIS-solving pattern but keeping values instead of throwing away. When we traversed all of it's subtrees, we erase value of the node from where we pushed. To do this we track the number of non-empty multisets and index we pushed each value in. Time complexity $$$O(n \log n)$$$.
Submission : https://atcoder.jp/contests/abc165/submissions/12637543

→ Reply

sasuke4981

5 years ago, # ^ |

@gratus907 can you please tell how you came to conclusion for problem E?

→ Reply

gratus907

5 years ago, # ^ |

I thought it intuitively after some casework... and I tried to prove my thought (I mean, not rigorously, but like convincing enough to start writing code)
As I've wrote, a case when two people meet twice is only when there exists $$$(a, b)$$$ and $$$(c, d)$$$ which $$$b-a$$$, $$$n+a-b$$$, $$$d-c$$$, $$$n+c-d$$$ has repetitions. Try some casework in $$$n = 8$$$, $$$n = 10$$$ to convince yourself with this statement :)

I actually have nothing much to say as I did tons of caseworks on paper...:(

→ Reply

okwedook

5 years ago, # ^ |

← Rev. 2 →

You don't really need any multiset for problem F. Just change the value at lower_bound and remember what it was. After solving all subtrees and updating the answer just return the value to what it was. Submission

→ Reply

gratus907

5 years ago, # ^ |

← Rev. 2 →

Apparently yes.. I discussed this problem with my friend after the contest and he also said the same thing. I felt very dumb since he coded like 800 bytes while I coded more than 2000... lol
I have no idea how I managed to think returning values by dfs tree and then thought something like "WOW I want vector<multiset<int>>" and started coding :(

→ Reply

Grey_Matter

5 years ago, # |

I'm assuming some greedy strategy works for C. Can somebody please post their logic/solution? I filtered queries such that for each (a, b) indices pair — the optimal c for maximum d is known. For the array A[n], I set A[0] = 1. From here, I am confused about how to construct the rest of the array. I tried a couple of ways but there were always some cases not adhering to the rule.

→ Reply

5 years ago, # ^ |

C was a pruned brute solution i think.

→ Reply

Grey_Matter

5 years ago, # ^ |

Yeah. During the contest, I thought the time complexity would be too much. I wish I had checked it with a program though. For n = m = 10, there are about 48,000 possible sequences only.

→ Reply

ShineEternal

5 years ago, # |

It seems difficult orz

→ Reply

tzc_wk

5 years ago, # |

+43

I think E is harder than F, as I'm not good at construction and pattern observing

→ Reply

It_Wasnt_Me

5 years ago, # ^ |

F was like if you know segment tree you will solve it immediately. Nothing special was in it

→ Reply

cheissmart

5 years ago, # ^ |

+19

How is segment tree related to F? I think most contestants solve it like this: submission

→ Reply

raja1999

5 years ago, # ^ |

You can find lenghh of LIS ending at a node u, using segment tree as well after compressing a[i] s

→ Reply

cheissmart

5 years ago, # ^ |

+28

Oh, I got it. But I think this implementation is much easier.

→ Reply

Tathagat_shah

5 years ago, # ^ |

Could you please Explain, how to solve F using segment tree. Thanks It_Wasnt_Me

→ Reply

BurnoutAg7

5 years ago, # |

+12

Is this round a bit easier than before? I used to solve 4 or 5 problems but today I solved 6 within a short time. Well anyway the problems are still very good (like, you can solve D and E with about 300 bytes of code but you need to think a long while). BTW, I think C is a bit hard for C. Since DFS may be not very "beginner-friendly".

→ Reply

sumit_kk10

5 years ago, # |

D one was way too easier than the C one

→ Reply

one_last_chance

5 years ago, # |

← Rev. 2 →

Check Same question ... I still missed it.. hard luck today.

→ Reply

Nson

5 years ago, # |

F is an easier version of NA Southeast Regional 2019 problem G

→ Reply

hoke_t

5 years ago, # ^ |

Here it is on Kattis: https://open.kattis.com/problems/neverjumpdown

→ Reply

wxhtzdy

5 years ago, # |

← Rev. 4 →

-29

Nice contest!

→ Reply

Errichto

5 years ago, # ^ |

+12

This comment shouldn't be answered. This is a problem from an ongoing contest, Bubblecup.

→ Reply

siddharthabhi30

5 years ago, # |

← Rev. 2 →

From stars and bars trick we get for C only 92378 states are there i.e ncr(10+10-1,10-1)

→ Reply

ADJA

5 years ago, # |

A. Oh, constraints are really small, let's just iterate.
B. Hm, it's exponential growth, I think max answer is not too big. Let's write and see (turns out max answer was in samples, but I didn't notice).
C. Hm, seems like a lot of states, no idea, let's read D.
D. Hmm, let's write bruteforce and see. Oh, it's always zero for multiples, ok, let's take multiple-1 if we can.
C. Hmm, maybe there are not too many states? Let's write bruteforce and see. Oh, it's really small, dumb me. (It's just C(n + m — 1, n))

E and F are nice, but quite easy.

→ Reply

Priyam2k

5 years ago, # ^ |

How do you arrive at C(n + m — 1, n)? I had to count them by writing the dfs.

→ Reply

5 years ago, # ^ |

← Rev. 2 →

The sum of gaps between consecutive numbers is less than equal to m-1, it's basic P&C afterwards.

→ Reply

Shisuko

5 years ago, # ^ |

← Rev. 3 →

+24

This is a classic stars and bars application.

Note the condition that $$$1 \leq A_1 \leq A_2 \leq ... \leq A_n \leq M$$$. Thus, it is sufficient to count how many times each number from $$$1$$$ to $$$M$$$ appears in the sequence (because we would then only have one way to arrange these numbers---in nondecreasing order). So, now imagine a line with $$$N$$$ stars and $$$M-1$$$ bars. The stars before the 1st bar corresponds to the number of 1s, the stars between the 1st and 2nd bar correspond to the number of 2s, etc. For example, if m=4 and n=7, then *||****|** corresponds to one $$$1$$$, zero $$$2$$$s, four $$$3$$$s, and two $$$4$$$s. So, how many possible ways are there to arrange $$$M-1$$$ bars and $$$N$$$ stars in a line? There are $$$M+N-1$$$ "spaces", and of them we need to choose $$$N$$$ locations to be where we place the stars. We place the bars in all other locations.

→ Reply

Priyam2k

5 years ago, # ^ |

Thanks!

→ Reply

Vlaine

5 years ago, # ^ |

Isn't it "N locations to be where we place the stars. We place the bars in all other places"?

→ Reply

Shisuko

5 years ago, # ^ |

You are correct, I have edited it now. Thanks

→ Reply

trying_to_learn_coding

5 years ago, # |

Can someone explain the observation made in problem E.

→ Reply

walleeva

5 years ago, # ^ |

check thiscould be helpful but a bit long explanation

→ Reply

trying_to_learn_coding

5 years ago, # ^ |

Thanks.. Quite good explanation

→ Reply

s_hertelli

5 years ago, # |

in problem E: if i match 1 with n then 2 with n-1 and so on (m times) why is it wrong

I got WA with this approach in 9 test cases

→ Reply

Nson

5 years ago, # ^ |

For 8 3, you would match

1 8
2 7
3 6

Consider, initially, $$$A = 1$$$, $$$B = 3$$$. They will fight at rounds 3($$$A = 3$$$ and $$$B = 6$$$) and 7($$$A = 7$$$ and $$$B = 2$$$).

This strategy works for odd N though.

→ Reply

cr8

5 years ago, # ^ |

← Rev. 2 →

But this only happens when they have the same distance between the pairs. So if you avoid that special case, should it be right? https://atcoder.jp/contests/abc165/submissions/12657318

→ Reply

Nson

5 years ago, # ^ |

For 8 3 your code prints exactly the same output of my previous message.

→ Reply

KobeDuu_

5 years ago, # ^ |

initially,B = 4

→ Reply

Hallucinationnnnnn

4 years ago, # ^ |

In your reply,B=4

→ Reply

vivekcrux

5 years ago, # |

Can anyone prove the running time complexity for the brute solution of C please?

→ Reply

Not-Afraid

5 years ago, # ^ |

← Rev. 2 →

O(Q * 92378) because number of valid(non-decreasing arrays) arrays with n = 10 and m = 10 are 92378. You can calculate this with dp or with Combinatorics.

Code for Counting with Dp

#include <bits/stdc++.h>

using namespace std;

int dp[11][11];

int go(int id, int last) {
  if (id == 10) return 1;
  if (~dp[id][last]) {
    return dp[id][last];
  }
  int ans = 0;
  for (int i = last; i <= 10; ++i) {
    ans += go(id + 1, i);
  }
  return dp[id][last] = ans;
}

signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  memset(dp, -1,sizeof dp);
  cout << go(0, 1);

  return 0;
}

→ Reply

chokudai

5 years ago, # |

Auto comment: topic has been updated by chokudai (previous revision, new revision, compare).

→ Reply

karanagarwalla

5 years ago, # |

← Rev. 2 →

May someone help me debug F: LIS on Tree? I have done using binary search and dynamic programming. I have used 0-indexed dp. My submission: https://atcoder.jp/contests/abc165/submissions/12674946

→ Reply

oversolver

5 years ago, # ^ |

test

→ Reply

newStartNotSure

5 years ago, # ^ |

+13

ans[v] will not be lo + 1. It will be the current size of vector. Just changed that got AC: https://atcoder.jp/contests/abc165/submissions/12675337

→ Reply

karanagarwalla

5 years ago, # ^ |

Sorry my bad. I thought the length of LIS at node v. Thanks a lot for your help.

→ Reply

oversolver

5 years ago, # |

hello?

→ Reply

Bhj2001

5 years ago, # |

← Rev. 2 →

How does the checker work in E? chokudai

→ Reply

Priyam2k

5 years ago, # ^ |

For all the pairs given by the user check their difference both ways. Like 1 and 10 will have difference 1 and 9. These differences should be all different. So you can check in O(M).

→ Reply

gaurav1903

5 years ago, # |

-6

I can't understand why my A solution fails Here's my code

k=int(input()) a,b=map(int,input().split()) if b-a+1>=k: print('OK') else: print('NG')

can anyone point out my mistake

→ Reply

oversolver

5 years ago, # ^ |

a=b=k

→ Reply

KobeDuu_

5 years ago, # |

why would I get WA for problem.E

#include <bits/stdc++.h>

#define x first
#define y second
#define pii pair<int,int>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long LL;
const int maxn = 1005;
int main(){
    int n,m; cin >> n >> m;
    vector<pii> ans;
    int L = 1,R = n;
    while(m){
        if(L+n-R == R-L) L += 1;
        else{
            ans.push_back(pii(L,R));
            L++; R--; m--;
        }
    }
    for(int i = 0;i < sz(ans); ++i) 
        cout << ans[i].x << " " << ans[i].y << '\n';
    return 0;
}

→ Reply

KobeDuu_

5 years ago, # ^ |

I found bug!

→ Reply

swapnil07

5 years ago, # |

← Rev. 2 →

+24

I believe the test files for the problem E were incorrect.
Instead of n <= 100000 , it should be m <= 100000 . If I write an assert statement for the value of n being less than or equal to 1e5, the verdict is RE, while for 2e5+2 it is AC.

→ Reply

swapnil07

5 years ago, # ^ |

Oh, there was a clarification as well, my bad. :(

→ Reply

Kulhari_adi

5 years ago, # |

Problem F:I have used LIS(nlogn) with B.F.S. but getting T.L.E......please help. https://atcoder.jp/contests/abc165/submissions/12695808

→ Reply

5 years ago, # ^ |

You may try dfs instead.(Read my code for more info).

→ Reply

5 years ago, # ^ |

I have used dfs but got TLE Here is the link: https://atcoder.jp/contests/abc165/submissions/12791770

→ Reply

5 years ago, # ^ |

← Rev. 2 →

You shouldn't pass a "vector L" in a function.You know,vectors are like arrays,so they require time to pass between functions.Try changing it to" vector &L",which passes a "virtual" vector(like a pointer).That shall get an AC.

→ Reply

5 years ago, # ^ |

Or you can make L an array out of the dfs functions.My code used just that.

→ Reply

5 years ago, # ^ |

Ok thanks. But can you figure out complexity of that code

→ Reply

5 years ago, # ^ |

O(n log n) for dp,plus a constant(of the vector).It's good enough.

→ Reply

5 years ago, # ^ |

Sorry for my code?

→ Reply

5 years ago, # ^ |

Can you figure out the complexity of my above code?

→ Reply

5 years ago, # ^ |

O(n^2)(for passing the vector).

→ Reply

5 years ago, # ^ |

Thank you I got the concept. Whenever we pass a vector by value it copies the content rather than updating it which is costly

→ Reply