JaySharma1048576's blog

By JaySharma1048576, 4 months ago, In English

I am sorry for the weak tests in B, for C being a little standardish and for misjudging the relative difficulties of E and F. Nevertheless, I hope you enjoyed the round. Here is the editorial. Do provide your feedback on each problem so that I can improve upon them the next time.

A. Subtle Substring Subtraction

Hint 1
Hint 2
Tutorial
Bonus tasks
Solution
Feedback

B. A Perfectly Balanced String?

Hint 1
Tutorial
Bonus task
Solution
Feedback

C. Palindrome Basis

Hint 1
Hint 2
Tutorial
Bonus Task
Solution
Feedback

D. Lost Arithmetic Progression

Hint 1
Hint 2
Hint 3
Tutorial
Solution
Feedback

E. Power or XOR?

Hint 1
Hint 2
Hint 3
Hint 4
Tutorial
Bonus Task
Solution
Feedback

F. Anti-Theft Road Planning

Hint 1
Hint 2
Tutorial
Solution
Feedback
 
 
 
 
  • Vote: I like it
  • +93
  • Vote: I do not like it

»
4 months ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

I spend at least 5 times as much time on B as I do on C ...

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is alright mate, I did B in 15mins, but I could not solve C at all...

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Couldn't solve B but managed C in <40 mins. :(

»
4 months ago, # |
Rev. 3   Vote: I like it -69 Vote: I do not like it

.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    maybe its because U solve it too late , and it gave barely any points

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it -65 Vote: I do not like it

      They just could give me 0 pints not -78 !!

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +7 Vote: I do not like it

        when you perform lower than ur current rating level ur rating will drop

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it -66 Vote: I do not like it

          Okay , I won't enter any contexts anymore fuck their judgment

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it +28 Vote: I do not like it

            You shouldnt think like , contest bring your rating to your real performance , sometimes you can have rating drops but in the end when you look for like a 1 year rating graph , you will see a linear growth

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it +19 Vote: I do not like it

            Lol, bye.

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            Fun fact: For the first five contests you participate, you get an extra few hundred rating points as technically unrated accounts start at 1500 (behind the scene), and after that, there is no such thing.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        If CF worked like that I could have been red...

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I like the idea of "I solved A, so I get some points" ;) We good looking people must stick together!

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I couldnt understand how do we prevent counting the same thing over and over in C

  • »
    »
    4 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    This code won't count the same thing

    for (int i = 1; i <= tot; i++) {
        for (int j = num[i]; j <= maxn - 1; j++) {
            dp[j] = (dp[j] + dp[j - num[i]]) % mod;
        }
    }
    

    but if you swap the the order of i and j, you'll get wrong answer because you count the same thing

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    instead of counting for T test cases, you only count once for all the possible values of n and then get the answer for each test case in O(1). So your final answer would be O(498*N + T), not O(T*N*498). I hope that it helps.

»
4 months ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

in the editorial of problem C, aren't there only M = 498 palindromes?

»
4 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Here are the video Solutions for A-D in case someone is interested.

»
4 months ago, # |
Rev. 2   Vote: I like it -27 Vote: I do not like it

/

»
4 months ago, # |
  Vote: I like it +12 Vote: I do not like it

If you prefer command line, checkout CF Doctor for more flexibility and faster feedback.

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.

If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).

»
4 months ago, # |
  Vote: I like it +23 Vote: I do not like it

Finally reached green :))

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey man do you recommend learning dp to reach pupil? Or should I just focus more on basics? Congratulations btw :)

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      Thanks! About dp, I didn't really know dp that well, I was usually doing graph and bitwise operation problems because it was hard for me to understand. But I didn't use them xd. I recommend you to do the math and basic problems, basically, anything you don't feel comfortable doing, so you can improve some bit of your skills slowly, but surely. Also don't forget to check out editorials, even if you solve the problem because it happens that you solve it "bad" way that doesn't make you any good, and by seeing editorials you can understand the true idea behind solutions, so you can see how coding works from the perspective of "professional" coders who created the contest. Good luck improving your skills, hopefully, you will reach green soon, but don't forget that it is necessary to be fast, first of all, improve yourself and the new color will come as if nothing happened :)))

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks mate! And about the editorial thing, yes it's so true! I mean in this contest itself I solved B in a weird way. When I looked at the editorial, only then I came to know that it could have been solved much more easily :)

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hey man! Just came here to let you know that I finally reached green hehe :)) And I still don't know dp lmao

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
          Rev. 5   Vote: I like it 0 Vote: I do not like it

          Hey, I just found this book about CP, it is a good one, has lots of stuff in it explained well, you should check it out if you have not heard of it before, it is called "Competitive Programming Handbook", you can search it up on google, it is a book and has lots of in it that can help you improve. It also has a site where you can check your solutions to problems from the book. Go to cses.fi -> courses -> CSES Problem Set and then you can practice problems on topics of your choice. Good luck!

          • »
            »
            »
            »
            »
            »
            7 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yup I know about that book. I learnt some basic stuff from there, but most of the stuff from the book is just too advanced for me lol.

»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Thanks for the fast editorial!

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem C, I don't get why the second term of the dp is $$$dp_{k-p_m, m}$$$ but not $$$dp_{k-p_m, m-1}$$$, because we have the mth palindrome number fixed and then we have m-1 other palindromes that need to be chosen to give our answer

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because if we can use the same number more than once, so even if we use the mth palindrome number ending at k, we can still use all other m palindrome numbers

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because you still need to use pm to construct k-pm

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

will I reach pupil before I die?

»
4 months ago, # |
  Vote: I like it +81 Vote: I do not like it

Problem F

Hint1 says "try to find the one which has the least sum of road lengths."

I want to know the proof that 47616 is the least sum.

  • »
    »
    4 months ago, # ^ |
    Rev. 4   Vote: I like it +8 Vote: I do not like it

    Update: My bad, the solution below is worse than the standard solution. It should be $$$x_k=16x_{k-1}+3\times 2^k$$$. Apologies for incovenience.

    I don't know whether my solution reaches the least sum possible, but it seems much better than the one given in the tutorial.

    Let's recursively construct the matrix $$$A$$$ mentioned in the tutorial. We are going to construct a $$$2^k\times 2^k$$$ matrix $$$A_k$$$ for each $$$k\in [0,5]$$$, thus giving a solution to the original problem by taking the first $$$n$$$ rows and columns of $$$A_5$$$.

    The base case $$$A_0$$$ is simple, with a single $$$0$$$. Here is my way to get $$$A_k(k\geq 1)$$$ by $$$A_{k-1}$$$: flip $$$A_{k-1}$$$ to its right side to form a $$$2^{k-1}\times 2^k$$$ matrix (let's say, $$$B_k$$$), then flip $$$B_k$$$ to its down side to form a $$$2^k\times 2^k$$$ matrix $$$C_k$$$. Finally, we multiply each element in $$$C_k$$$ by $$$4$$$, and add $$$0,1,2,3$$$ to the up-left, up-right, down-left, and down-right part of the matrix respectively to form $$$A_k$$$ (by the up-left part I mean the submatrix consisting of elements in both the first $$$2^{k-1}$$$ rows and first $$$2^{k-1}$$$ columns, the other three are defined in similar ways).

    Let $$$x_k$$$ be the sum of length of edges in $$$A_k$$$. One can find that $$$x_0=0$$$, and $$$x_k=4x_{k-1}+3\times 2^k$$$. By using the calculator it turns out that $$$x_5=2976$$$, far lower than the problem's original constraints.

»
4 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Finally able to use some standard dp I learnt in a rated contest. Love it! XD.

»
4 months ago, # |
  Vote: I like it +23 Vote: I do not like it

Is C too standard?

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

loved D ;D

»
4 months ago, # |
  Vote: I like it +71 Vote: I do not like it

I have a solution for problem F that constructs the same grid but with a completely different intuition. So let's say for a fixed row, all the values should be the same, that way you can know if you have passed that row before. Since if you ever make a "redundant" move, you will have to cross it again and the xor will cancel out. The same logic applies to the columns. So then you try to use 5 bits to manipulate the information for rows and 5 bits for the columns. Think about the line that evenly splits the rows into two halves. If you put a line of all of the same bit there, simply by checking if that bit is on, you can see which halves of the partition the rows is a part of. Then you have a smaller problem of half the rows to deal with. Finally, when there is only 1 row left, you can just leave the last bit on to check if it has crossed that row or not. The same logic applies to the columns. Now you also have to pick the bits rows to manipulate and the bits the columns manipulate separately. I found that the choice of

rows[] = {1, 4, 16, 64, 512}
col[] = {2, 8, 32, 128, 256}

fits within the limit of $$$48000$$$. To construct the answer itself, you check if a certain bit is on, and if it is, you update the respective row/column value and also xor x to make sure that the contribution of the prefix is considered.

My implementation of the idea is here.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Solution to bonus task of problem C : 155417311 My first DP problem solved in a contest even though it was similar to standard coin change problem.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I like B

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you explain the initial thought process to solve B. I have read the editorial yet don't understand how should one begin to think about the problem to reach the solution.

»
4 months ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

In editorial for problem B

s will be perfectly balanced if and only if si,si+1,…,si+k are all pairwise distinct

shoudn't it be si,si+1,…,si+k-1 since there are k distinct chars

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

My A problem was garbled but I passed the in-match test and got RE after the match because the array was opened too small.How happy I was at the end of the race and how sad I was after the retest.。゚(゚´Д`゚)゚。

»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Here is another way to calculate $$$\binom{n}{m} \bmod 2$$$. We know that $$$\binom{n}{m} = \frac{n!}{m!(n - m)!}$$$. Define $$$P(n) = \max\{k : 2^k | n!\} = \sum_{i = 1}^{+\infty} \lfloor \frac{n}{2^i} \rfloor$$$. Then $$$\binom{n}{m} \bmod 2 = 1$$$ iff $$$P(n) - P(m) - P(n - m) = 0$$$.

Obviously, we can calculate $$$P(n)$$$ in $$$O(\log n)$$$ time, but here is a more efficient way. Suppose $$$n = 2^{a_1} + 2^{a_2} + \cdots + 2^{a_m}$$$. Then

$$$ \begin{aligned} \sum_{i = 1}^{+\infty} \lfloor \frac{n}{2^i} \rfloor &= \sum_{j = 1}^m\sum_{i = 1}^{+\infty} \lfloor \frac{2^{a_j}}{2^i} \rfloor \\\\ &= \sum_{j = 1}^m\sum_{i = 1}^{a_j} 2^{a_j - i}\\\\ &= \sum_{j = 1}^m (2^{a_j} - 1)\\\\ &= n - m \end{aligned} $$$

Obviously, $$$m = \text{popcount}(n)$$$, the number of $$$1$$$(s) in binary form of $$$n$$$, which can be calculated fast in C++ with __builtin_popcount(n) or __builtin_popcountll(n) (when n is long long type). This improvement helped me from TLE to AC, and shows that __builtin_popcount really has very small constant. :P

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have coded almost the same solution (with same time complexity) for 1673C - Палиндромный базис but still TLE! Can someone help me understand why?

int checkPalindrome(int n) {
    int original = n;
    int remainder;
    int reversed = 0;
    while (n != 0) {
        remainder = n % 10;
        reversed = reversed * 10 + remainder;
        n /= 10;
    }
 
    if (original == reversed)
        return 1;
    return 0;
}
 
int mod = 1e9 + 7;
 
vector<int> arr;
int n;
void helper() {
    for (int i = 0; i <= 40000; i++) {
        if (checkPalindrome(i)) {
            arr.push_back(i);
        }
    }
    n = arr.size();
}
 
void solve() {
    int sum;
    cin >> sum;
 
    vector<vector<int>> dp(n + 1, vector<int>(sum + 1, 0));
 
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 1;
    }
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= sum; j++) {
            if (arr[i] <= j) {
                dp[i][j] = (dp[i][j - arr[i]] + dp[i - 1][j]) % mod;
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
 
    cout << dp[n][sum] << endl;
}
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    You recompute $$$dp$$$ for every testcase, so the number of operations is on the order $$$10^4 \times 4 \cdot 10^4 \times 500 = 2 \cdot 10^{11}$$$.

    Instead precompute the $$$dp$$$ table once before all testcases, then simply output $$$dp[n][sum]$$$ in each test case.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Don't calculate dp array every time. It is enough to calculate it only one time at the very beginning.

»
4 months ago, # |
  Vote: I like it +2 Vote: I do not like it

i solved A and B after contest

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Hey if some one can tell me what is the max size of vector we can have of long long int in c++? AS for problem B I had something of 1e6 but neither it gave MLE nor any other error.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    One long long int occupies 8 bytes. The array of 1M values itself occupies 8 Mbytes of memory. vector ocupies more but not twice. How many arrays do you create?

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      actually it was vector not array and its maximum size will be 26*2*1e5 155418148

      you can check here . I am doing same with array and its giving run time error with array in my own system but for vector its accepting I don't know why though

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I need a help, in problem B firstly we need to find out that how many distinctive characters are there. So, i wrote a function in C to find out the number of elements which are distinctive. So my question is: What is the more efficient way to find out the distinctive elements in a string? here is my code in C:

long int DistinctChars(char *s)
{
  long int len = strlen (s);
  long int i, j, d = 0;
  for (i = 0; i < len; i++)
    {
      if (s[i] != '^')
	{
	  for (j = i + 1; j < len; j++)
	    {
	      if (s[i] == s[j])
		{
		  s[j] = '^';
		}
	    }
	  d++;

	}
    }
  return d;
}
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    There are only 26 letters. You could make an array of 26 zeroes and mark with 1 every letter found. The sum of the array is an answer.

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

The Bonus Tasks are really educational !! Thanks a lot

»
4 months ago, # |
  Vote: I like it -6 Vote: I do not like it

In editorial for B, do you mean $$$s_i, s_{i+1}, \dots s_{i+k-1}$$$

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For the editorial of Problem D:

Could you explain why For a particular value of p, there are r/p possible values of a satisfying conditions 2 and 3 and r/p possible values of l satisfying conditions 2 and 4?

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Given p is a factor of r which we take as common difference of array A. Then let elements of C be x1 x2 x3 x4....xn the number of terms of A b/w xi and xi+1 will be (x2-x1)/p-1= r/p-1

    before x1 there could be thus (r/p-1) +1(no number to left of x1) = r/p numbers this because the number x0=x1-r

    x0 is not in C which implies it is not in A since x0 = x1-k*q (r=k*q) ( Not taking infinity case into consideration here)

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Let p is the step of sequence A. Sequence A contains z — the first value of C. Sequence A can start exactly from z, from z-p, from z-2*p, ..., from z — (r/p-1)*p. Total is r/p variants. Absolutely the same situation at the end of seqence. It can stop at f, at f+p, at f+2*p, ..., at f+(r/p-1)*p. So every divider p adds (r/p)*(r/p) variants.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks, I got it!

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain how to extend 2^k*2^k gray code to 2^k*2^(k+1) please?

»
4 months ago, # |
  Vote: I like it +37 Vote: I do not like it

I have a very simple solution for problem F:

First, lets look at the 1d version of the problem. Recall that the action of $$$+1$$$ or $$$-1$$$ is just flipping the first few bits of the number in binary representation. Firstly, 0-index the buildings. For edge between $$$i$$$ and $$$i+1$$$, we will assign the length as the highest power of 2 that divides $$$i+1$$$. For each query, we will check through the bits of $$$re$$$ (the number returned by the interactor). if the $$$ith$$$ bit is on, we will filp the first $$$i$$$ bits of the current $$$x$$$ coordinate.

The sum of length, if $$$n$$$ is a perfect power of 2, is $$$n/2\times\log(n)$$$. Proof is left to the reader.

By implementing for the $$$x$$$ coordinate on odd bit positions and $$$y$$$ coordinate on even bit positions, the sum is exactly $$$47616$$$. Proof is again, very simple and left to the reader.

Implementation, which is quite short and pretty: here

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain how the dp is working for problem C Palindrome Basis?? If anyone can share some resources then also it will be helpful.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I think the editorial has skipped a possible intuition for the dp states and transitions under the cover of an existing standard problem.

    During my upsolving I thought like this :-

    Since the problem states that sequences are differentiated solely on the basis of frequencies, why not think in terms of sorted sequences.

    I find out the list of palindromes in sorted order first.

    It's easy to see that if two sorted sequences are the same then they will have the same frequencies.

    My states for dp are :- $$$dp_{value,last}$$$

    basically the current sequence has a sum = value and we had appended some element x as the latest element which can be <= last.

    $$$dp_{value,last} = dp_{value,last−1} + dp_{value−p_{last},last}$$$

    So we can either have a sequence whose sum is = value and the latest element appended is <= last $$$-$$$ 1 and we do not append anything or we can have a sequence where we append $$$p_{last}$$$, in that case, our sequence's former last element should have been <= last and also its sum should be = $$$value - p_{last}$$$

    so transitions are just the same as in the editorial

    This is one way to think 'intuitively' about the states perhaps there are other ways to go about it too.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for the analysis. I liked yours way of thinking . It felt easier to understand.

»
4 months ago, # |
  Vote: I like it +10 Vote: I do not like it

My solution for B was this:

Assume $$$S$$$ — set of distinct letters in string $$$s$$$. Let's check every substring $$$s_iAs_j$$$, where $$$s_i = s_j = c,\,c \not\in A$$$ for every $$$c \in S$$$. Note that $$$A$$$ can be empty ($$$A = \emptyset$$$).

We give answer NO if there is letter $$$\hat c \ne c$$$ such that $$$\hat c \in S$$$ and $$$\hat c \not\in A$$$. That means that substring $$$s_i A s_j$$$ has two letters $$$c$$$ and zero letters $$$\hat c$$$. Otherwise the answer is YES.

My submission: 155416323

P.S. I guess there might be a problem with time complexity since we have two nested cycles for letters $$$a...z$$$. But I think either we find NO fast, either the second cycle will run only each $$$k$$$ iterations, where $$$k$$$ -- number of distinct letters in $$$s$$$. Correct me if I'm wrong.

P.P.S In my code I should break the cycle if I find NO, it was my fault :D

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This is a very great editorial, thanks!

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain, or at least give a hint, about the reason why the formula for problem F is true?

This: $$$\dfrac{3}{2}(4^m)(2^m - 1)$$$

»
4 months ago, # |
  Vote: I like it -21 Vote: I do not like it

Problem C What is the problem in this code: (memory limit exceeds)

unordered_map<long long,int> dp[502];
vector<int> pd;

long long rec(int i, int sum){
  //  cout<<i<<sum<<" ";
    long long ans = 0;
    if(i>=pd.size()) return -1;
    if(sum == 0){
        return 1;
    }
    if(dp[i][sum] !=0) return dp[i][sum]%modulo;

    if(pd[i]>sum) return dp[i][sum] = -1;

    if(rec(i+1,sum)==-1) return dp [i][sum] = rec(i, sum-pd[i])%modulo;
    if(rec(i, sum - pd[i])==-1) return dp[i][sum] = rec(i+1,sum)%modulo;
    if(rec(i, sum - pd[i])==-1 && rec(i+1, sum) ==-1) return -1;

    return dp[i][sum] = (rec(i, sum - pd[i]) + rec(i+1, sum) )%modulo;

}

int reverse(int n)
{
    int r=0;
    while(n>0)
    {
        r=r*10+n%10;
        n/=10;
    }
    return r;
}

bool palindrome(int n)
{
    return (reverse(n)==n);
}


void solve(){
    int sum; cin>>sum;
    long long x = rec(0 ,sum);
    if(x==-1) {
        cout<<"0\n";
        return;
    }
    //rec(1,3);
    //cout<<dp[1][3]<<dp[0][2];//<<dp[2][3];

    cout<<x%modulo<<endl;
}

int main() {


	//ios_base::sync_with_stdio(false);
	//cin.tie(NULL);

 for(int i=1;i<2*40004;i++)
    {
        if(palindrome(i))
            pd.push_back(i);
    }


	int t ;
	cin>>t;
	while(t--){
	solve();
	//	cout<<endl;
	}
	return 0;
}

Also this code gives 0 in random test cases, why??? ****

const int N = 40004, M = 502;
const long long MOD = 1000000007;
long long dp[N][M];

vector<int> pd;

long long rec(int i, int sum){
  //  cout<<i<<sum<<" ";
    long long ans = 0;
    if(i>=pd.size()) return -1;
    if(sum == 0){
        return 1;
    }
    if(dp[i][sum] !=0) return dp[i][sum]%modulo;

    if(pd[i]>sum) return dp[i][sum] = -1;

    if(rec(i+1,sum)==-1) return dp [i][sum] = rec(i, sum-pd[i])%modulo;
    if(rec(i, sum - pd[i])==-1) return dp[i][sum] = rec(i+1,sum)%modulo;
    if(rec(i, sum - pd[i])==-1 && rec(i+1, sum) ==-1) return -1;

    return dp[i][sum] = (rec(i, sum - pd[i]) + rec(i+1, sum) )%modulo;

}

int reverse(int n)
{
    int r=0;
    while(n>0)
    {
        r=r*10+n%10;
        n/=10;
    }
    return r;
}

bool palindrome(int n)
{
    return (reverse(n)==n);
}


void solve(){

    int sum; cin>>sum;
    long long x = rec(0 ,sum);
    if(x==-1) {
        cout<<"0\n";
        return;
    }


    cout<<x%modulo<<endl;
}

int main() {

    memset(dp, 0, sizeof(dp));
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

 for(int i=1;i<2*40004;i++)
    {
        if(palindrome(i))
            pd.push_back(i);
    }


	int t ;
	cin>>t;
	while(t--){
	solve();
	//	cout<<endl;
	}
	return 0;
}
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone kindly explain the implementation of B.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Very nice contest! I love super-super ad-hoc problems, they're the most interesting to me. Unfortunately I couldn't quite solve E in time, because I initially misread "at least $$$k$$$" as "exactly $$$k$$$", and then panicked :(

»
3 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

hi everyone, my solution to problem b is different and i think it's better using the concept to sliding window and maps, just wanted to share it:->

include <bits/stdc++.h>

using namespace std;

define int long long

define endl " \n"

signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t; cin>>t; while(t--){ string a; cin>>a; map<char,int> x; for(int i=0;i<a.length();i++){ x[a[i]]++; } int flag=0; int j=0; int i=0; map<char,int> ans; while(j<a.length()){ ans[a[j]]++; if(ans[a[j]]>=2){ if(ans.size()!=x.size()){ flag=1; break; } ans[a[i]]--;

if(ans[a[i]]==0){

                flag=1;
                break;
            }
            i++;
        }
        j++;
    }
    if(flag==1){
        cout<<"No"<<endl;
    }
    else{
        cout<<"yes"<<endl;
    }

}


return 0;

}

SORRY for the mess, this was my first time posting, here is the link to the submission https://codeforces.com/contest/1673/submission/155436027

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am trying to solve E. wrote the same code as in editorial but still getting Wrong answer on test case 9. This is my code. Plz, let me know where I am going wrong.

// Online C++ compiler to run C++ program online

#include <bits/stdc++.h>
using namespace std;
#define loop(i, s, e) for(long long int  i = s; i < e; i++)
#define lli long long int 
const int pow20 = 1048576;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // Write C++ code here
    lli n, k;
    cin >> n >> k ;
    vector<lli> Arr(n);
    vector<char> Ans(pow20+1,'0');
    loop(i, 0, n) cin >> Arr[i];
    // loop(i, 0, n) cout << Arr[i] << " ";
    // cout<<endl;
    loop(i, 0 , n){
        lli pow = 1;
        loop(j, i, n){
            // cout << "( "<<i << ","<< j << " ) ";
            
            if(j == i) pow *= Arr[j];
            else {
                if(Arr[j]>=20) break;
                else pow *= ((lli)1<<Arr[j]);
            }
            if(pow >= pow20) break;
            
            
            int remainingN = n-j+i-3;
            int remainingK = k-2;
            
            if(i == 0) {
                remainingN++;
                remainingK++;
            }
            if(j == n-1){
                remainingN++;
                remainingK++;
            } 
            
            // cout << "=("<< remainingN <<","<< remainingK << ","<< pow <<") " ;
            lli x = remainingN-remainingK;
            lli y = remainingK-1;
            lli z = remainingN-1;
            if(remainingN>=remainingK && (remainingN ==0 || (remainingK>0 && (z == y|x))))
                Ans[pow] = '0'+'1'-Ans[pow];
                // Ans[pow] = Ans[pow] ^ 1;
        }
    }

    bool start=false;
    for(int i=pow20-1;i>=0;i--)
    {
        if(start && Ans[i]=='0' )
            cout << 0;
        else if(Ans[i]=='1')
        {
            cout << 1;
            start=true;
        }
    }
    if(!start) cout << 0;
    cout << endl;


    return 0;
}
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I got this as Checker log wrong answer expected YES, found NO [731st token]

can you give me test case for 731 token ? 159332450

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem F was very good. Thank you!

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem C in space complexity to O(n)?

Please help!