Pretests are not weak, time-limit is tight

Can div 2 C be solved without graphs usage? if so can someone explain how to solve it without graphs?

the second case should be 1-2+4=3

Same thing happened with me. After contest, I used dictionary to store the answers. Here is my AC code.

def valid(n):
    n = str(n)
    for i in n:
        if int(i)!=0 and (int(n)%int(i))!=0:
            return False
    return True

d = dict()       
for _ in range(int(input())):
    nn = int(input())
    n = nn
    if nn in d:
        print(d[nn])
        continue
    
    while not valid(n):
        n+=1
    d[nn]=n
    print(n)

Just hacked your lower constant solution. That one passed only cause there wasn't an early exit counter test case.

Btw the reason why PyPy is super slow here is that PyPy is 32 bit on CF, so this problem requires you to do a ton of work on big integers. This code would have easily passed on pretty much any other online platform. Remember to always look out for slow big integer operations in the future! Especially in problems like this where a lot of the big integer calculations easily can be avoided.

After uphacking your code I continued hacking. Currently up to 391 uphacks on Div 2 B. The system tests were definitely lacking.

LCM(1,2,3,4,5,6,7,8,9)=2520 So ::>> EVERY MULTIPLE OF 2520 is divisible by all digits( 1,2,3,4,5,6,7,8,9 )

NOW let x=n(GIVEN NUMBER). SO just iterate x ,i.e., do x++ UNTIL THE given CONDITION in question SATISFIES.This will take at most 2519 iterations.

can u post the link to the code pls?

1.Ignore the rooks on coordinates of form (x,x) since they are already on the diagonal

2.Make directed edge between two rooks if x coordinate of the one rook matches y coordinate of the other rook. Suppose there is rook on coordinate (x,y) and another on $$$(x_1,x)$$$ then there will be edge from rook on (x,y) to rook on $$$(x_1,x)$$$.

From point 2 we will get a graph . Answer will be number of vertices + number of cycles in the graph . This is because for each vertex we have to do at least one operation . Whereas for cycle , we need to do at-least 2 operation for any one of the vertex on cycle to break the cycle. Note : Here we are not counting vertices (of form (x,x)) in point 1 in our calculation thus no need to subtract as given in the Editorial.

For example in following 5*5 matrix (sorry for bad picture), minimum number of operations is 5 (4 vertex + 1 cycle). Red dots are rooks and red edges form the graph.

Try yourself in less than 5 operations and you won't be able to do it.

Well i considered it to be a graph with n nodes where each coordinate (i,i) ( 1<=i<=n) are considered as nodes. There is an edge between a node at (i,i) and (j,j) if there is a rook at (i,j). Ignore the rooks placed on coordinates of the type (i,i) because those nodes form self loops. Now simply count the number of cycles in the graph.

Now the answer is

number of cycles + number of rooks not on any (i,i)

This is my submission link 101935324

Same with me . Don't know whats the point of making those submission fails system test! Atleast , they could have added a pretest that would take longer time, so that people could get that point of log factor!

I think its not due to log factor but constant factor of set. i am not sure.

Hey neckbotov, can you explain why can't we treat each vertex independently? I mean why not just find out if a vertex is winning or losing by simply traversing topological order in reverse. Essentially, why can't the grundy number for a vertex be 0 or 1?

I constructed it with bidirectional edges and it worked as well if you accept multiple edges. Otherwise you wont be able to see the cycle of length 2 easily (for such a cycle you need two rooks that have switched coordinates, e.g. 1 2 and 2 1).

My implementation is bit different. I created graph of pairs — $$$(x,y).$$$ You can look at my code. Not sure, if it's helpful.

I'll try to explain a bit.

Start dfs from any pair $$$(a,b)$$$ if it is not visited and explore its connected component. A pair $$$(c,d)$$$ is connected to pair $$$(a,b)$$$ iff $$$d=a$$$ or $$$c=b$$$. I'm first assuming there is $$$cycle$$$ in the connected component. Start from $$$(a,b)$$$. If it has $$$0$$$ connected nodes, we are sure there will no cycle as we can put $$$(a,b)$$$ at any of the $$$2$$$ suitable points. If it has only $$$1$$$ connected node, we can be sure that there is no cycle (we can move that rook at only suitable point) but we will still put the only connected node into the stack (if its un-visited) to explore further total number of nodes in the connected component. If it has $$$2$$$ neighbor nodes, put them into stack (if they are un-visited).

Finally, after each dfs, $$$ans+=x + c$$$ where $$$x$$$ is nodes in the connected component and $$$c=1$$$ if there is a cycle in the component else $$$0$$$

I'm not sure if cycle is correct term for it but I mean is if in any connected component, if we find any node $$$(x,y)$$$ for which either of it's $$$2$$$ suitable positions is free, we can displace that rook to its any suitable position thus breaking the locks. If we can't find any such position, we have pay 1 extra than the total nodes in the component.

Either will do, but not both. We need to move a rook from $$$(x,y)$$$ to either $$$(x,x)$$$ or $$$(y,y)$$$.

Another approach would be:-

Make a copy of the original string (call it "ss"), and fill all '?' with '0' in string ss.

Then calculate the answer for string ss and store it in "temp".

Initialize "ans" and assign it the value of "temp".

Then, start iterating backward in the original string s (i.e. from i=n-1). On positions where s has '?', recalculate temp by subtracting the number of comments if this position had '0' in it, and adding the term if this position would have '1' in it, greedily.

Then, update:

ans=min(ans,temp)

The final minimum number of comments is obtained in "ans".

Yes, it is

Read D

I am similar with you, and I choose to sleep

Test case 12 has not been there at the time of the system test! It has been added later. xmt You're lucky to get away with that :D Anyway, you would be gaining CM I guess, Congrats!!

The following change 101919959 fixes the issue. (Using the vis in while loop to validate)

The following change 101919959 fixes the issue. (Using the vis in while loop to validate)

I arrived at the same solution eventually. 101922707

Instead of time D&C we can build a segment tree on all paths present in queries, and turn them on/off.

Ideas from yesterday's 1458F - Range Diameter Sum were somewhat helpful.

Sorry for replying after a long time. I'm referring to your implementation and have some questions about the divide-and-conquer process. I noticed that your code may add an insertion twice to a segment tree node (though it doesn't matter in this problem). Does your solution still function correctly when maintaining information that doesn't have this property (for example, maintaining the sum of all elements)? If not, does raising $$$q$$$ to the nearest power of $$$2$$$ help?

EDIT: I found this article, but I still can't understand why it is correct.

This is not a proof but let me share my idea.

Let's consider the situation where all the signs are a minus sign(i.e. the n — 2 prefix signs are all minus signs) and you can turn an arbitrary minus sign into a plus sign. In this case, the result of calculation will become minimum. Let this value be V.

When you want to obtain some value greater than V, it is always better to choose as big a number as possible and change its sign(but even after the change, V should not exceeds the value we want) because you want to adjust V with small numbers afterwards. (In other words, why do you use several small numbers to make a big number that already exists? You are missing out!)

Yeah I also have the confusion, especially when we convert from negative to positive, like: -13 = -16 + 2 + 1 So when we meet -13, how can we decide whether +16 or just leave it here

I struggle with it a lot yesterday, but the solution from ecnerwala convince me a lot, you can take a look at his stream.
The basic idea is that he treat +-2^S[i] as -2^S[i] + (0 or 2^{S[i]+1}). So we can add all S[i] to T and decompose it into binary with power of i+1.
More formally, sum(+-2^S[i]) = T => sum(2^S[i+1] or 0) = T + sum(2^S[i])

Suppose number we need to reach is $$$tot$$$.Since sign of a[n],a[n-1] is fixed , we can subtract and add their powers from $$$tot$$$. Now we initialize $$$s=0$$$ and we need to reach $$$tot$$$ using characters from 1 till n-2 .

I used following greedy method (and i hope editorial refers to same greedy method) : sort the string from 1 till n-2 . Now iterate from n-2 to 1 and if $$$s \gt tot$$$ subtract $$$2^{a[i]}$$$ else add.submission

Proof : Suppose we are at index $$$i$$$ and $$$s \gt tot$$$ . If in optimal solution we do $$$s += 2^{a[i]}$$$ (contrary to what i mentioned) , then sum of numbers left , say $$$H$$$ , must be greater than $$$2^{a[i]}$$$ (otherwise $$$s + 2^{a[i]} - H \gt tot$$$ and answer won't exist) . Also since $$$H \gt 2^{a[i]}$$$ and array is sorted , there must be some subset say $$$SS$$$ of $$$a[1],a[2],a[3]...a[i-1]$$$ such that sum of their power of 2 is equal to $$$2^{a[i]}$$$ .We also need to add subtract at least $$$2^{a[i]}$$$ in future , else $$$s$$$ will be greater than $$$tot$$$.

But then we can do $$$s -= 2^{a[i]}$$$ instead and we can add sum of power of 2 of subset $$$SS$$$ in future. Similar proof for case $$$s \lt =tot$$$ .

Poman Numbers ( Div2 E/ Div1 C )

Explanation of the greedy part of the solution + Commented Code

                                                                                                                                                                                          /*
 
                                         IDEA
1. We have to assign signs (+,-) to different powers and make the "sum of powers" = T

2. ( As sign of last two powers is already fixed )
   Change T = T - ( -2^(str[n-2]) + 2^(str[n-1]) )  
   T = abs(T)   -> because if we can make T, we can also make -T

3. Initially consider  the powers to be negative 
      let sum = sum of powers = (-)2^(str[0]) + (-)2^(str[1]) + (-)2^(str[2]) ...... (-)2^str[n-3]
      let rem = T - sum -> The number we need to add to sum , to make it equal to T

4. We have taken 2^x as a negative power, ( i.e added -2^x to sum )
      Suppose later on we want to change this sign to positive ( i.e we want to add +2^x to sum ) , 
      we can add 2^(x+1) to the sum because:
      (+)2^x = (-)2^x + ( 2^(x+1) )  -> 8 = -8 + 16

Therefore we can try to contruct rem from the powers of 2.
Read the code to understand better.
                                                                                                                                                                                          */

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

int n, T, pwr[26], cnt[60];
string str;

void read() {
      cin >> n >> T >> str;
      pwr[0] = 1;
      for(int i = 1; i < 26; i++) pwr[i] = 2*pwr[i-1];
}

int32_t main() {
      read();

      // signs of last two powers are already fixed
      T = T - (-pwr[ str[n-2] - 'a' ] + pwr[ str[n-1] - 'a' ]);

      // If we can make T we can also make -T
      T = abs(T);

      int sum = 0, rem = 0;
      for(int i = 0; i < n-2; i++) {

            int x = str[i] - 'a';
            // assigning all the powers negative sign
            sum -= pwr[x];

            // incrementing the cnt[x+1], as we can add 2*(x+1) power to later 
            // on change the sign of this power (2*x) to positive
            cnt[x + 1]++;
      }

      // rem -> The number we need to add to sum to make it equal to T.
      rem = T - sum;

      // cnt[i] -> the number of 2^i we have
      // We can either use the powers available in cnt or leave them as it is
      // Using a power will means we are reversing the sign of the power to positive.

      for(int i = 0; rem != 0 and sum != T; i++){
            if( (rem&(1LL<<i)) ){
                  rem -= (1LL<<i);
                  sum += (1LL<<i);
                  if( cnt[i] == 0 ){
                        cout << "No";
                        return 0;
                  }
                  cnt[i]--;
            }

            // merging current power to the next power as this power we be of no use now
            cnt[i+1] += cnt[i]/2;
      }

      cout << "Yes" << endl;
      return 0;
}

103545539

I didn't use graph but the solution is too long, basic idea is to see whether we can give a move when some points go to diagonal 101886029

Another approach 101883649.

Ques- Since the weights of the items are powers of two, we can choose them greedily,how?

Ans --> Firstly, let T = abs(T) because if we can make T from the array then -T can also be made by just reversing the symbols i.e + to -; and viceversa.

Now, get the sum of all elements and if sum is less than T then ans is clearly no, otherwise lets assume that T can be made using sum therefore sum_left = sum — T now for our assumption to be true we should be able to make val = sum_left/2 from the array elements :

i) if sum_left is odd then our assumption is false and print 'no'

ii)else we can simply check by sorting array in descending order and subtracting a[i] from val if val >= ai

finally if val becomes 0 our assumption was true i.e print 'yes' else 'no'

Code Link: 101958203

Your vector only contains n's digits, not x. Therefore, it will add +1 until the number x is divisible by the every digits n. My english is very bad, so i think you get the main idea

I hope you know about DSU .If not , read here , very easy to understand.

Suppose we have two vertices $$$v_1,v_2$$$ in the graph formed having edge between them . Then we connect root parent of $$$v_1$$$ and root parent of $$$v_2$$$ in DSU "join" operation . But while joining if we found that they are already in same tree (i.e have same root "parent") then there is a cycle since there was a path between $$$v_1,v_2$$$ earlier and thus adding one edge between them will make a cycle.

Now count all the cycles using above method and use the formula either described in editorial or here.

From DP I think the time complexity would be O(n^2).

I also faced a similar issue

Let's say there are 3 rooks at (a, b), (b, c) and (c, d). In your WA solution, if you start your dfs from c, you will mark c and d as visited and then call dfs(a), this will return true because c is marked visited, but it was from a different component, you need a way to differentiate the nodes marked visited in the dfs(a) call and the ones marked earlier, this is what you are doing in your AC solution when you mark them 1 during the call and 2 after the call is finished.

use long long instead of int to avoid overflow