include <bits/stdc++.h>

5 years ago, # |

The contest will start in 2 mins!

→ Reply

ILoveBitches

5 years ago, # ^ |

-7

It already started!

→ Reply

5 years ago, # ^ |

Thanks!

→ Reply

czh294

5 years ago, # |

I wonder where I can find the tutorial after this contest. I am a beginner this is my first time to participate in this atcoder contest

→ Reply

letsJustDoIt

5 years ago, # ^ |

-17

In the Contest Page itself , after the contest AtCoder provides Tutorials for each problem in well descriptive way.

→ Reply

Iftekhar_Hakim_K

5 years ago, # ^ |

Sometimes editorial in English is not provided promptly after the contest. It is better to have a look in this discussion post after it ends. Many people will share their ideas.

→ Reply

ram_2000

5 years ago, # ^ |

can u send me the link to the atcoder tutorial (at least the Japanese one so that I can use google translate).

→ Reply

Its_Easy

5 years ago, # ^ |

In the contest page you will get a tab called "Editorial" whenever its available.

→ Reply

Agnimandur

5 years ago, # |

-14

Finally!

Full sweep of the problem set (after some annoying debugging on F).

→ Reply

iynaur87

5 years ago, # |

+20

F is interesting! get AC at the very last minute!

→ Reply

hydro_lyte

5 years ago, # |

← Rev. 4 →

How to solve D? I was getting WA for last 4 test cases.

→ Reply

pigeon_hole

5 years ago, # ^ |

-9

you have to get length of cycle in component containing 1

→ Reply

outerspace

5 years ago, # ^ |

Can you tell me what's wrong here? submission

→ Reply

pigeon_hole

5 years ago, # ^ |

its not always the case that you have to travel cycle atleast once

→ Reply

drizzy

5 years ago, # ^ |

What's wrong with my submission? Code link

→ Reply

https://atcoder.jp/contests/abc167/submissions/13089636

5 years ago, # ^ |

	 if(k<0){
	 	cout<<path[i]<<" ";return 0;
	 }

Shouldnt this be path[k+i]

→ Reply

Sadat999

5 years ago, # ^ |

Can you please check this solution of mine?

→ Reply

Here's a short implemenation.

5 years ago, # ^ |

Well, the TLEs are caused by find(hello.begin(), hello.end(), aaa);

→ Reply

recursively

5 years ago, # ^ |

find the beginning of the cycle in the created graph (or linked list), as well as the length of the cycle. Then, roughly speaking, take K % (cycle of length) and just traverse the list one more to find the final index.

→ Reply

Imperial_Lord

5 years ago, # ^ |

Do it for 2 different cases k<=n and k>n. Check manually for k<=n and use the idea of cycle for k> n!

Here is the code

→ Reply

zodiac

5 years ago, # ^ |

-14

Hint : After a point towns start to repeat themselves periodically and king starts travelling in a cycle. https://atcoder.jp/contests/abc167/submissions/13059179

→ Reply

jatinmunjal2k

5 years ago, # ^ |

Simulate the teleportation until you find repetition. Then go and find the first occurrence of the repeated value. The answer will be to travel to the first occurrence and then going in a loop from the first occurrence to last occurrence, for which the answer can be calculated using modulo.

→ Reply

spacewalker

5 years ago, # ^ |

+25

Let $$$f_k(i)$$$ be the town we end up at if we start at town $$$i$$$ and teleport $$$k$$$ times. Then note that for positive $$$p$$$,

$$$f_{2^p}(i) = f_{2^{p-1}}(f_{2^{p-1}}(i))$$$

The input corresponds to $f_1$. So compute $$$f_2, f_4, f_8, \dots$$$ using this DP. Then divide $$$k$$$ into powers of 2 and apply the $$$f_i$$$ that correspond to those powers.

→ Reply

Its_Easy

5 years ago, # ^ |

I did it using binary lifting...as it was what i got in my mind first but finding cycle length is a great idea(and easier i guess).

Here is my submission: Code

→ Reply

rahuliitkgp

5 years ago, # ^ |

← Rev. 3 →

I have observed most people used std::set and messy implementations to find the starting point of the cycle but you can use a very easy floyd warshall cycle detection algorithm to find it. you can learn about it on the internet it very easy to understand

Here is my implementation I have heavily commented it at so that you can understand easily

→ Reply

xiaoshizhan

5 years ago, # ^ |

← Rev. 12 →

Because there are n towns, accoriding to pigen hole theroy, after n moves, there must be repeated visited towns. So the solutions is: (1) if k <= n, just simulate k moves; (2) if k > n, simulate n moves. If the n-th visited town is x, then the cycle length is n-last[x]. last[x] is the last time x is visited before the n-th move. Decompose k moves into three parts. First n moves, then (k-n)/(n-last[x]) cycles, then (k-n)%(n-last[x]) moves. After the cycles part the king returns to x. So the answer is move from x for (k-n)%(n-last[x]) moves.

→ Reply

Trgt_2021_explosion

5 years ago, # ^ |

For 2nd case(k>n) why I have to simulate n moves? I have to simulate just till I got a city(say X) which has already appeared. so just find previous occurrence of X say it's I. so I should subtract I from k. k=k-i; now take mod. k=k%length_of_cycle; and then traverse from i till k.

What is wrong with idea?? Can you please point out. I am getting RE for some case because of zero length_of_cycle. Because when i am taking separate case i.e. return if cycle_length is zero then i getting wrong answer instead of RE. But length of cycle can never be zero. I am

I have been stuck. Please help anyone.my submission

→ Reply

5 years ago, # ^ |

There must be some of by one error... What if k==l.length()?

→ Reply

Trgt_2021_explosion

5 years ago, # ^ |

← Rev. 2 →

For k>= l.length()

You can see in the code{line 45,46,47} I am finding previous occurrence of X (since this is the town which got repeated for the 1st time). say it's index is 'i' then cycle_length= l.length()-i-1; Since cycle/looping start from i so we should subtract the steps before i so k=k-i; and now we will take the mod with cycle_length and then traverse from i till k.

If I am wrong somewhere please tell.

→ Reply

xiaoshizhan

5 years ago, # ^ |

test your code with: 1 10000 1

→ Reply

xodeChemist

5 years ago, # ^ |

first find the length of cycle then using bisection you can get the solution one think you have to consider when cycle length is 2e5 overflow can occure because 2e5*1e18 cross long long range ..

→ Reply

5 years ago, # |

How to Solve E ?

→ Reply

5 years ago, # ^ |

+15

loop k1=0 to k:
   ans+=c(n-1,k1)*m*(m-1)^(n-1-k1)

→ Reply

5 years ago, # ^ |

Why?

→ Reply

5 years ago, # ^ |

explanation below

→ Reply

5 years ago, # ^ |

+25

c(n-1,k1) part is straight forward: find k1 points to split the whole row.

In each of k1 + 1 segments, colors must be different. The 2 blocks at either side of each splitting point have same color.

m is for the first block of first segment, it can choose from all m colors. for the rest blocks of first segment, each one can only choose from m-1 colors since its color must be different from adjacent blocks.

for the first block of other segment, it has only 1 choice: the same as the last one of previous segment. the rest blocks of other segment are like that in the first segment, each has m-1 choices.

Hence the algorithm.

→ Reply

5 years ago, # ^ |

why c(n-1,k1)?? ... why not c(n,k1)??

→ Reply

pandastic

5 years ago, # ^ |

We are looking for the number of ways to choose k1 pairs of adjacent/consecutive blocks out of the total number of n-1 such pairs.

→ Reply

5 years ago, # ^ |

Ohh ... Thanks!

→ Reply

5 years ago, # ^ |

pandastic is right about it below.

→ Reply

5 years ago, # ^ |

← Rev. 2 →

Initially, we want to split the array into (k1+ 1) non-empty segments, so we are selecting elements from first n-1 elements and each selected element represents right borderline of the segment. We will get an empty segment if we allow n elements. See the problem with c(n,k1) :

→ Reply

Rudraksh

5 years ago, # ^ |

Bhai ye picture kaise banai?

→ Reply

5 years ago, # ^ |

Online Ms paint, then upload that picture on some image hosting website and finally link that in the comment.

→ Reply

recursively

5 years ago, # ^ |

I understand the idea but keep hitting TLEs. How can you computer "n-1 choose k1" efficiently?

→ Reply

5 years ago, # ^ |

use c(n,m)=n!/m!/(n-m)! and precompute and cache x!.

don't use c(n,m)=c(n-1,m)+c(n-1,m-1)

→ Reply

CP_Sucks

5 years ago, # ^ |

shouldn't it be (m — 1)^(k -1) instead ??

→ Reply

5 years ago, # ^ |

After choosing k1 pairs, merge them and the problem reduce to: paint these segments such that adjacent segments having a different color. click here

→ Reply

5 years ago, # ^ |

merge with next element

→ Reply

CP_Sucks

5 years ago, # ^ |

I am sorry i still don't get why are you merging the two things. Dont they need to have different colors. So like first 2 will have same colors m ways and rest 2 will have m — 1 choices , so m*(m — 1)*(m — 1)

→ Reply

ranger2k

5 years ago, # ^ |

Can you please explain what's wrong with my submission, I have done exactly the same thing https://atcoder.jp/contests/abc167/submissions/13111548

→ Reply

5 years ago, # ^ |

count /= x -> WA

count *= inv(x) -> AC

where inv(x) is modular inverse of x

And consider the case when x = 0

→ Reply

ranger2k

5 years ago, # ^ |

AC thx mate.

→ Reply

shikhar.saxena24

5 years ago, # ^ |

(m-1)^(n-1-k1) bro why you do this ans how do you know say you have done k partitions then the multiplications in each block ?

→ Reply

5 years ago, # ^ |

for certain k1, the total ways of coloring equals to the multiplication of ways of coloring in each segment.

Denote b[i] be the number of blocks in ith segment, thus sum(b[i])=n. 1<=i<=k1+1.

As I mentioned above, for the first segment, the first block has m colors to choose and each of rest blocks has m-1 colors to choose. thus for the first segment the total ways of coloring is s[1]=m*(m-1)^(b[1]-1).

for the second segment, the first block has only 1 choice, which is the same as the last block of previous segment. each of rest block in second segment has m-1 colors to choose. Thus for the second segment the total ways of coloring is s[2]=1*(m-1)^(b[2]-1).

Similarly, s[3]=1*(m-1)^(b[3]-1)...s[k1+1]=1*(m-1)^(b[k1+1]-1).

So the total ways of coloring for k1 is:

s[1]*s[2]*s[3]*...*s[k1+1]
=m*(m-1)^(b[1]-1)*1*(m-1)^(b[2]-1)*...*1*(m-1)^(b[k1+1]-1)
=m*(m-1)^(b[1]+b[2]+...+b[k1+1]-(k1+1))
=m*(m-1)^(n-1-k1)

→ Reply

ajit

5 years ago, # ^ |

← Rev. 3 →

+53

Here is my approach: Consider we divide the n blocks into p sets of partitions and label them as n1,n2,n3,...,np. We could do it in (n-1)c(p-1) ways.

Another constraint is the total pairs of contiguous blocks with same color <=k. It means that (n1-1)+(n2-1)+....+(np-1)<=k which implies n1+n2+...+np-p<=k which implies n-p<=k thus we get p>=n-k

Now for coloring part of p sets can be done in m*((m-1)^(p-1)) ways.

So simply iterate p from n-k to n and add ((n-1)c(p-1)) * (m*((m-1)^(p-1))) to the answer.

→ Reply

5 years ago, # ^ |

Thanks ajit. Nicely explained. Now I am feeling sad that I was not able to solve it during contest .

→ Reply

liupo

5 years ago, # ^ |

← Rev. 2 →

could you explain why (n1-1)+(n2-1)+....+(np-1)<=k more?:)

→ Reply

ajit

5 years ago, # ^ |

← Rev. 2 →

Because a set(subarray) of x elements of same color have x-1 pairs of contiguous elements of same color like if [1,2,...x] is a set of elements of same color then we have the pairs (1,2) (2,3) ... (x-1,x) to count which in total is x-1

→ Reply

landour

5 years ago, # ^ |

I have a small doubt in problem statement

For n=6 m=2 k=2

2 2 2 1 2 2

Is this a valid combination?

→ Reply

ajit

5 years ago, # ^ |

No, because we have 3 pairs of contiguous blocks of same colour with indices (1,2) (2,3) (5,6) which is greater than k=2

→ Reply

landour

5 years ago, # ^ |

Okay thanks!

→ Reply

liupo

5 years ago, # ^ |

now I got it, Thank you for your help

→ Reply

5 years ago, # ^ |

← Rev. 2 →

Can you please explain the m*((m-1)^(p-1)) part ?

Also ,since we are choosing p segments out of total n-1 segments then shouldn't it be c(n-1,p) ?

→ Reply

rr459595

5 years ago, # ^ |

← Rev. 4 →

We have 'p' partitions where the blocks inside each partition are colored the same with some color. For eg: 1 1 1 | 2 2 | 3 3 (3 partitions and 3 colors with n=7). First partition can be colored with 'm' colors and remaining (p-1) partitions can be colored with (m-1) colors each, as colors between adjacent partitions must be different.

Also, it's C(n-1,p-1) as we have to choose (p-1) bars (to get 'p' segments) from a total of (n-1) bars .

→ Reply

5 years ago, # ^ |

Now I am even more confused. :(

→ Reply

rr459595

5 years ago, # ^ |

Which part is confusing ?

→ Reply

5 years ago, # ^ |

Got it now, thanks :)

→ Reply

yogi

5 years ago, # ^ |

← Rev. 3 →

Nicely explained,can you please explain, (n-1)C(p-1) part like how you get this relation. UPD: Got it.

We are using (p-1) because to get p partitions we have to put (p-1) bars between the n blocks.

We will not do the mistake to choose n because there is no point on putting the bars at the beginning ie behind the first block.

→ Reply

tanmay2625

5 years ago, # |

+77

F was 1203F1 - Complete the Projects (easy version) in disguise..

→ Reply

StarFlux

5 years ago, # ^ |

← Rev. 2 →

+31

Exact same problem: https://mirror.codeforces.com/gym/101341/problem/A

EDIT: link to the editorial for this problem: https://mirror.codeforces.com/blog/entry/51445?#comment-393777

→ Reply

madlad

5 years ago, # |

What sorting method works for F?

→ Reply

CheldonShooper

5 years ago, # ^ |

difference of opening and closing brackets in non-decreasing order

→ Reply

pigeon_hole

5 years ago, # ^ |

← Rev. 2 →

how are you taking care of these cases

)(

(

)

→ Reply

KichhuMichhu

5 years ago, # ^ |

Put all the Open braces at first, and closing braces at last. For )( cases, sort them by https://mirror.codeforces.com/blog/entry/77148?#comment-619238 and put in between open and closed braces. If everything works out, put Yes.

→ Reply

TheSawan

5 years ago, # ^ |

Can we re arrange some string ? where is it written in statement?

→ Reply

coderanant

5 years ago, # ^ |

No, we can't re-arrange a particular string.

→ Reply

aditya_sheth

5 years ago, # ^ |

-7

can someone explain why this works?

My idea was to sort according to the minimum of opening-closing bracket at any point for each string. Then to use segment tree to get the string which gives maximum opening-closing brackets in a certain range. I don't know why this code doesn't work. Is the idea correct?

→ Reply

raja1999

5 years ago, # ^ |

← Rev. 2 →

+25

Try this.

(((((

))

))))(

Your method gives No. But the answer is Yes

→ Reply

aditya_sheth

5 years ago, # ^ |

-10

Thanks!!

→ Reply

5 years ago, # ^ |

Every string has a balance of open/close, and a min value, which is the minimum balance where the string can be used.

ie it looks like '))((((....', then the balance must be 2 before we can use it. We need to consider both properties.

→ Reply

jagarwal

5 years ago, # ^ |

I think this algo is wrong. Consider the following case:

4
(
)((
))(((((
)))))

Here your algo will give answer "No", but the correct answer is "Yes".

→ Reply

KichhuMichhu

5 years ago, # ^ |

Right! That's why we need some hacking phase (and crowdsource some more test cases) :D Thanks for pointing out.

→ Reply

KichhuMichhu

5 years ago, # ^ |

-10

(A.openCount-A.closeCount) - (B.openCount-B.closeCount)

→ Reply

HelloWorld

5 years ago, # |

What are the difficulties of todays' problems in terms of codeforces ratings?

→ Reply

tanmay2625

5 years ago, # ^ |

← Rev. 2 →

-26

A,B,C < 1000

D : 1200/1300

E : 1500/1600

F : 2000/2100

→ Reply

Agnimandur

5 years ago, # ^ |

My best estimate:

A — 600 B — 900 C — 1100 D — 1400 E — 1700 F — 2000

Roughly, the gap in difficulty between the problems was the same.

→ Reply

_Bishop_

5 years ago, # |

How to solve E?

→ Reply

Iftekhar_Hakim_K

5 years ago, # ^ |

← Rev. 3 →

+14

At most K adjacent pairs can be same. So at least n-1-k pairs have to be different. Let we need to make p pairs different. So it can be done in C(n-1,p)*M*(M-1)^p. Do this for all p from n-1-k to n-1.

→ Reply

vijasi

5 years ago, # ^ |

Can you explain, how you got the formula?

→ Reply

Iftekhar_Hakim_K

5 years ago, # ^ |

Choosing p pairs from n-1 is C(n-1,p). If p adjacent pairs are different,there are p+1 parts,where each part has same color. Now,there are M ways to color the first part, all other parts have (M-1) ways.

→ Reply

https://atcoder.jp/contests/abc167/submissions/13121855

5 years ago, # ^ |

Hey! Am still not clear with your intuition. Choosing p pairs is fine. But how did you arrive at them being adjacent? Can you please explain your idea?

→ Reply

KHVic

5 years ago, # ^ |

← Rev. 2 →

I try to break it down

C(n-1,p) => number of ways to pick p items so that it has the same color as the item left to it

Consider the case of p = 0, all items are distinct then there are N blocks with different color When p = 1, one item has same color with block on left, so number of continuous block with same color becomes N-1. ... go on until p = k so there can be N-p number of continuous block with the same color

Now to choose the color: First continuous block can be any color M Second until last continuous block segment can only be one of the M-1 color

Thus, total ways to color block segment = M*(M-1)^(N-p-1)

Putting it together=> total of ways to color * total of ways to select p items = C(n-1,p)*M*(M-1)^(N-p-1)

→ Reply

xodeChemist

5 years ago, # ^ |

thanks for your explanation

→ Reply

SPyofgame

5 years ago, # |

← Rev. 4 →

How to solve E ? Can someone hint me ?

My approach with MLE

int n, m, k;
/// 3 dimentional vector
v3_i f;

/**
magic(i, pre, cnt):
    i   = current index
    pre = previous color used
    cnt = number of same adj

res = magic(0, 0, 0)
*/ 
int magic(int i = 0, int pre = 0, int cnt = 0)
{
    if (cnt > k) return 0;      /// If there are more (k) same adj
    if (i >= n) return 1;       /// If we fisnish building an array
    int &res = f[i][pre][cnt];
    if (res != -1) return res; /// If calculated then return
    res = 0;

    for (int nxt = 1; nxt <= m; ++nxt) /// For every color
        res = (res + magic(i + 1, nxt, cnt + (pre == nxt))) % MOD;
    
    return res;
}

int main()
{
    n = readInt();
    m = readInt();
    k = readInt();

    /// Assign f[n + 1][n + 1][k + 1] = {-1}; 
    f.assign(n + 1, v2_i(n + 1, vi(k + 1, -1)));
    cout << magic();
    return 0;
}

My approach with WA

/// Same approach with previous one
/// But assuming that we only care about 2 cases
/// -> We take the same color
/// -> We take the diff color
/// int pre -> bool pre || reduce complexity

int n, m, k;
v3_i f;
int addMod(int a, int b, int mod = MOD) { return (a + b) % MOD; }
int magic(int i = 0, bool pre = 0, int cnt = 0)
{
    if (cnt > k) return 0;      /// If there are more (k) same adj
    if (i >= n) return 1;       /// If we fisnish building an array
    int &res = f[i][pre][cnt];
    if (res != -1) return res; /// If calculated then return
    res = 0;

    if (i == 0)
        return (2LL * magic(1, 0, 0)) % MOD; /// because magic(1, 0, 0) = magic(1, 1, 0)

    /// There are (m - 1) different color to choose
    res = addMod(res, ll(m - 1) * magic(i + 1, !pre, cnt));

    /// There is only one same color to choose
    res = addMod(res, 1LL * magic(i + 1,  pre, cnt + 1));
    return res;
}

int main()
{
    n = readInt();
    m = readInt();
    k = readInt();

    f.assign(n + 1, v2_i(2, vi(k + 1, -1)));
    int res = magic();
    cout << res;
    return 0;
}

→ Reply

mbishnoi2

5 years ago, # |

Can anyone explain approach for problem C.

→ Reply

thelonewolf

5 years ago, # ^ |

You can bruteforce for all 2^n possibilies since n<=12.

→ Reply

abhi.gang699

5 years ago, # ^ |

hey, please tell how could one do it if the constraints are large ?

→ Reply

Vanilla_

5 years ago, # ^ |

-8

Look at the backtrack function, it generates all possible subsets, and then the solve() function checks if the books in the subset satisfy the condition

→ Reply

abhi.gang699

5 years ago, # ^ |

understood , thanks for the help !!

→ Reply

Vanilla_

5 years ago, # ^ |

abi gang :)

→ Reply

ritesharma

5 years ago, # ^ |

recursion approch. check all posibilities, cauz constraint is very less(2^12)*12.

→ Reply

shikhar.saxena24

5 years ago, # ^ |

do it look like 2d knapsack?

→ Reply

ritesharma

5 years ago, # ^ |

← Rev. 2 →

its just all subsequences problem; its rucursion approch u can solve by iterative method using bitmask;

here is two possibilities either i can take that book or i can leave that book, if i take then dp[j(0 to m]]-=ar[i][j] (after subtracting dp[j] would be the required value).if all required value <=0 that mean we have achieved the question requirment so i just compare with ans in base case

    static int ans=Integer.MAX_VALUE;
    static void solve(int id,int sum) {
       if(id<0) {
         boolean f=true;;
         for(int i=0;i<ar[0].length;i++) {
             if(dp[i]>0)return;
         }
         ans=Math.min(ans, sum);
         return;

       }
       for(int i=0;i<ar[0].length;i++) {
         dp[i]-=ar[id][i];
       }

         solve(id-1,sum+c[id]);
         for(int i=0;i<ar[0].length;i++) {
          dp[i]+=ar[id][i];
         }
         solve(id-1,sum);

    }

→ Reply

shikhar.saxena24

5 years ago, # ^ |

Thanks for the help Ritesh but if the constraint were big then should we use knapsack

→ Reply

ritesharma

5 years ago, # ^ |

no bro cauz this problem does not depend only on x and n, it depend on value of every book algorithm and cost of book and x and k value.so so i think we cant fill dp like knapsack;

→ Reply

Gomango999

5 years ago, # ^ |

M and N were very small, so you were able to brute force and test every possible combination of books bought vs cost.

→ Reply

ritik_patel05

5 years ago, # ^ |

← Rev. 2 →

Use bitmask to consider all possibilities and update the minimum cost if it's valid.

Submission

→ Reply

Norrius

5 years ago, # ^ |

With only $$$N = 12$$$ books, you can brute force all possible sets of them ($$$2^N = 4096$$$) and find the minimal cost. An easy way to work with it is to have an integer where $$$i$$$-th bit is set if you take $$$i$$$-th book.

→ Reply

Video Tutorials for E and F

5 years ago, # ^ |

Just a brute force for all 2^N combinations. My solution

→ Reply

zxcv890

5 years ago, # ^ |

I just used brute force. Try all possible subset of rows using bitmasks. The constraints imply this will fit within time.

→ Reply

stefdasca

5 years ago, # |

+28

My Discord Server

→ Reply

SPyofgame

5 years ago, # ^ |

Thanks for your solution but can I solve E with dp ?

→ Reply

stefdasca

5 years ago, # ^ |

There is a O(nk) DP solution but it's not fast enough.

→ Reply

ujju_sucks

5 years ago, # ^ |

← Rev. 4 →

Can u please explain the O(n*k) solution?? I tried solving using dp with segment tree but got WA. I used dp[i] =(i<=k+1?power(m,i):(m-1)* summation(dp[i-k-1] to dp[i-1])

→ Reply

https://mirror.codeforces.com/blog/entry/77148?#comment-619369

5 years ago, # ^ |

← Rev. 2 →

Hey! ujju_sucks I used the similar approach. But instead of using segment tree. I stored sum of previous k+1 elements. But couldn't get it working. Can you please check the approach

→ Reply

5 years ago, # ^ |

Hey! I think we misunderstood the problem. The question is asking for adjacent colour pairs across the entire colouring to be less than K. And not for any segment.

→ Reply

ujju_sucks

5 years ago, # ^ |

+18

Holy shit!!!! I am such a fool

→ Reply

Its_Easy

5 years ago, # ^ |

The reaction to realization of truth ..

→ Reply

leetcode07

5 years ago, # ^ |

← Rev. 2 →

Hey can you please explain in brief what is wrong with this dp? I am unable to follow your conclusion.

→ Reply

5 years ago, # ^ |

N=8 K=1 aabccdee This is invalid. As total pairs are 3.

→ Reply

31naretidem

4 years ago, # ^ |

I'd been losing my mind for over a day trying to find an example that didn't work.. thank you for posting this lmao

just as a curiosity, here's an O(n) dp solution to the way we initially understood the problem. I'm not fully confident it's correct, but hey it might be!

Code

#include <bits/stdc++.h>
using namespace std;

const int mod = 998244353;
const int N = 2e5+23;

int n, m, k;
long long dp[N];

int main() {
  scanf("%d%d%d", &n, &m, &k); ++k;
  long long cur = 1;
  dp[0] = 1;
  for (int i = 1; i <= n; ++i) {
    dp[i] = cur;
    if (i == n) {
      dp[i] = dp[i] * m % mod;
    } else {
      dp[i] = dp[i] * (m-1) % mod;
    }
    cur = (cur + dp[i]) % mod;
    if (i-k >= 0) cur = (cur - dp[i-k] + mod) % mod;
  }
  printf("%lld", dp[n]);
  return 0;
}

→ Reply

https://mirror.codeforces.com/blog/entry/77148?#comment-619369

5 years ago, # ^ |

Hey! stefdasca You can optimised the DP solution by storing previous k+1 sums. Can you please check the approach

→ Reply

leetcode07

5 years ago, # ^ |

I tried to do it with dp but could not reduce states. If somebody has done it using dp, please share the approach. Thanks

→ Reply

SPyofgame

5 years ago, # ^ |

My dp complexity is O(n ^ 3), how about you ?

My code

int n, m, k;
/// 3 dimentional vector
v3_i f;

/**
magic(i, pre, cnt):
    i   = current index
    pre = previous color used
    cnt = number of same adj

res = magic(0, 0, 0)
*/ 
int magic(int i = 0, int pre = 0, int cnt = 0)
{
    if (cnt > k) return 0;      /// If there are more (k) same adj
    if (i >= n) return 1;       /// If we fisnish building an array
    int &res = f[i][pre][cnt];
    if (res != -1) return res; /// If calculated then return
    res = 0;

    for (int nxt = 1; nxt <= m; ++nxt) /// For every color
        res = (res + magic(i + 1, nxt, cnt + (pre == nxt))) % MOD;
    
    return res;
}

int main()
{
    n = readInt();
    m = readInt();
    k = readInt();

    /// Assign f[n + 1][n + 1][k + 1] = {-1}; 
    f.assign(n + 1, v2_i(n + 1, vi(k + 1, -1)));
    cout << magic();
    return 0;
}

→ Reply

HelloWorld

5 years ago, # ^ |

← Rev. 2 →

Hey, for choosing x components from n elements, there should be (n-1)C(x-1) ways, right? Then why did you multiply each m*(m-1)^(x-1) element by (n-1)C(x)? UPD: I understood my mistake.

→ Reply

Gomango999

5 years ago, # |

When are the editorials posted for these contests?

→ Reply

srnsh1999

5 years ago, # ^ |

The Japanese tutorials are usually posted quite early after the contest ends. You might have to wait a day maybe for the english editorial sometimes. But you can always use Google Translate :).

→ Reply

lohit_97

5 years ago, # |

A difficult version of D is here: https://cses.fi/problemset/task/1750

Instead of starting at 1, start at a given X and solve the problem.

→ Reply

amiratou

5 years ago, # ^ |

Hint

→ Reply

verma_ankit484

5 years ago, # |

Why doesn't the relative sorting of strings work?

Solution (Wrong on only 1 case)

→ Reply

iynaur87

5 years ago, # ^ |

← Rev. 2 →

(

)((

()))

→ Reply

5 years ago, # ^ |

If a string looks like '))(((((...' you cannot use it everywhere. Each string has a balance and a min value of needed balance before that string.

→ Reply

void.abyss

5 years ago, # |

Lol, read k adjacent pairs will have the same colors in E.

→ Reply

kingarp1914

5 years ago, # ^ |

same :-( still around half of all test cases passed.

→ Reply

neel19

5 years ago, # |

How did you generate all the permutations for C? What I did is, I looped from 0-2^n-1, convert the value to binary, Wherever the bit is set, I push it to a temporary vector and send that vector to fun for solve. Here is what I did. Overcomplicated code How to simplify this?

→ Reply

lohit_97

5 years ago, # ^ |

To check if a bit is set or not, you don't need to convert it to string.

For example to check if jth bit in X is set or not, you can simple check the value of (x & (1<<j))

→ Reply

sharath101

5 years ago, # ^ |

This might help

→ Reply

dixitgarg

5 years ago, # |

For F: let's say some blocks have been placed giving total sum ( by total sum, I mean number of '(' minus number of ')' ), equal to prev. Now for all the blocks left, which have a minimum value of prefix sum greater than or equal to prev , select a block having a maximum total sum.This can be done by using binary search and seg-tree.

Is it wrong ? since I am getting WA verdict , not sure if the implementation is wrong or the logic is wrong.

→ Reply

aditya_sheth

5 years ago, # ^ |

← Rev. 2 →

-11

My ideas was also exactly this. It doesn't work for me too :( Can someone give a counter example for this idea?

→ Reply

gud_day

5 years ago, # ^ |

← Rev. 2 →

-8

Try the following test case :

["(((", ")", ")))("]

The correct answer is yes

EDIT : Formatting

→ Reply

abhishek_saini

5 years ago, # ^ |

← Rev. 2 →

+14

This approach will fail for the following case:

3
(((
())
)))(

After taking first string, you should take the third one, but according to your algo, you will take the second one.

→ Reply

Hints and Solutions for problems A-D

5 years ago, # ^ |

← Rev. 3 →

Why "equal to prev"?

We can use a string at a position if the current balance of open/close is bigger than the needed open brackets before that string.

To greedyly find a seq we can use all strings with above property, and would use the one with the biggest balance. Since that one gives most oportunities for the next step.

On each step we need to check if balance is smaller/bigger than needed open brackets.

But I do not get how to implement this in O(n logn)

Edit: Ok, did not see that: Every string has a third property, the number of closing brackets which must occour after it. We need to consider this, too.

→ Reply

sg_186

5 years ago, # |

-23

Three test cases are not possible for ques2? what is wrong in my code...

include <bits/stdc++.h>

using namespace std;

define int long long

int32_t main() { int a,b,c,k; cin>>a>>b>>c>>k;

int ans=0;
ans+=a*1;
int x=k-a;
if(x>0){
    ans+=b*0;
    x=x-b;
}
if(x>0){
    ans+=x*(-1);
}


cout<<ans<<endl;
return 0;

}

→ Reply

kingarp1914

5 years ago, # ^ |

you missed the case when k<a. In that case answer is just 'k' but your code prints 'a'

→ Reply

sahilbansal17

5 years ago, # |

→ Reply

650iq

5 years ago, # ^ |

Very nicely written pls make of codeforces as well.

→ Reply

abhisar1414

5 years ago, # |

Can someOne explain me this solution for D

https://atcoder.jp/contests/abc167/submissions/13028277

→ Reply

lohit_97

5 years ago, # ^ |

Read about Binary Lifting.

→ Reply

_Chaitanya1999

5 years ago, # |

← Rev. 2 →

How to do problem C (Skill Up) using DP if the constraints are slightly bigger(like n,m<=50).. Any kind of suggestion is appreciated. Link to the problem is -> https://atcoder.jp/contests/abc167/tasks/abc167_c

→ Reply

dixitgarg

5 years ago, # ^ |

← Rev. 2 →

Using min-cost max-flow, take n nodes to the left side ( represents books), m nodes to the right side ( represents algorithms), connect a source to all the n nodes in the left with capacity = total understanding it provides for all algorithms, and cost = cost of the ith book. connect sink with all the m nodes to the right with capacity x and cost 0, also for all the n nodes in the left, connect to each of the m nodes with a capacity equal to a[i][j] and cost 0. Now perform min cost maxflow algorithm and for the maximum flow calculate the minimum cost, if the maximum flow is not equal to m*x, then the answer is -1.(maximum flow cannot be greater than m*x since the capacity of all the edges to sink is x).

→ Reply

phantom11

5 years ago, # |

← Rev. 2 →

Is there a way to see test cases for Atcoder? My F submission failed on two test cases only, and I wanted to check what the case is. Here is my submission. Algorithm described in short:

Make Pair of elements for each string, (required, total), required saying how many opening brackets are required before this string (based on the minimum of the running total), and total telling what the end total is. Each opening bracket is +1, closing is -1.
Sort the Pairs based on required in ascending order.
In a loop, pick all the pairs which have their required less than the current_sum (initally 0), put it in the priority queue, sorted by decreasing total.
if queue was empty, print "No" else poll one element from the queue.

→ Reply

kadam

5 years ago, # ^ |

https://www.dropbox.com/sh/nx3tnilzqz7df8a/AAAYlTq2tiEHl5hsESw6-yfLa?dl=0 ,but the testcases of this round have not been added. Check again after few hours.

→ Reply

https://mirror.codeforces.com/blog/entry/77148?#comment-619315

5 years ago, # ^ |

→ Reply

phantom11

5 years ago, # ^ |

I checked and it passes that case.

→ Reply

wydadman

5 years ago, # |

It was my first contest in ATcoder, In the telporter problem I had 51 AC testcases and wondering if I can access the failed testcases? sub1_21.txt and files like that!

→ Reply

5 years ago, # ^ |

Testcases are available at this link after some days https://www.dropbox.com/sh/arnpe0ef5wds8cv/AAAk_SECQ2Nc6SVGii3rHX6Fa?dl=0

→ Reply

gouravraj

5 years ago, # |

← Rev. 2 →

Can anyone help me with problem C (Skill Up). Problem

→ Reply

5 years ago, # ^ |

Use brute force over all 2^n possibilities. I use bitmask to do so. https://atcoder.jp/contests/abc167/submissions/13070747

→ Reply

xodeChemist

5 years ago, # ^ |

0/1 knapsake also works

→ Reply

5 years ago, # |

For problem E, am using following dp approach. Need help in finding the issue with it.

dp[N] = dp[N-0] * nWays + ... dp[n-i] * nWays + ... dp[n-(k+1)] * nWays

- if n-i > 0 then nWays = m-1
- if n-i = 0 then nWays = m
- else nWays = 0

So at any point, I need to maintain sum of previous k+1 dp elements.

Here's the code

#define LL long long

int mod = 998244353;
LL dp[200005];

int main() {
	LL n,m,k;
	cin >> n >> m >> k;

	dp[1] = m;
	dp[2] = (dp[1] * (m-1))%mod;
	if(k > 0)
		dp[2] = (dp[2] + m)%mod;

	LL sum = dp[2];
	int st = 2;
	int cnt = 1;
	for(int i=3;i<=n;i++) {
		LL ways = (m-1)%mod;
		dp[i] = (sum * ways)%mod;
		if(cnt < k+1)
			dp[i] = (dp[i] + m)%mod;

		sum = sum + dp[i];
		cnt++;
		if(cnt > k+1) {
			sum = (sum - dp[st])%mod;
			sum = (sum + mod)%mod;
			st++;
			cnt--;
		}
	}

	cout << dp[n] << endl;

	return 0;
}

→ Reply

5 years ago, # ^ |

Can someone please point out where am I going wrong?

→ Reply

KHVic

5 years ago, # ^ |

← Rev. 3 →

Did you misunderstand the question? your dp formula seems to be implying that for each contiguous block there can not be more than K adjacent colors. The question is asking for adjacent color pairs across the entire coloring to be less than K.

→ Reply

5 years ago, # ^ |

← Rev. 2 →

So as far as I understood the question, maximum amount of contiguous blocks having same colour can not be more than K+1? Am I still interpreting it wrong?

For Ex: N = 4, M = 3, K = 2
aaabc, abbbc, aabbc, ababc... are valid sequences
aaaab, bbbbc are not valid sequences as it contains contagious block of length 4 (>3).

→ Reply

5 years ago, # ^ |

Thanks for pointing out. I think misunderstood the problem.

→ Reply

swapnil159

5 years ago, # |

I am very new to atcoder (given only 4 contests). Can someone give me an estimate as to what are the equivalent atcoder ratings wrt codeforces ratings??

→ Reply

5 years ago, # ^ |

+12

Maybe atcoder+300 == codeforces

→ Reply

AayushICS

5 years ago, # |

Hello. Can anyone give ideas on how to write a choose function that computes large values of C(c,r)%m quickly? Thanks.

→ Reply

5 years ago, # ^ |

To calculate C(n, r)%m and if m is prime its always better to compute factorial and their inverses in O(nlogm) and then use them to calculate C(n, r)%m in O(1) time. Here is the link to my submission: https://atcoder.jp/contests/abc167/submissions/13084560

→ Reply

https://cp-algorithms.com/combinatorics/binomial-coefficients.html

5 years ago, # ^ |

→ Reply

5 years ago, # |

What is wrong with my approach? Here is my submission link: https://atcoder.jp/contests/abc167/submissions/13095279. I divide both the strings into pos(total difference positive) and neg(total difference negative). In a greedy approach you place all pos strings before neg strings. Moreover in pos strings you place all strings in non-increasing order of minimal difference. You place all neg strings non-decreasing order of minimal difference. In case of ties you take the one with larger total difference.

→ Reply

living_in_genjutsu

5 years ago, # |

Most of the times the E or the F problem of the ABC is always related to combinatorics and I am not good at it.So can anyone suggest where can I find problems related to Combinatorics for practice.

→ Reply

trying_to_learn_coding

5 years ago, # |

please explain what is the error in my code for problem F? https://atcoder.jp/contests/abc167/submissions/13096927

→ Reply

trying_to_learn_coding

5 years ago, # ^ |

what I did is I remove all the perfect strings such as (()),()(). now if the sum of all the string +1 for ( and -1 for ) is not equal to zero the answer is No. else sorted it according to the difference of (open-close) in decreasing order and then traverse the whole string if the sum gets negative at any point then I output NO else yes.

→ Reply

vineetjai

5 years ago, # |

← Rev. 8 →

My solution for F: is to separate strings into 3 categories that resultant is (,),)(. Then putting all opening at front, all closing in end, and sorting )( according to open_count-close_count in decreasing order and putting in middle. My solution got AC on atcoder but failing on following testcase by giving answer No but it's actual answer is Yes. Here is my solution.

4  
((((( 

)))))(((((((( 

))))))(((((((((( 

))))))))))))

→ Reply

5 years ago, # ^ |

Each one of those strings has a property 'leading opening brakets'. It cannot be used at positions where the balance is less than that number.

So, we cannot simply sort by open_count-close_count, but we need to build a subset of strings with the leading opening brakets less than current balance, and then choose the one from those by using the sorting.

→ Reply

vineetjai

5 years ago, # ^ |

← Rev. 3 →

If you have solutions then please share link to your code.

Update: aren't you suggesting O(n^2) solution?

→ Reply

5 years ago, # ^ |

This one looks good https://mirror.codeforces.com/blog/entry/77148?#comment-619641

→ Reply

rananjay23

5 years ago, # ^ |

Please see this . I think it is correct .

→ Reply

TaeHo0o00o0N

5 years ago, # |

-16

how to solve A ?

→ Reply

arnab_goswami

5 years ago, # ^ |

+40

Learn FFT

→ Reply

newStartNotSure

5 years ago, # |

Testcase for F was very weak. AC code: https://atcoder.jp/contests/abc167/submissions/13063944 which fails on the TC:

(

)((

))((((

)))))

Answer should be Yes but AC solution gives No.

→ Reply

kumarkunal3510

5 years ago, # |

can anybody tell me what is wrong in my submission of d . It is just failing for some testcases

→ Reply

arnab_goswami

5 years ago, # ^ |

Ah, How can we know whats wrong in your code if you will not give the link

→ Reply

arnab_goswami

5 years ago, # ^ |

ur name should be kunal kamra

→ Reply

nEw_PineaPple

5 years ago, # |

← Rev. 3 →

My approach for problem F:

Find for each string the final sum(SUM) and the minimal sum(MIN) in that string. Minimum is restrained by zero.
Then divide the strings into four groups. First, those with SUM > 0 & MIN == 0, second those with SUM > 0 && MIN < 0, third with SUM < 0 and fourth with SUM == 0.
Next, we place the strings one after another and maintain CURSUM.
Place the first category in the beginning in any order.
Then we place the second category in order of decreasing MIN. This is because these strings still increase the CURSUM. If at any time CURSUM + MN < 0, we return no.
Then we place all strings of the fourth category. If at any time CURSUM + MN < 0, we return no.
Lastly, we place the strings of the third category in order of increasing MN as these strings decrease CURSUM. If at any time CURSUM + MN < 0, we return no.
If after this CURSUM is not 0 we return no else return yes.

This gives WA. Can any one give a counter test?
My code

→ Reply

fofao_funk

5 years ago, # ^ |

try this

3 (((( ))) ))(

→ Reply

nEw_PineaPple

5 years ago, # ^ |

got it. thanks!

→ Reply

rananjay23

5 years ago, # |

← Rev. 6 →

Edit : My solution got AC but is not correct (see example below) . I have modified the approach little bit (see my comment below) and now it is giving correct answer for the example below as well.

solution for F : We need to assign each string a weight , sort them in descending order according to the weight and finally combine the strings in that order . Now how to assign the weight ? Let us call number of occurrences of $$$($$$ as $$$O$$$ and number of occurrences of $$$)$$$ as $$$c$$$ . We calculate these numbers for each string individually and then we do following :

code snippet

       if(o==0)
            p[i].first = INT_MIN;
        else if(c==0)
            p[i].first = INT_MAX;
        else if(o>c)
            p[i].first = INT_MAX-c;
        else if(o<c)
            p[i].first = INT_MIN+o;
        else
            p[i].first = 0;

Reason :we want as may characters of type $$$($$$ in initial part of final string and as many character of type $$$)$$$ in final part. we want strings of type $$$((((($$$ to occur first and strings of type $$$))))$$$ to occur last. Now for string in which $$$o>c$$$ , we put that string first which has least number of $$$c$$$ .Example : we will put $$$))(((((($$$ before $$$)))(((((((((($$$ because let $$$(($$$ occurs before both of them then if we put $$$)))(((((((((($$$ just after it , then there will be unbalance .

Case for strings in which $$$c>o$$$ is symmetric to the case $$$o>c$$$ if we look from right side .

Now for strings in which $$$o==c$$$ , they don't contribute any extra '(' or ')' and thus we put them in the middle . Else they can cause problem . We can build the final string by combining all other strings after sorting and check if it is balanced .

submission : link

→ Reply

geeky.ass

5 years ago, # ^ |

← Rev. 3 →

Shouldn't the following test case output "Yes"? (by arranging them in the given order)

4
(
)(((())
))(((
)))

I got "No" from your code

→ Reply

rananjay23

5 years ago, # ^ |

← Rev. 8 →

Thanks for providing counter example . I have redefined the weights as following : we find number of '$$$($$$' not balanced by '$$$)$$$' and call it o1 and number of '$$$)$$$' not balanced by '$$$($$$' as c1 .For example in $$$)((())))$$$ c1 = 2 .

code snippet

        o1 = c1 = 0;

        for(j=o=0;j<s.size();++j)
        {
            if(s[j]==')')
            {
                if(o==0)
                    ++c1;
                else
                    --o;
            }
            else
                ++o;

        }

        for(j=s.size()-1,c=0;j>=0;--j)
        {
              if(s[j]=='(')
              {
                  if(c==0)
                    ++o1;
                  else
                    --c;
              }
              else
                  ++c;  
        }

        
        if(o1==0)
        {
            p[i].first.first = INT_MIN;
            p[i].first.second = INT_MIN;
        }
        else if(c1==0)
        {
            p[i].first.first = INT_MAX;
            p[i].first.second = INT_MAX;
        }
        else if(o1>c1)
        {
            p[i].first.first = INT_MAX-c1;
            p[i].first.second = INT_MIN+o1;
        }
        else if(o1<c1)
        {
            p[i].first.first = INT_MIN+o1;
            p[i].first.second = INT_MAX-c1;
        } 
        else
        {
            p[i].first.first = 0;
            p[i].first.second = 0;
        }

Now we want the strings having more number of unbalanced '(' on the left part of final string and the strings having more number of unbalanced ')' on the right part of the final string .The idea is similar to the above comment ,except o1 and o2 are calculated differently.Also for the case in which unbalanced '$$$($$$' are more than unbalanced '$$$)$$$' , we will put those first in which number of unbalanced '$$$)$$$' are less . For example $$$))(((($$$ will be placed before $$$))))(((((((((($$$ . Also $$$))((((($$$ will be placed before $$$))((($$$ . All other cases are symmetric if we see from right side.

We do that and we check if final string is balanced or not.

submission

It got AC as well as it is working on above example given by geeky.ass . I will be very happy if some one provides further any counter example .It also got accepted in almost same problem with better test cases .

→ Reply

akkipoonia

5 years ago, # |

problem F , need a counter example why my code fails=>https://atcoder.jp/contests/abc167/submissions/13105666

→ Reply

walleeva

5 years ago, # |

Detail explanation and code for C D and E

→ Reply

siddhugzp

5 years ago, # |

← Rev. 5 →

+26

Solution for F.

There are no good explanation in the comments. Also some of the wrong solution are getting accepted with some heuristics link . So I thought I would explain how I did it after 3 hours of struggling. And if anyone can counter my solution you are welcome. I will try to explain form the basics.

Let us first see the representation

For a single String i 1 ≤ i ≤ N

Let an a[N][2] array representing count of -

For String i a[i][0] denotes the maximum value count) in count ) - count ( brackets can reach while we are sweeping from left to right and a[i][1] denote the same for maximum ( while sweeping form right to left that is max count ( - count )

For example (()) -> a[i][0] and a[i][1] will both be 0 , ()) -> a[i][0] will be 1 and a[i][1] will be 0. ((( -> a[i][0] will be 0 and a[i][1] will be 3

If the final string formed after rearranging is T then for it to be perfect for any pos 1 ≤ pos ≤ N we should never encounter difference of count ( and count ) less than zero

Then make two sets of a[N][2]

First set containing a[i][1]-a[i][0] ≥ 0 let us denote it as S1

Second set containing the remaining elements that is a[i][1] - a[i][0] < 0 let us denote it as S2

Sort S1 according to the value of a[i][0] in increasing order Sort S2 according to the value of a[i][1] in decreasing order

Append the second set at the back of the first set

Initial let us denote the difference of ( and ) bracket by S then initially S=0 Sweep right form 1 to N

Subtract a[i][0]form S

check if S is less than zero then print No and return

add a[i][1] to S

If finally S is zero print Yes

Now why this works ?? I'm not sorting according to some difference of value of a[i][0] - a[i][1].

Explanation.

1 ) As you can see in the sorting order of S1 the value of S keeps on increasing it never decreases. This proves the fact that at any point we are using the maximum possible S - a[i][0] to be checked as less than 0 . Because a[i][0] is sorted in increasing order.

2 ) The second part is not that intuitive like why to sort S2 based on a[i][1] in decreasing order. To get the feel of it try imagining doing the same thing we did in the first part form backwards like taking the mirror image of the string we will have to do the same thing we did in the first part for S1. That is why it is sorted in decreasing order of arr[i][1]. I don't have any other way to explain what's going on in my mind other than this for the second part.

3) The S value should be equal to zero I mean that is but obvious .

→ Reply

hp1999

5 years ago, # ^ |

← Rev. 2 →

Well, I don't know what the editorial will say or if this approach is actually correct or not, but I just couldn't stop myself from commenting here that how simple yet beautiful this approach is (with your lucid explanation). My implementation for this approach: https://atcoder.jp/contests/abc167/submissions/13118554.

→ Reply

Thallium54

5 years ago, # |

Can anyone explain why this code works for problem F?

→ Reply

Saksham_2000

5 years ago, # |

can Anyone please explain to me the 2nd condition of problem E using an Example?. (adjacent pairs blah blah) I find it confusing.

→ Reply

Beyrad

5 years ago, # |

what is the solution for D?

→ Reply

beetroot

5 years ago, # ^ |

← Rev. 2 →

For D,you got to find a cycle(the cycle may not start from town 1) For example, if the given array is 6 5 2 5 3 2, then the cycle starts from town 2 ( 5-->3-->2). So first of all find the starting point of the cycle, and subtract the required number of steps to reach this starting point from k. Now you'll only move within the cycle. Since k can be large, take (k modulo cycle length). Lets say k modulo cycle length is x. Then obviously x<cycle length. So simply perform x steps. The town you land on is your answer.

Here's my code!

→ Reply

AMIT9019

5 years ago, # |

← Rev. 2 →

For F, I have taken array of pair and for each string given I keep in the array count of left and right braces which are unbalanced , and Then I sort the array considering the count of opening bracket and then considering the closing bracket. And then i took two variables l and r keeping track of opening bracket from starting and closing bracket from ending respectively. I started two fill the l and r from respective two sorted arrays and I think the approach is right because I Have tried almost all the test cases available in this blog for that question but not a single one has failed and also I am getting RE in few cases only not WA so the problem might be of implementation.. Can any one help.. Submission

→ Reply

bfx0215

5 years ago, # |

Can someone give me a counterexample to problem F? I tried all the counter examples in the comments, but they were all correct, thank you very much！ https://atcoder.jp/contests/abc167/submissions/13121322

→ Reply

bfx0215

5 years ago, # ^ |

I still can't find a counter example, I've tried all the cases the comments gave that could be wrong

→ Reply

bfx0215

5 years ago, # ^ |

+16

I got it !

→ Reply

Bakry

5 years ago, # |

+20

I think the test data is weak in problem F, many solutions got accepted are printing "No" in this case while the answer is "Yes". The test case:

4
((((
))))((
))(
)

→ Reply

5 years ago, # ^ |

+12

This is problem F with stronger tests: 101341A - Streets of Working Lanterns - 2, enjoy

→ Reply

It_Wasnt_Me

5 years ago, # ^ |

my code got AC on atcoder

But WA on test 71 in this problem

any idea what test 71 looks like ?

→ Reply

5 years ago, # ^ |

Test 71

Answer

YES
9 7 6 5 3 1 4 10 2 8

→ Reply

It_Wasnt_Me

5 years ago, # ^ |

Thanks got AC now on both

it turns out that what I have commented was the right xD

→ Reply

BumbleBee

5 years ago, # ^ |

Is it possible to allow access to all cases?
I already got AC, but I have a code that fails on case 45 and I couldn't figure out the bug in that code.

→ Reply

5 years ago, # ^ |

← Rev. 2 →

Test 45

BTW, the generator is very stupid for this problem:

void GenerateSequence(std::string &out, int len)
{
    if (len <= 0) {
        return;
    }
    if (rnd.next() < PARTITION_PROBABILITY) {
        int position = (rnd.next(0, len >> 1) << 1);
        GenerateSequence(out, position);
        GenerateSequence(out, len - position);
    } else {
        out.push_back(OPENINIG_BRACKET);
        GenerateSequence(out, len - 2);
        out.push_back(CLOSING_BRACKET);
    }
}

then swap / don't swap two random characters, then randomly cut the string to pieces.

So you can easily stress it locally.

If someone needs other tests, tell me your Polygon account.

→ Reply

BumbleBee

5 years ago, # ^ |

Thanks for the generator, I tried stress testing too, my generator couldn't find the case. Now I will try with this one.

→ Reply

verngutz

4 years ago, # ^ |

I got AC in both versions with the following wrong greedy: repeatedly append to the whole string the unused string which doesn't make the whole string irrecoverably unbalanced (too many unmatched closed parens), and with the highest number of unmatched open parens among all valid choices.

The counter case:

6
()(((())
)
()()(
(())))(
((
)))))((

→ Reply

4 years ago, # ^ |

I added your test and some more against your solution

→ Reply

CodeVid_19

5 years ago, # |

i am not able to find what is wrong with my code 4. Teleporter link of my soln is: https://atcoder.jp/contests/abc167/submissions/13078515 please mention testcase at which my code is wrong

→ Reply