### chokudai's blog

By chokudai, history, 17 months ago,

We will hold AtCoder Beginner Contest 167.

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

We are looking forward to your participation!

• +138

 » 17 months ago, # |   -16 No Comments on this blog . This is strange I guess
•  » » 17 months ago, # ^ |   -22 you did it
•  » » » 17 months ago, # ^ |   -11 ok
 » 17 months ago, # |   0 The contest will start in 2 mins!
•  » » 17 months ago, # ^ |   -7 It already started!
•  » » » 17 months ago, # ^ |   0 Thanks!
•  » » » 17 months ago, # ^ |   -17 Its already finished
 » 17 months ago, # |   0 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
•  » » 17 months ago, # ^ |   -17 In the Contest Page itself , after the contest AtCoder provides Tutorials for each problem in well descriptive way.
•  » » » 17 months ago, # ^ |   +7 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.
•  » » » » 17 months ago, # ^ |   0 can u send me the link to the atcoder tutorial (at least the Japanese one so that I can use google translate).
•  » » » » » 17 months ago, # ^ |   +1 In the contest page you will get a tab called "Editorial" whenever its available.
 » 17 months ago, # |   -14 Finally!Full sweep of the problem set (after some annoying debugging on F).
 » 17 months ago, # |   +20 F is interesting! get AC at the very last minute!
 » 17 months ago, # | ← Rev. 4 →   0 How to solve D? I was getting WA for last 4 test cases.
•  » » 17 months ago, # ^ |   -9 you have to get length of cycle in component containing 1
•  » » » 17 months ago, # ^ |   0 Can you tell me what's wrong here? submission
•  » » » » 17 months ago, # ^ |   0 its not always the case that you have to travel cycle atleast once
•  » » » » » 17 months ago, # ^ |   0 Thanks. Just added if(K<0) and AC. Man, wish it struck me.
•  » » » » » 17 months ago, # ^ |   0 What's wrong with my submission? Code link
•  » » » » » » 17 months ago, # ^ |   0  if(k<0){ cout<
•  » » » » » » » 17 months ago, # ^ |   0 Just failing on one test case...code.test : " sub1_01.txt "
•  » » » » » » » » 17 months ago, # ^ |   0 Datatype of k should be long long.
•  » » » » » » » » » 17 months ago, # ^ |   0 I have already... #define int long long 
•  » » » » » 17 months ago, # ^ |   0 Can you please check this solution of mine?https://atcoder.jp/contests/abc167/submissions/13089636
•  » » » » » » 17 months ago, # ^ |   0 Well, the TLEs are caused by find(hello.begin(), hello.end(), aaa);
•  » » 17 months ago, # ^ |   +2 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.
•  » » 17 months ago, # ^ |   +1 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
•  » » » 17 months ago, # ^ |   0 I didn't consider the case where k <= n, so WA on test37. What a pity.
•  » » 17 months ago, # ^ |   0 Overflow prob in mod. Was getting same bug until I switched to long longs.
•  » » 17 months ago, # ^ |   -6 You have to see what steps are repeating, and how many steps are non repeating. store both these kinds of steps. if k
•  » » 17 months 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
•  » » 17 months ago, # ^ |   +3 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.
•  » » 17 months 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.Here's a short implemenation.
•  » » 17 months ago, # ^ |   0 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
•  » » 17 months ago, # ^ | ← Rev. 3 →   0 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 understandHere is my implementation I have heavily commented it at so that you can understand easily
•  » » 17 months ago, # ^ | ← Rev. 12 →   0 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.
•  » » » 17 months ago, # ^ |   0 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 amI have been stuck. Please help anyone.my submission
•  » » » » 17 months ago, # ^ |   0 There must be some of by one error... What if k==l.length()?
•  » » » » » 17 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » » 17 months ago, # ^ |   0 test your code with: 1 10000 1
•  » » » » » » » 17 months ago, # ^ |   0 It's giving 1 as output.
•  » » 17 months ago, # ^ |   0 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 ..
 » 17 months ago, # |   +7 How to Solve E ?
•  » » 17 months ago, # ^ |   +15 loop k1=0 to k: ans+=c(n-1,k1)*m*(m-1)^(n-1-k1) 
•  » » » 17 months ago, # ^ |   +1 Why?
•  » » » » 17 months ago, # ^ |   0 explanation below
•  » » » 17 months 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.
•  » » » » 17 months ago, # ^ |   0 why c(n-1,k1)?? ... why not c(n,k1)??
•  » » » » » 17 months ago, # ^ |   +3 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.
•  » » » » » » 17 months ago, # ^ |   0 Ohh ... Thanks!
•  » » » » » 17 months ago, # ^ |   +3 pandastic is right about it below.
•  » » » » » 17 months ago, # ^ | ← Rev. 2 →   +6 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) :
•  » » » » » » 17 months ago, # ^ |   0 Bhai ye picture kaise banai?
•  » » » » » » » 17 months ago, # ^ |   +2 Online Ms paint, then upload that picture on some image hosting website and finally link that in the comment.
•  » » » » 17 months ago, # ^ |   0 I understand the idea but keep hitting TLEs. How can you computer "n-1 choose k1" efficiently?
•  » » » » » 17 months ago, # ^ |   +1 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)
•  » » » 17 months ago, # ^ |   +1 shouldn't it be (m — 1)^(k -1) instead ??
•  » » » » 17 months ago, # ^ |   0 After choosing k1 pairs, merge them and the problem reduce to: paint these segments such that adjacent segments having a different color. click here
•  » » » » » 17 months ago, # ^ |   0 merge with next element
•  » » » » » » 17 months ago, # ^ |   +1 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)
•  » » » » » » 17 months ago, # ^ |   0 Sorry ignore my doubts , i misread the statement, i thought only k should be differently colored. Thanks for the help tho.
•  » » » 17 months ago, # ^ |   0 Can you please explain what's wrong with my submission, I have done exactly the same thing https://atcoder.jp/contests/abc167/submissions/13111548
•  » » » » 17 months ago, # ^ |   0 count /= x -> WA count *= inv(x) -> AC where inv(x) is modular inverse of x And consider the case when x = 0
•  » » » » » 17 months ago, # ^ |   +1 AC thx mate.
•  » » » 17 months ago, # ^ |   0 (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 ?
•  » » » » 17 months ago, # ^ |   0 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) 
•  » » 17 months 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-kNow 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.
•  » » » 17 months ago, # ^ |   +1 Thanks ajit. Nicely explained. Now I am feeling sad that I was not able to solve it during contest .
•  » » » 17 months ago, # ^ | ← Rev. 2 →   0 could you explain why (n1-1)+(n2-1)+....+(np-1)<=k more?:)
•  » » » » 17 months ago, # ^ | ← Rev. 2 →   +3 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
•  » » » » » 17 months ago, # ^ |   +1 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?
•  » » » » » » 17 months ago, # ^ |   +2 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
•  » » » » » » » 17 months ago, # ^ |   0 Okay thanks!
•  » » » » 17 months ago, # ^ |   0 now I got it, Thank you for your help
•  » » » 17 months ago, # ^ | ← Rev. 2 →   0 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) ?
•  » » » » 17 months ago, # ^ | ← Rev. 4 →   +3 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 .
•  » » » » » 17 months ago, # ^ |   0 Now I am even more confused. :(
•  » » » » » » 17 months ago, # ^ |   0 Which part is confusing ?
•  » » » » » » » 17 months ago, # ^ |   0 Got it now, thanks :)
•  » » » 17 months ago, # ^ | ← Rev. 3 →   0 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.
 » 17 months ago, # |   +77 F was 1203F1 - Complete the Projects (easy version) in disguise..
•  » » 17 months ago, # ^ | ← Rev. 2 →   +31 Exact same problem: https://codeforces.com/gym/101341/problem/AEDIT: link to the editorial for this problem: https://codeforces.com/blog/entry/51445?#comment-393777
 » 17 months ago, # |   0 What sorting method works for F?
•  » » 17 months ago, # ^ |   0 difference of opening and closing brackets in non-decreasing order
•  » » » 17 months ago, # ^ | ← Rev. 2 →   0 how are you taking care of these cases)(()
•  » » » » 17 months ago, # ^ |   0 Put all the Open braces at first, and closing braces at last. For )( cases, sort them by https://codeforces.com/blog/entry/77148?#comment-619238 and put in between open and closed braces. If everything works out, put Yes.
•  » » » » » 17 months ago, # ^ |   0 Can we re arrange some string ? where is it written in statement?
•  » » » » » » 17 months ago, # ^ |   0 No, we can't re-arrange a particular string.
•  » » » » » 17 months 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?
•  » » » » » » 17 months ago, # ^ | ← Rev. 2 →   +25 Try this.3((((())))))(Your method gives No. But the answer is Yes
•  » » » » » » » 17 months ago, # ^ |   -10 Thanks!!
•  » » » » » » 17 months ago, # ^ |   +8 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.
•  » » » » » 17 months ago, # ^ |   0 I think this algo is wrong. Consider the following case: 4 ( )(( ))((((( ))))) Here your algo will give answer "No", but the correct answer is "Yes".
•  » » » » » » 17 months ago, # ^ |   +1 Right! That's why we need some hacking phase (and crowdsource some more test cases) :D Thanks for pointing out.
•  » » » » » » 17 months ago, # ^ |   0 My solution gives wrong answer in few test cases for the same problem. help me. Solution
•  » » » 17 months ago, # ^ |   0 CheldonShooper Can you please tell how did you think of this approach. I mean what was your intuition? Is it a well known problem? And madlad how did you know that this problem requires sorting for sure?
•  » » 17 months ago, # ^ |   -10 (A.openCount-A.closeCount) - (B.openCount-B.closeCount)
 » 17 months ago, # |   0 What are the difficulties of todays' problems in terms of codeforces ratings?
•  » » 17 months ago, # ^ | ← Rev. 2 →   -26 A,B,C < 1000D : 1200/1300E : 1500/1600F : 2000/2100
•  » » 17 months ago, # ^ |   +4 My best estimate:A — 600 B — 900 C — 1100 D — 1400 E — 1700 F — 2000Roughly, the gap in difficulty between the problems was the same.
 » 17 months ago, # |   +4 How to solve E?
•  » » 17 months 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.
•  » » » 17 months ago, # ^ |   0 Can you explain, how you got the formula?
•  » » » » 17 months ago, # ^ |   0 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.
•  » » » » » 17 months ago, # ^ |   0 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?
•  » » » » » » 17 months ago, # ^ | ← Rev. 2 →   +2 I try to break it downC(n-1,p) => number of ways to pick p items so that it has the same color as the item left to itConsider 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 colorNow 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 colorThus, 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)
•  » » » » » » » 17 months ago, # ^ |   0 thanks for your explanation
 » 17 months ago, # | ← Rev. 4 →   0 How to solve E ? Can someone hint me ? My approach with MLEint 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; } 
 » 17 months ago, # |   0 Can anyone explain approach for problem C.
•  » » 17 months ago, # ^ |   +3 You can bruteforce for all 2^n possibilies since n<=12.
•  » » » 17 months ago, # ^ |   0 hey, please tell how could one do it if the constraints are large ?
•  » » » » 17 months ago, # ^ |   -8 https://atcoder.jp/contests/abc167/submissions/13121855Look at the backtrack function, it generates all possible subsets, and then the solve() function checks if the books in the subset satisfy the condition
•  » » » » » 17 months ago, # ^ |   0 understood , thanks for the help !!
•  » » » » » » 17 months ago, # ^ |   0 abi gang :)
•  » » 17 months ago, # ^ |   0 recursion approch. check all posibilities, cauz constraint is very less(2^12)*12.
•  » » » 17 months ago, # ^ |   0 do it look like 2d knapsack?
•  » » » » 17 months ago, # ^ | ← Rev. 2 →   0 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;i0)return; } ans=Math.min(ans, sum); return; } for(int i=0;i
•  » » » » » 17 months ago, # ^ |   0 Thanks for the help Ritesh but if the constraint were big then should we use knapsack
•  » » » » » » 17 months ago, # ^ |   0 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;
•  » » » » » » » 17 months ago, # ^ |   0 tthanks bhaiya
•  » » 17 months ago, # ^ |   0 M and N were very small, so you were able to brute force and test every possible combination of books bought vs cost.
•  » » 17 months ago, # ^ | ← Rev. 2 →   +1 Use bitmask to consider all possibilities and update the minimum cost if it's valid.Submission
•  » » 17 months ago, # ^ |   +3 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.
•  » » 17 months ago, # ^ |   0 Just use brute force recursion. solution
•  » » » 17 months ago, # ^ | ← Rev. 2 →   0 Hey, thank you for posting your solution. I was going through it. On line 57 you have declared the size of 'cost' (M+1): vector cost(M+1,0);. Why you have not declared it of N or N+1?
•  » » » » 17 months ago, # ^ | ← Rev. 3 →   0 Apologies for not replying soon! The idea of cost vector was to represent the state that recursion tree is in after completing i iterations. So during the ith iteration we have 2 choices Add the ith row to the cost array Don't add it Now what should be the size of cost? Since we are adding a row to the cost vector, the cost vector should have the same size as the row i.e. no of columns in a row. What are the number of columns? -> M+1Remember that N is the no of rows.
•  » » » » » 17 months ago, # ^ |   0 Hey! I was up-solving some other problems so, couldn't find time to go through your comment. Now I understood what you're saying, thank you!
•  » » 17 months ago, # ^ |   0 Just a brute force for all 2^N combinations. My solution
•  » » 17 months ago, # ^ |   0 I used bf to find all possible combinations of books and printed the valid combination with least price.
•  » » 17 months ago, # ^ |   0 The idea is that you can select a certain number of books from n books in power(2,n) ways. Lets say you choose a certain set of books from those n books, then you have to check if those n books satisfy your criteria. The criteria is that those set of books must be able to increase your skill levels in each of those m algorithms above X. Also you store the total cost of buying those set of books. you repeat this for all such combinations and then simply output the least cost
•  » » 17 months ago, # ^ |   +1 I just used brute force. Try all possible subset of rows using bitmasks. The constraints imply this will fit within time.
 » 17 months ago, # |   0 by when will the editorials of contest be available?
•  » » 17 months ago, # ^ |   0 English Tutorials could take up to a week. Japanese tutorial should be available soon. Use use Google Translate, otherwise check here for solution.
•  » » 17 months ago, # ^ |   0 english editorial takes usually 2-3 days.
 » 17 months ago, # |   +28
•  » » 17 months ago, # ^ |   +7 Thanks for your solution but can I solve E with dp ?
•  » » » 17 months ago, # ^ |   +6 There is a O(nk) DP solution but it's not fast enough.
•  » » » » 17 months ago, # ^ | ← Rev. 4 →   +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])
•  » » » » » 17 months ago, # ^ | ← Rev. 2 →   +1 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 approachhttps://codeforces.com/blog/entry/77148?#comment-619369
•  » » » » » » 17 months ago, # ^ |   +3 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.
•  » » » » » » » 17 months ago, # ^ |   +18 Holy shit!!!! I am such a fool
•  » » » » » » » » 17 months ago, # ^ |   +1 The reaction to realization of truth ..
•  » » » » » » » 17 months ago, # ^ | ← Rev. 2 →   0 Hey can you please explain in brief what is wrong with this dp? I am unable to follow your conclusion.
•  » » » » » » » » 17 months ago, # ^ |   +4 N=8 K=1 aabccdee This is invalid. As total pairs are 3.
•  » » » » » » » 15 months ago, # ^ |   0 I'd been losing my mind for over a day trying to find an example that didn't work.. thank you for posting this lmaojust 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 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; } 
•  » » » » 17 months ago, # ^ |   0 Hey! stefdasca You can optimised the DP solution by storing previous k+1 sums. Can you please check the approach
•  » » » 17 months ago, # ^ |   0 I tried to do it with dp but could not reduce states. If somebody has done it using dp, please share the approach. Thanks
•  » » » » 17 months ago, # ^ |   0 My dp complexity is O(n ^ 3), how about you ? My codeint 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; } 
•  » » 17 months ago, # ^ | ← Rev. 2 →   0 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.
 » 17 months ago, # |   0 When are the editorials posted for these contests?
•  » » 17 months ago, # ^ |   0 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 :).
 » 17 months ago, # |   +7 A difficult version of D is here: https://cses.fi/problemset/task/1750Instead of starting at 1, start at a given X and solve the problem.
•  » » 17 months ago, # ^ |   +9 HintUse binary lifting.
 » 17 months ago, # |   +4 Why doesn't the relative sorting of strings work?Solution (Wrong on only 1 case)
•  » » 17 months ago, # ^ | ← Rev. 2 →   +3 ()((()))
•  » » 17 months ago, # ^ |   +3 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.
 » 17 months ago, # |   +8 Lol, read k adjacent pairs will have the same colors in E.
•  » » 17 months ago, # ^ |   +6 same :-( still around half of all test cases passed.
 » 17 months ago, # |   0 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?
•  » » 17 months ago, # ^ |   +1 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<
•  » » 17 months ago, # ^ |   0
 » 17 months ago, # |   +3 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.
•  » » 17 months 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?
•  » » 17 months ago, # ^ | ← Rev. 2 →   -8 Try the following test case :["(((", ")", ")))("]The correct answer is yesEDIT : Formatting
•  » » 17 months 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.
•  » » » 17 months ago, # ^ |   0 My solution gives wrong answer in few test cases for the same problem. help me. Solution
•  » » 17 months ago, # ^ | ← Rev. 3 →   0 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.
 » 17 months ago, # | ← Rev. 2 →   0 How to solve $C$ when $N$ is large?
•  » » 17 months ago, # ^ |   0
•  » » » 17 months ago, # ^ |   0 How do you choose which item to buy?
»
17 months 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;

}

•  » » 17 months ago, # ^ |   +5 you missed the case when k
•  » » » 17 months ago, # ^ |   0 thanks bro
 » 17 months ago, # |   +7
•  » » 17 months ago, # ^ |   +3 Very nicely written pls make of codeforces as well.
 » 17 months ago, # |   0 Can someOne explain me this solution for Dhttps://atcoder.jp/contests/abc167/submissions/13028277
•  » » 17 months ago, # ^ |   +6 Read about Binary Lifting.
 » 17 months ago, # |   0 Can anyone told me the problem in this code(Dth Problem), Only partial test cases are working in it13092124
 » 17 months ago, # | ← Rev. 2 →   +4 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
•  » » 17 months ago, # ^ | ← Rev. 2 →   0 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).
 » 17 months ago, # | ← Rev. 2 →   +3 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.
•  » » 17 months ago, # ^ |   +3 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.
•  » » 17 months ago, # ^ |   0
•  » » » 17 months ago, # ^ |   0 I checked and it passes that case.
 » 17 months ago, # |   0 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!
•  » » 17 months ago, # ^ |   +1 Testcases are available at this link after some days https://www.dropbox.com/sh/arnpe0ef5wds8cv/AAAk_SECQ2Nc6SVGii3rHX6Fa?dl=0
 » 17 months ago, # | ← Rev. 2 →   0 Can anyone help me with problem C (Skill Up). Problem
•  » » 17 months ago, # ^ |   0 Use brute force over all 2^n possibilities. I use bitmask to do so. https://atcoder.jp/contests/abc167/submissions/13070747
•  » » » 17 months ago, # ^ |   0 please explain the way to do so
•  » » 17 months ago, # ^ |   0 0/1 knapsake also works
 » 17 months ago, # |   0 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; } 
•  » » 17 months ago, # ^ |   0 Can someone please point out where am I going wrong?
•  » » » 17 months ago, # ^ | ← Rev. 3 →   +1 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.
•  » » » » 17 months ago, # ^ | ← Rev. 2 →   0 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). 
•  » » » » » 17 months ago, # ^ |   0 Thanks for pointing out. I think misunderstood the problem.
 » 17 months ago, # |   +5 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??
•  » » 17 months ago, # ^ |   +12 Maybe atcoder+300 == codeforces
 » 17 months ago, # |   0 Hello. Can anyone give ideas on how to write a choose function that computes large values of C(c,r)%m quickly? Thanks.
•  » » 17 months ago, # ^ |   0 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
•  » » 17 months ago, # ^ |   0
 » 17 months ago, # |   0 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.
 » 17 months ago, # |   0 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.
 » 17 months ago, # |   0 Can someone explain me what is wrong in my D code? #include using namespace std; #define forr(i,a,n) for(long long int i=a; i=n; i--) vector v(300000), ans, ans2,ans3; int vis[300000], vis2[300000]; int main() { ios_base :: sync_with_stdio(false),cin.tie(NULL),cout.tie(0); long long int a,b; cin>>a>>b; forr(i,1,a+1) { long long int x; cin>>x; v[i]=x; } int k=1,flag=0; ans.push_back(1); vis[1]++; while(1) { if(flag) vis[k]++; if(vis[k]==3) break; ans.push_back(v[k]); k=v[k]; flag=1; } forr(i,0,ans.size()) { if((vis[ans[i]]==2 or vis[ans[i]]==3) and !vis2[ans[i]]) ans3.push_back(ans[i]), vis2[ans[i]]=1; else if(vis[ans[i]]==1 and !vis2[ans[i]]) ans2.push_back(ans[i]), vis2[ans[i]]=1; } if(ans2.size()>=b) cout<
 » 17 months ago, # |   0 please explain what is the error in my code for problem F? https://atcoder.jp/contests/abc167/submissions/13096927
•  » » 17 months ago, # ^ |   0 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.
 » 17 months ago, # |   0 https://atcoder.jp/contests/abc167/submissions/13098882Can anybody please tell me the error in my code. A test case would be better.
 » 17 months ago, # | ← Rev. 8 →   +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 ((((( )))))(((((((( ))))))(((((((((( )))))))))))) 
•  » » 17 months ago, # ^ |   -25 r*ndi rona mat kar. AC mil gya na toh khush reh.
•  » » 17 months ago, # ^ |   0 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.
•  » » » 17 months ago, # ^ | ← Rev. 3 →   0 If you have solutions then please share link to your code.Update: aren't you suggesting O(n^2) solution?
•  » » » » 17 months ago, # ^ |   0 This one looks good https://codeforces.com/blog/entry/77148?#comment-619641
•  » » » » » 17 months ago, # ^ |   0 Please see this . I think it is correct .
 » 17 months ago, # |   -16 how to solve A ?
•  » » 17 months ago, # ^ |   +40 Learn FFT
 » 17 months ago, # |   +4 Testcase for F was very weak. AC code: https://atcoder.jp/contests/abc167/submissions/13063944 which fails on the TC:5()(()(())(((()))))Answer should be Yes but AC solution gives No.
 » 17 months ago, # |   +3 can anybody tell me what is wrong in my submission of d . It is just failing for some testcases
•  » » 17 months ago, # ^ |   +3 Ah, How can we know whats wrong in your code if you will not give the link
•  » » 17 months ago, # ^ |   +5 ur name should be kunal kamra
 » 17 months ago, # |   0 for problem B: I cant get the idea why he use it: if((bit >> i) & 1) { price += c[i]; for(int j = 0; j < m; j++) { understood[j] += a[i][j]; } }I understand that we check all 2^n combination. but how this code helps here? here is the full code: https://ideone.com/9DsLpo
•  » » 17 months ago, # ^ |   0 got it. bitmasking.
 » 17 months ago, # | ← Rev. 3 →   0 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
•  » » 17 months ago, # ^ |   +8 try this3 (((( ))) ))( 
•  » » » 17 months ago, # ^ |   0 got it. thanks!
 » 17 months ago, # | ← Rev. 6 →   +4 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(oc$, 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 •  » » 17 months ago, # ^ | ← Rev. 3 → 0 Shouldn't the following test case output "Yes"? (by arranging them in the given order) 4 ( )(((()) ))((( ))) I got "No" from your code •  » » » 17 months ago, # ^ | ← Rev. 8 → 0 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=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
 » 17 months ago, # |   0 problem F , need a counter example why my code fails=>https://atcoder.jp/contests/abc167/submissions/13105666
 » 17 months ago, # |   0 Detail explanation and code for C D and E
 » 17 months 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 ≤ NLet 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 3If 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 zeroThen make two sets of a[N][2]First set containing a[i][1]-a[i][0] ≥ 0 let us denote it as S1Second set containing the remaining elements that is a[i][1] - a[i][0] < 0 let us denote it as S2Sort S1 according to the value of a[i][0] in increasing order Sort S2 according to the value of a[i][1] in decreasing orderAppend the second set at the back of the first setInitial let us denote the difference of ( and ) bracket by S then initially S=0 Sweep right form 1 to NSubtract a[i][0]form Scheck if S is less than zero then print No and return add a[i][1] to S If finally S is zero print YesNow 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 .
•  » » 17 months ago, # ^ | ← Rev. 2 →   +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.
 » 17 months ago, # |   0 Can anyone explain why this code works for problem F?
 » 17 months ago, # |   +1 can Anyone please explain to me the 2nd condition of problem E using an Example?. (adjacent pairs blah blah) I find it confusing.
 » 17 months ago, # |   0 what is the solution for D?
•  » » 17 months ago, # ^ | ← Rev. 2 →   0 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
 » 17 months ago, # | ← Rev. 2 →   0 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
 » 17 months ago, # |   0 Can anyone please help me in finding the bug in my approach for solving problem D?https://atcoder.jp/contests/abc167/submissions/13089636
 » 17 months ago, # |   0 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
•  » » 17 months ago, # ^ |   0 I still can't find a counter example, I've tried all the cases the comments gave that could be wrong
•  » » » 17 months ago, # ^ |   +16 I got it !
 » 17 months 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 (((( ))))(( ))( ) 
•  » » 17 months ago, # ^ |   +12 This is problem F with stronger tests: 101341A - Streets of Working Lanterns - 2, enjoy
•  » » » 17 months ago, # ^ |   +5 my code got AC on atcoder But WA on test 71 in this problemany idea what test 71 looks like ?
•  » » » » 17 months ago, # ^ |   +1 Test 71 AnswerYES 9 7 6 5 3 1 4 10 2 8 
•  » » » » » 17 months ago, # ^ |   0 Thanks got AC now on both it turns out that what I have commented was the right xD
•  » » » » » 17 months ago, # ^ |   0 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.
•  » » » » » » 17 months ago, # ^ | ← Rev. 2 →   +1 Test 45BTW, 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.
•  » » » » » » » 17 months ago, # ^ |   0 Thanks for the generator, I tried stress testing too, my generator couldn't find the case. Now I will try with this one.
•  » » » 15 months ago, # ^ |   0 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 ()(((()) ) ()()( (())))( (( )))))(( 
•  » » » » 15 months ago, # ^ |   0 I added your test and some more against your solution
 » 17 months ago, # |   0 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
•  » » 17 months ago, # ^ |   0 First of all you exceed the limited size of your array by one. ll a[n]; for(ll i=1;i<=n;i++) { cin >> a[i]; } `
 » 17 months ago, # |   0 hello I have a couple questions on Task C and Task D Can anyone please help me with my code by showing me a counter-case?here is my code for Task C (Skill Up): https://www.ideone.com/dXAF93 I am getting WA for this. I don't understand why...I am sorry.here is my code for Task D (Teleporter): https://www.ideone.com/83lldq I am getting TLE for this. I thought the longest pattern would be 2*10^5, and maybe I could get to the final destination in time..Much appreciated in advance.
 » 17 months ago, # |   +8 when will the editorial be published?
 » 17 months ago, # |   0 https://atcoder.jp/contests/abc167/submissions/13005847 Can anyone help me to understand what he did in the line 25 to 27??
 » 17 months ago, # |   0 chokudai, is there any chance some day there is different time for any of the AtCoder contest? That is so sad that in our time zone atcoder contests starts at 5am. AtCoder is becoming more popular with the community, so some time rotation would be amazing.
 » 17 months ago, # | ← Rev. 2 →   0 For those who is struggling on Teleporter, here's my solution with explanation: https://github.com/wingkwong/competitive-programming/blob/master/atcoder/contests/abc167/D.cpp
 » 17 months ago, # |   0 Too weak pretests in problem F, you can solve this problem by len(s) ^ 2.
 » 17 months ago, # |   0 can someone please explain problem statement of E, specifically this line "We will consider two ways to paint the blocks different if and only if there is a block painted in different colors in those two ways."
 » 17 months ago, # |   0 Guys urgent...I think 168 clashes with kickstart!!!
 » 17 months ago, # |   0 Atcoder Beginner Contest 168 is clashing with Google kickstart Round C. Please look into this matter.
 » 17 months ago, # | ← Rev. 2 →   0 https://atcoder.jp/contests/abc167/submissions/13258356 whats wrong with this solution?? F-Bracket sequencing