### M.Mahdi's blog

By M.Mahdi, 4 years ago,

Hi again!

If you notice typos or errors, please send a private message.

### 688A: Opponents

#### Solution

Let's find out for each row of the given matrix if it is completely consisting of ones or not. Make another array canWin, and set canWini equal to one if the i-th row consists at least one zero. Then the problem is to find the maximum subsegment of canWin array, consisting only ones. It can be solved by finding for each element of canWin, the closest zero to it from left. The complexity of this solution is O(nd), but the limits allow you to solve the problem in O(nd2) by iterating over all possible subsegments and check if each one of them is full of ones or not.

C++ code
Python code

### 688B: Lovely Palindromes

#### Hint

Try to characterize even-length palindrome numbers.

#### Solution

For simplifications, in the following solution we define lovely integer as an even-length positive palindrome number.

An even-length positive integer is lovely if and only if the first half of its digits is equal to the reverse of the second half.

So if a and b are two different 2k-digit lovely numbers, then the first k digits of a and b differ in at least one position.

So a is smaller than b if and only if the first half of a is smaller than the the first half of b.

Another useful fact: The first half of a a lovely number can be any arbitrary positive integer.

Using the above facts, it's easy to find the first half of the n-th lovely number — it exactly equals to integer n. When we know the first half of a lovely number, we can concatenate it with its reverse to restore the lovely integer. To sum up, the answer can be made by concatenating n and it's reverse together.

The complexity of this solution is .

C++ code
Python code

#### Challenge

What if you were asked to find n-th positive palindrome number? (1 ≤ n ≤ 1018)

### 687A: NP-Hard Problem

#### Hint

Try to use all of the vertices. Then look at the two vertex covers together in the graph and see how it looks like.

#### Solution

Looking at the two vertex covers in the graph, you see there must be no edge uv that u and v are in the same vertex cover. So the two vertex covers form a bipartition of the graph, so the graph have to be bipartite. And being bipartite is also sufficient, you can use each part as a vertex cover. Bipartition can be found using your favorite graph traversing algorithm(BFS or DFS). Here is a tutorial for bipartition of undirected graphs.

The complexity is O(n + m).

C++ code

#### Challenge

In the same constraints, what if you were asked to give two disjoint edge covers from the given graph? (The edge covers must be edges-disjoint but they can have common vertex.)

### 687B: Remainders Game

#### Hint

Assume the answer of a test is No. There must exist a pair of integers x1 and x2 such that both of them have the same remainders after dividing by any ci, but they differ in remainders after dividing by k. Find more facts about x1 and x2!

#### Solution

Consider the x1 and x2 from the hint part. We have x1 - x2 ≡ 0 () for each 1 ≤ i ≤ n.

So:

We also have (). As a result:

We've found a necessary condition. And I have to tell you it's also sufficient!

Assume , we are going to prove there exists x1, x2 such that x1 - x2 ≡ 0 () (for each 1 ≤ i ≤ n), and ().

A possible solution is x1 = lcm(c1, c2, ..., cn) and x2 = 2 × lcm(c1, c2, ..., cn), so the sufficiency is also proved.

So you have to check if lcm(c1, c2, ..., cn) is divisible by k, which could be done using prime factorization of k and ci values.

For each integer x smaller than MAXC, find it's greatest prime divisor gpdx using sieve of Eratosthenes in .

Then using gpd array, you can write the value of each coin as p1q1p2q2...pmqm where pi is a prime integer and 1 ≤ qi holds. This could be done in by moving from ci to and adding gpdci to the answer. And you can factorize k by the same way. Now for every prime p that , see if there exists any coin i that the power of p in the factorization of ci is not smaller than the power of p in the factorization of k.

Complexity is .

C++ code

And a nice implementation by Reyna: 18789803

### 687C: The values you can make

#### Hint

Use dynamic programming.

#### Solution

Let dpi, j, k be true if and only if there exists a subset of the first i coins with sum j, that has a subset with sum k. There are 3 cases to handle:

• The i-th coin is not used in the subsets.
• The i-th coin is used in the subset to make j, but it's not used in the subset of this subset.
• The i-th coin is used in both subsets.

So dpi, j, k is equal to dpi - 1, j, k OR dpi - 1, j - ci, k OR dpi - 1, j - ci, k - ci.

The complexity is O(nk2).

C++ code

#### Challenge

In the same constraints, output the numbers you can never not make! Formally, the values x such that for every subset of coins with the sum k, there exists a subset of this subset with the sum x.

### 687D: Dividing Kingdom II

Unfortunately, our mistake in setting the constrains for this problem made it possible to get Ac with O(qm) solution. We hope you accept our apology.

#### Hint

Consider the following algorithm to answer a single query: Sort the edges and add them one by one to the graph in decreasing order of their weights. The answer is weight of the first edge, which makes an odd cycle in the graph. Now show that there are only O(n) effective edges, which removing them may change the answer of the query. Use this idea to optimize your solution.

#### Solution

First, let’s solve a single query separately. Sort edges from interval [l, r] in decreasing order of weights. Using dsu, we can find longest prefix of these edges, which doesn’t contains odd cycle. (Graph will be bipartite after adding these edges.) The answer will be weight of the next edge. (We call this edge “bottleneck”).

Why it's correct? Because if the answer is w, then the we can divide the graph in a way that none of the edges in the same part have value greater than w. So the graph induced by the edges with value greater than w must be bipartite. And if this graph is bipartite, then we can divide the graph into two parts as the bipartition, so no edge with value greater than w will be in the same part, and the answer is at most w.

Let's have a look at this algorithm in more details. For each vertex, we keep two values in dsu: Its parent and if its part differs from its parent or not. We keep the second value equal to "parity of length of the path in original graph, between this node and its parent". We can divide the graph anytime into two parts, walking from one vertex to its parent and after reaching the root, see if the starting vertex must be in the same part as the root or not.

In every connected component, there must not exist any edge with endpoints in the same part.

After sorting the edges, there are 3 possible situations for an edge when we are adding it to the graph:

1. The endpoints of this edge are between two different components of the current graph. Now we must merge these two components, and update the part of the root of one of the components.

2. The endpoints of this edge are in the same component of the current graph, and they are in different parts of this component. There is nothing to do.

3. The endpoints of this edge are in the same component of the current graph, and they are also in the same part of this component. This edge is the "bottleneck" and we can't keep our graph bipartite after adding it, so we terminate the algorithm.

We call the edges of the first and the third type "valuable edges".

The key observation is: If we run above algorithm on the valuable edges, the answer remains the same.

Proof idea: The edges of the first type are spanning trees of connected components of the graph, and with a spanning tree of a bipartite graph, we can uniquely determine if two vertices are in the same part or not.

So if we can ignore all other edges and run our algorithm on these valuable edges, we have O(n) edges instead of original O(n2) and the answer is the same.

We answer the queries using a segment tree on the edges. In each node of this tree, we run the above algorithm and memorize the valuable edges. By implementing carefully (described here), making the segment tree could be done in .

Now for each query [l, r], you can decompose [l, r] into segments in segment tree and each one has O(n) valuable edges. Running the naive algorithm on these edges lead to an solution for each query, which fits in time limit.

C++ code

### 687E: TOF

#### Hint: What the actual problem is

Looking at the code in the statement, you can see only the first edge in neighbors of each node is important. So for each vertex with at least one outgoing edge, you have to choose one edge and ignore the others. After this the graph becomes in the shape of some cycles with possible branches, and some paths. The number of dfs calls equals to 998 × ( sum of sizes of cycles ) + n +  number of cycles.

#### Solution

The goal is to minimize the sum of cycle sizes. Or, to maximize the number of vertices which are not in any cycle. Name them good vertices.

• If there exists a vertex v without any outgoing edge, we can make all of the vertices that v is reachable from them good. Consider the dfs-tree from v in the reverse graph. You can choose the edge from this tree as the first edge in neighbors[u], in order to make all of these vertices good.

• Vertices which are not in the sink strongly connected components could become good too, by choosing the edges from a path starting from them and ending in a sink strongly connected component.

• In a sink strongly connected component, there exists a path from every vertex to others. So we can make every vertex good except a single cycle, by choosing the edges in the paths from other nodes to this cycle and the cycle edges.

So, every vertices could become good except a single cycle in every sink strongly connected component. And the length of those cycles must be minimized, so we can choose the smallest cycle in every sink strongly connected component and make every other vertices good. Finding the smallest cycle in a graph with n-vertex and m edges could be done in O(n(n + m)) with running a BFS from every vertex, so finding the smallest cycle in every sink strongly connected component is O(n(n + m)) overall.

C++ code

#### Challenge

What if the target function is reversed? It means you have to choose a single outgoing edge from every node with at least one outgoing edge, and maximize the sum of cycle sizes in the chosen graph.

I thought about this one a lot but can't find any solution. Do you have any idea?

Tutorial of Practice Round

• +94

 » 4 years ago, # |   +27 Its round 360 not 300
•  » » 4 years ago, # ^ |   +30 Fixed. Thanks!
 » 4 years ago, # |   0 can u explain me 687B: Remainders Game with more breifly....................
•  » » 4 years ago, # ^ |   +12 From chinese theorem (https://en.wikipedia.org/wiki/Chinese_remainder_theorem), we know that if we know the values of x%a and x%b, then we know for sure x%lcm(a, b). So in our problem if we take x%c1, x%c2 ... x%cn, if we know these values as problems says, then we know x%lcm(all ci), so if we know that value we know also x%lcm(ci)%K, so we need to check if K / lcm(all ci) is regular division with no remainder. Because of overflow we can't calculate lcm(), so we need prime factorization(I am not going to explain it now, but if you have any problem comment below)
•  » » » 4 years ago, # ^ |   0 thanx alot.........
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +4 Wikipedia said that the numbers ci should be coprime, but in the problem there is not that restriction. Does it matters?
•  » » » » 4 years ago, # ^ |   +9 Wikipedia also says that if numbers ci are not pairwise coprime then all solutions to the congruence system are congruent modulo . Check again.
•  » » » » » 4 years ago, # ^ |   0 Sorry but I cannot find that sentence, can you help me please :'(
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +1 I tried to calculate LCM (c1, c2,... cn) but unfortunately the number overflowed and I got WA. In other words, I wanted to check if the LCM is a multiple of k or: GCD (LCM(c1, c2, ... cn), K) = K ?Some accepted solutions calculate it as LCM (GCD(c1, k), GCD(c2, k), ... GCD(cn, k)) = K ?I don't understand how both equations are equivalent?
•  » » » » 4 years ago, # ^ |   0 Even i leart this after the contest:http://www.cut-the-knot.org/arithmetic/GcdLcmProperties.shtml
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +17 Here's another way of thinking: LCM = union of prime factors. GCD = intersection of prime factors. We need to test if LCM(c1, ..., cn) % K == 0 so this is equivalent to the LCM containing all prime factors of k: intersect(pfactors(k), union(pfactors(c1), ..., pfactors(cn))) == pfactors(k) but we don't have to take union before intersection — we can first use intersection to kill off ones that are not prime factors of k, and then taking the union.
•  » » » 4 years ago, # ^ |   0 I got till the part where you have written that if we know x%lcm(all ci), then we know also x%lcm(ci)%K . But I couldn't understand the logic of next statement. Why should we check k/lcm(all ci). Can you please explain.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +14 Further descriptions added to the tutorial.
•  » » » 4 years ago, # ^ |   +3 thanx sir...
 » 4 years ago, # |   0 Thank u for the editorial. I've been waited for a long time.
 » 4 years ago, # |   0 687B - Remainders Game can be solved using only ints. See 18807557 (solve() at the bottom).
 » 4 years ago, # |   +9 why the time complexity of problem 688B is O(logn)?
•  » » 4 years ago, # ^ |   -10 I think that's just a typo, it should be O(n)
•  » » » 4 years ago, # ^ |   +19 You are iterating over the digits of the number..not the number itself. That is why, its O(logn).
•  » » » » 4 years ago, # ^ |   0 yeah, you are right.
•  » » 4 years ago, # ^ |   +2 Because it's O(length).
•  » » 4 years ago, # ^ |   +1 I think n is the number itself, not the number of digits of the number. The solution takes time proportional to the number of digits, and the number of digits is proportional to logn.
•  » » » 4 years ago, # ^ |   0 i got that, TYSM.
•  » » » 4 years ago, # ^ |   0 omg, what a silly question. :(
•  » » » » 4 years ago, # ^ |   0 No not really, actually that same question came up for me too!
 » 4 years ago, # |   +6 This is how one should write editorials. Thanks :)
 » 4 years ago, # |   0 Could you please explain div1 D? I totally don't understand why the answer to a single query is the first edge in sorted order which turns graph into not bipartite? How do we actually divide the graph?
•  » » 4 years ago, # ^ |   +8 Further descriptions added to the tutorial. I hope it's clear now.
•  » » » 4 years ago, # ^ |   0 Thanks, I somehow thought that we need to sort in ascending order and I couldn't understand how it could be true. Now it's totally clear.
 » 4 years ago, # | ← Rev. 2 →   0 Div2A can be done in O(n) using idea of kadane's algorithom .... Edit: i think i forgot to calculate complexity of strst() then it will be O(n^2) right?
 » 4 years ago, # | ← Rev. 3 →   +26 Time Limit for 1B Even the author's solution TLEs with just cin and takes 900 ms with optimized cin. In problems which such large input (106 integers), doesn't it make sense to keep the TL greater than 1 second? I'm sure inefficient solutions would not pass even if TL was kept at 1.5 - 2 seconds instead of 1 second. Also, if the official solution takes 900 ms with cin and ios :: sync_with_stdio(false), shouldn't TL be at-least twice that time? Further, there wasn't a maxtest in the pretest or a warning in the question to necessarily use scanf. You might argue that there is a "lesson" to learn from all this : But the fact remains that, every once in a while when we encounter such problems, there will always be a bunch of users who will have to suffer due to this. Many people find it convenient to use optimized cin instead of scanf as it works fine for almost all problems.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +24 You are right. We're sorry about this.This happened because our C++ and java implementations work under the half of the time limit, so we didn't noticed this during the preparation. It's definitely an issue, I will pay attention to this from now on whenever I prepare a problem.
•  » » 4 years ago, # ^ |   +1 There shouldn't be a problem where scanf passes and cin doesn't, I agree.But I can't say I understand the other side either: if you know this problem exists, why risk a whole problem because you think cin >> a is prettier than scanf ("%d", &a)?
•  » » » 4 years ago, # ^ |   +12 No one really decides to "risk the problem because cin is prettier" you now — many people who prefer cin/cout know about the issue, but it's easy to forget that in every problem with a O(n) solution you have to check if the constaints were made 106 instead of 2·105 and input/output becomes a bottleneck,
•  » » » » 4 years ago, # ^ |   +26 That's my point — if you always use scanf, then you don't need to check anything. If you prefer cin anyway, then you are taking risks just because it's prettier.
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   +11 Starting to use scanf and printf also has its own side-effects. In Yandex Elimination Round I wrote a code for a problem and just right before submitting it (blind, without verdict), I changed cin cout to scanf printf and WRONG.... Cause output was long long and I used %d as output specifier. Also in Round 348, I used cin/cout with ios:sync_with_stdio(false) and got TLE. The fact was that I even didn't imagine that solution with these optimizations get TLE and I think it is definitely problem setters fault. (And the same goes for this contest too that my B failed because of this)
•  » » » 4 years ago, # ^ |   +5 Yesterday I didn't even think about using scanf. I just wanted to solve the problem fast, and I always use optimized cin, so I just did that and submitted. A few minutes before the contest ended, I realized that N = 106 and TL = 1s might be a problem. My code had passed the pretests comfortably, so I did not bother resubmitting...
 » 4 years ago, # | ← Rev. 2 →   -33 Problem in lovely Pallindrome I submitted this code in java , but it shows run time error on testcase 8 , but i submitted the same code in C++ , it passes all testcases . I have just started competitive programming please help , i am not able to find what going wrong ? import java.util.*; import java.io.*; public class Main{ public static String reverseIt(String str){ String newStr = ""; for (int i=0;i < str.length();i++){ newStr = str.charAt(i) + newStr; } return newStr; } public static void main(String[] args) { MyScanner sc = new MyScanner(); out = new PrintWriter(new BufferedOutputStream(System.out)); String str = sc.next(); String newStr = reverseIt(str); newStr = str + newStr; out.println(newStr); out.close(); } //-----------PrintWriter for faster output--------------------------------- public static PrintWriter out; //-----------MyScanner class for faster input---------- public static class MyScanner { BufferedReader br; StringTokenizer st; public MyScanner() { br = new BufferedReader(new InputStreamReader(System.in)); } String next() { while (st == null || !st.hasMoreElements()) { try { st = new StringTokenizer(br.readLine()); } catch (IOException e) { e.printStackTrace(); } } return st.nextToken(); } int nextInt() { return Integer.parseInt(next()); } long nextLong() { return Long.parseLong(next()); } double nextDouble() { return Double.parseDouble(next()); } String nextLine(){ String str = ""; try { str = br.readLine(); } catch (IOException e) { e.printStackTrace(); } return str; } } } 
•  » » 4 years ago, # ^ | ← Rev. 2 →   +12 First of all, please don't paste code here, you can paste your code on pastebin and post a link here or add a link to your submission.And in your reverse function, you are adding a new character to the beginning of the string for the whole length of the original string. So, every time before adding a character all the characters are first shifted to the right by 1 place and then the new character is added in the first place. So, this has a running time of O(n^2) where n is the length of the string.You should instead traverse the string while swapping the i'th characters from the beginning and the ending, where 0 <= i <= n / 2.And you don't even need to write the code for this as you can use Java's StringBuilder class to do this. I hope this helps :)Edit : You can see how easy the code becomes using StringBuilder — String s = in.next(); out.println(s + new StringBuilder(s).reverse().toString());This is the main code I wrote for the question :)
•  » » » 4 years ago, # ^ |   +6 Thanks a lot for your reply . Okay from now on , i will use pastebin .
•  » » » 4 years ago, # ^ |   0 Thanks a lot brother . In C++, i coded it the same way & it was accepted . Can you please enlighten ? And is it the right to take input ? (the way i have done ) .
•  » » » » 4 years ago, # ^ |   0 In C++ the code got accepted as C++ is faster than Java, about 2 times as fast usually.As you can see, even your C++ code took almost 500ms to execute so most probably your java solution also would've passed had the time limit been a little more than 1 sec.And yes you can take input either the way you have done or by taking input character by character and then forming the variable of required data type with them, which is a little faster than your method. But even your method is very fast and you mostly should never have any time limit problem because of it.
•  » » » » » 4 years ago, # ^ |   0 Thanks a lot again , for the prompt reply .
 » 4 years ago, # | ← Rev. 7 →   -37 Your Delay of publishing editorial prove you work at ysc and the delay of the second phase result of INOI is your fault.P.S: INOI is iran national olympiad that M.Mahdi delay the publishing result about 2 months... still waiting!P.S2: I'm using fake account, If I sent this with my own account he kills me.
•  » » 4 years ago, # ^ |   +19 Why using fake account???Be a man, and die standing :D
 » 4 years ago, # |   0 Thank you!
 » 4 years ago, # | ← Rev. 2 →   0 Edit : Figured it out. Can someone clarify the meaning of valuable edges in the editorial for Div1 D: "The edges which adding them makes change in our dsu and the bottleneck edge"
•  » » 4 years ago, # ^ |   0 Hi, I am also confused about this. What does it mean by valuable edges in div1 D, and how do you find them efficiently?
•  » » 4 years ago, # ^ |   +3 Updated. It's in more details now.
 » 4 years ago, # |   +9 M.Mahdi can you please look at the line "So you have to check if K is divisible by lcm(c1, c2, ..., cn), which could be done using prime factorization of k and ci values." in the solution of 687B: Remainders Game as I think it is slightly confusing because we need to check whether "lcm(c1, c2, ..., cn) is divisible by K" instead of K is divisible by lcm(c1, c2, ..., cn).
•  » » 4 years ago, # ^ |   0 It's fixed now. Thanks!
•  » » » 4 years ago, # ^ |   0 You should fix the formula standing after phrase "As a result: ..." too.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +8 No, its Correct! notice that when the answer in "NO" then k shouldn't be divisor of lcm(c1, c2, ..., ck)
 » 4 years ago, # | ← Rev. 2 →   -8 Is complexity of Div2B log(n) with root 2 or 10?
•  » » 4 years ago, # ^ |   -7 Is log10(n). You have to make linear operations in the lenght of the string, and the string given can have up to 100000 digits, so it shoud be more or less 100000 operations.
•  » » » 4 years ago, # ^ |   0 this is maybe a very dumb question, but please answer. why up to 100000 digits? if my eyes don't deceive me, the range of input is 1<=n<=10^100000 not 1<=n<=10^5 thank you
•  » » » » 4 years ago, # ^ |   0 The number of digits in 10^x is (x+1)
•  » » » » » 4 years ago, # ^ |   0 ohh... i get it. thanks
 » 4 years ago, # |   +2 Why x1 - x2|lcm(c1, c2, ...) ? Wouldn't it be the oposite?
•  » » 4 years ago, # ^ |   0 I have the exact same doubt dude!! because x1-x2 can take values of [0->Inf]*lcm(c1,c2,....);
•  » » 4 years ago, # ^ |   +1 Yes, it's fixed now. Thanks!
•  » » » 4 years ago, # ^ |   0 Thanks for fixing it dude, It really bugged me for a while now :P
 » 4 years ago, # |   +1 Can anyone explain the idea of div1 C?
 » 4 years ago, # | ← Rev. 3 →   0 pls HELP. In problem DIV2E The values you can make,I am using the same approach as in the editorial but getting memory limit exceeded since i am using array dp[501][501][501] .How can i make changes to my code such that it passes the memory limit. My submission: http://codeforces.com/contest/687/submission/18829433 M.Mahdi EDIT 1:Got AC after using short int. EDIT 2:This can also be solved using in O(k^k) since we need only the last layer.
•  » » 4 years ago, # ^ |   +1 You can use vectors instead of arrays; or use maps or sets. The idea is to use dynamic memory instead of static memory. Anyways you can check the solution of the problem setter and see how to use less memory. (O(k*k) instead of O(n*k*k))
•  » » 4 years ago, # ^ |   +8 Just use short or char instead of int. You don't need values up to 2^31.
•  » » » 4 years ago, # ^ |   +3 Got AC after using short int .Thnks. http://codeforces.com/contest/688/submission/18836648
•  » » 4 years ago, # ^ |   +7 You need only last layer of dp.
•  » » » 4 years ago, # ^ |   0 Yes we need only the last layer .BTW got AC after using short int
•  » » 4 years ago, # ^ |   0 Time Complexity will be O(n*k*k) not O(k*k) but space complexity will be reduced to O(k*k) if we use last layer.
 » 4 years ago, # |   +3 "In a sink strongly connected component" — do you mean "in a single strongly connected component"? That part was a bit confusing to me.But otherwise, thanks for the editorial!
•  » » 4 years ago, # ^ |   +3 A "sink SCC" is a SCC with no edges directed towards other SCCs.
•  » » » 4 years ago, # ^ |   +3 Oh I get it! Thank you for the clarification, now it is clearer to me.
 » 4 years ago, # |   0 I think it is wrongly written that we have to check if k is divisible by lcm(c1,c2,..cn) , it should have been the other way around , although the notation is correct.
 » 4 years ago, # |   0 By implementing carefully, making the segment tree could be done in O(m*log(m)*alpha) Can you please explain how this can be implemented with this complexity?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 We don't need to sort the edges in nodes of our segment tree. We can use the idea of merge sort to keep the edges sorted after merging the children of a node.When the edges are sorted, complexity of our solution for a single query is O(nα (n) + m). We can make it in O(mα (n)) by only considering the vertices with positive degree. And each one of the edges come in nodes of the segment tree, so this implementation is overall.
•  » » » 4 years ago, # ^ |   0 Expected solution, if I just use dsu with logN complexity gives TLE while it passes only with alpha(n). The brute solution works faster with the given constraints than the expected solution. Time limits and constraints are really bad. Expected solution with O(logN) for dsu. TLE :http://codeforces.com/contest/687/submission/18838352 Expected solution with O(alpha(n)) for dsu. Passes in 3.5ms. Note that segment tree is usual recursive implementation not iterative like yours.http://codeforces.com/contest/687/submission/18838612 M*Q brute solution. Passes in 1.7ms.http://codeforces.com/contest/687/submission/18806679
 » 4 years ago, # | ← Rev. 2 →   0 can someone help me out with recursion with memoisation solution for 687 c i used set for each node in recursion tree but it gives memory limit exceeded http://codeforces.com/contest/687/submission/18829914
 » 4 years ago, # | ← Rev. 2 →   +5 I could have bet that the O(m * q) solution wasn't intended :). Nonetheless, how could you possibly differentiate an O(m) (which is, in fact, bounded by n2 / 4) solution per query, with an O(n * log(n)) solution which is itself dominated by a big constant (not to mention the fact that you have to allow more time for worse constants). It is, indeed, tricky to find constraints for such a problem.
 » 4 years ago, # |   0 Can SOMEone PLEASE explain DIV2E, i m unable to formulate the dp states(i m quite weak at dp), a detailed explanation would be appreciated, thanks.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 I can explain you somewhat similar dp approach which I used and which is a bit simpler than the apporach given in editorial.The basic idea of my approach is that as Pari wants to give Arya 'k' amount of money, so let's say she gives money in two steps, first she gives 'x' amount of money and then remaining 'k-x' amount of money, and Arya doesn't do anything now and just realises that she can make this 'x' amount of money from total given money.So, now all we have to do is to check if we can form two subsets from the avalaible coins such that the sum of two subsets is 'k'. So, we use dp for that.dp[i][j] is 1 if we can form two subsets with sum i and j, and 0 otherwise.The base case is dp[0][0]=1 .Also,since k<=500 so we don't need array bigger than dp[500][500], since subset sums bigger than 500 are not required in any case. Now, for each coin we iterate over array from [k][k] to [0][0] in row major order. if dp[i][j]=1 then it means that we can form two subsets of coins with sum i and j, hence we have to choice to put the current coin in first set or second set. If we put in first set, then we get i+m and j (m is the coin value) so dp[i+m][j] should be made 1 , similar for dp[i][j+m]. make sure to not overflow the array. Finally, we check for every i from 0 to k and see if dp[i][k-i] is 1, if yes then we add it to the final answer, the reason for doing so is the same as I explained in the beginning of giving money as 'x' and 'k-x'
 » 4 years ago, # |   0 problem 1D Don't you have to sort those n log n egdes you find in segment tree each query?
•  » » 4 years ago, # ^ |   0 maybe a method similiar to merge sort could help
 » 4 years ago, # |   0 Can anyone tell me why I am getting wrong answer on test case 15. Problem 687Ahttp://codeforces.com/contest/688/submission/18833781
•  » » 4 years ago, # ^ |   +5 The Graph can have more than one connected component (Not all the vertices might be reachable from vertex 0)
•  » » » 11 months ago, # ^ |   0 Thank you!
•  » » » 8 months ago, # ^ |   0 how to ensure that now ?
•  » » 4 years ago, # ^ |   0 6 4 1 2 1 3 4 5 4 6 Answer 4 2 3 5 6 2 1 4 
 » 4 years ago, # |   0 Can anyone help me on the problem Div.2(D) Remainders Game? I'm a bit lost with the editorial since I haven't been familiar with math terminologies yet. But I understand the general idea and my implementation is kind of the same.My idea is that, we first find X = lcm(c_1, c_2, ... c_m). Then, my thought is that, for a number from 0 to X-1, all these numbers will have different representation consists of the remainders w.r.t c_i. For example, for c_1 = 2, c_2 = 3. For 0 — 5, the representation will be (0, 0), (1, 1), (0, 2), (1, 0), (0, 1), (1, 2) respectively. From number 6, this representation repeats. So, we can think of this as a special representation of numbers, as binary, decimal, etc... but with special rules.Then, if X is greater or equal than k(the given k), and it's a multiple of k, it should be ok to distinguish the remainders w.r.t k. But I'm getting wrong answer on test 10. Can anyone tell me where the problem is?Here is my implementation: codePS: by the way, how to write math formula with proper subscripts in the comment?
•  » » 4 years ago, # ^ |   0 integer overflow is occuring while taking lcm you can add nEle=gcd(nEle,k) just after taking lcm then the code should work fine
 » 4 years ago, # |   0 In Div2D (or DIV1 B) Editorial, I think it should be exact opposite.Plz correct me if I am wrong..
•  » » 4 years ago, # ^ |   +8 No, its correct. first notice that we want to find necessary and sufficient condition for the answer "NO". when k is not a divisor of lcm(c1, c2, ..., ck) then the answer is "NO". because each prime factor of lcm(c1, c2, ..., ck) should have greater power than that prime factor in k.
 » 4 years ago, # | ← Rev. 2 →   0 Can you explain me Anta code for 687A
 » 4 years ago, # |   -11 I'm afraid that the C++ solution given for the NP hard problem(div 2 -C), is not correct it gives wrong answer on the first test itself.
 » 4 years ago, # |   0 jjjjj
 » 4 years ago, # |   +1 Why is it x1-x2 | lcm(all(ci)) but not lcm(all(ci)) | x1-x2 in 687B - Remainders Game when it can be shown that x1-x2 can take all values from [0->Inf]*lcm(all(ci)) ? P.S: I am assuming that a|b means a divides b please correct me if I am wrong.
•  » » 4 years ago, # ^ |   0 I can see some people including me have misunderstood the notation.We use the notation of three dots vertically put in order to indicate "divisible by"We use the symbol | in order to describe "is a divisor of"Formally, a | b means b is divisible by a.
 » 4 years ago, # |   0 in Div 2 Problem E (687C: The values you can make ), i calculated n*k*k value, and it was way big, and i thought that can not be the solution. I thought this speed aproximation should be around 1 million(because in linear runtime solution, n is usually 1 000 000, but now i guess it is because of slow IO speed ). Do you have an own number or different method to judge if your code will be fast enough?
•  » » 4 years ago, # ^ |   0 10^8 operations per second has been reasonable metric for me.
 » 4 years ago, # | ← Rev. 2 →   0 Can anyone help me Getting WA for problem C (Div 2)http://ideone.com/3bNfFy
•  » » 4 years ago, # ^ |   0 Actually graph might be not connected and start bfs from vertex 1 can be not enough, I think.
•  » » » 4 years ago, # ^ |   0 Thanks!!AC now
 » 4 years ago, # |   0 How much tight are the constraints for Div A I tried bipartite with BFS. It says time limit exceeded on 54th test case, Please provide an insight where this code can be optimized.http://ideone.com/eKwgjv
•  » » 4 years ago, # ^ |   0 nice.
 » 4 years ago, # |   0 We don't need more than two dimension in the dp of "The values you can make" because dp[i][j][k] = dp[i][j][k] | dp[i-1][j][k] here's my solution http://codeforces.com/contest/688/submission/19469686
 » 4 years ago, # |   0 Can anyone,please, help with this submission Problem B (Reminder Games) WA31 http://codeforces.com/contest/687/submission/20366779
 » 4 years ago, # |   0 In 688E / 687CMy Top Down Solution 26136529 Didn't pass the Time Limit.My Bottom Up Solution 26136617 Passed the Time Limit.I thought that Top Down is always faster because it doesn't compute the states that I don't need.So why did that happen ? xD
•  » » 17 months ago, # ^ |   0 Apparently, you know it by now, So please tell share why it happened?
 » 20 months ago, # |   0 In 687B Remainders Game, it is written that lcm | (x1-x2). So, can't (x1-x2) be written as t*(lcm). Also, it says that (x1-x2) isn't congruent to 0 mod k.So, (x1-x2) = t*lcm (t is some constant) ...1and (x1-x2) != 0 (mod k) ...2From 1, 2 we have (t*lcm) != 0 (mod k). But in the editorial we only check for lcm != 0 (mod k).Why? Thanks in advance.
 » 13 months ago, # |   0 687D: "Using dsu, we can find longest prefix of these edges, which doesn’t contains odd cycle"Can someone explain how you would find this using dsu? It's not obvious to me.
 » 11 months ago, # |   0 For the Div1 C challenge, do we only have to change the ORs to ANDs? As in this case, all paths to a subset's sum must be true, in order for it to be true. We can reach dp[i][j][k] in three ways, dp[i-1][j][k] (not using the ith element), dp[i-1][j-arr[i][k] (using the ith element, but not putting it in the subset), and dp[i-1][j-arr[i]][k-arr[i]] (using the ith element, and putting it in the subset). In this case, dp[i-1][j][k] would mean that we can always make a subset of size k, when considering subsets of the set making up a sum of j. We can not directly use this info, as there are other ways to make dp[i][j][k] too. So, having a similar thought for the other two dependencies, I think ANDing the three values would give the answer. Authors, please do tell if it is the correct method, or am I lacking somewhere.
 » 10 months ago, # |   0 What does TOF really mean? Does anybody know?
 » 8 months ago, # | ← Rev. 3 →   0 ,
 » 4 months ago, # | ← Rev. 2 →   0 If i run your solution for 687A with the input: 6 4 1 2 2 3 4 5 4 6 It doesn't give the correct answer. Also, from the tutorial, I was wondering if you need to include connected components as well.
 » 3 months ago, # | ← Rev. 2 →   0 Hello can someone explain why I got a TLE on case 14 on Div1 A even though I did the same thing as the tutorial said?(I use Java btw)
•  » » 3 months ago, # ^ |   0 Idk, here is some java code tho. Submission: 90340516
 » 3 months ago, # | ← Rev. 5 →   0 In my solution of NP-Hard Problem whats going wrong? Thanks! 90340096 WA: Test Case 15. EDIT: NVM! LOL, I was always dfs-ing on index 0 and wasn't changing. Typos....
»
3 weeks ago, # |
0

Here is my code which is working fine in all other compilers, but showing error in 1st test case of this ques. i have no idea why same code is showing different output in cf's compiler and in GBD and atom. Help plzzz. //ans

# include<bits/stdc++.h>

using namespace std; int main() { int n,d; cin>>n>>d; int win[d],c=0,max=1,count=0; string pre; for(int i=0;i<d;i++) { fflush(stdin); cin>>pre; for(int j=0;j<n;j++) { if(pre[j] == '0') { c=1; } } if(c != 0) { win[i] = 1; c=0; } else { win[i] = 0; c=0; } }

for(int i=0;i<d-1;i++) { if((win[i] == win[i+1]) && win[i] == 1) { if(count == 0) count = count + 2; else count = count + 1; if(count >= max) max=count; } else count=0; //cout<<"i= "<<i<<" "<<win[i]<<endl; } cout<<max; }