pikmike's blog

By pikmike, history, 5 weeks ago, translation, In English

1400A - String Similarity

Idea: BledDest

Tutorial
Solution (adedalic)

1400B - RPG Protagonist

Idea: adedalic

Tutorial
Solution (adedalic)

1400C - Binary String Reconstruction

Idea: Roms

Tutorial
Solution (Roms)

1400D - Zigzags

Idea: adedalic

Tutorial
Solution (adedalic)

1400E - Clear the Multiset

Idea: Roms

Tutorial
Solution (Roms)

1400F - x-prime Substrings

Idea: BledDest and Roms

Tutorial
Solution (pikmike)

1400G - Mercenaries

Idea: BledDest and Roms

Tutorial
Solution (BledDest)
 
 
 
 
  • Vote: I like it
  • +204
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

Editorial for E is not visible, can you please fix it.

»
5 weeks ago, # |
Rev. 2   Vote: I like it -22 Vote: I do not like it

Nice Explanations !

»
5 weeks ago, # |
Rev. 3   Vote: I like it -18 Vote: I do not like it

You can see nothing

»
5 weeks ago, # |
  Vote: I like it +28 Vote: I do not like it

In the contest page, the tutorial link redirects to neal's blog of Unofficial editorial. Maybe you should add this blog as tutorial, and neal's blog as extra tutorial.

»
5 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Any similar problems like B for practice ?

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

Can someone explain what's wrong with my solution for B?

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

    You aren't checking the cases when Follower can't pick enough items because Protagonist didn't leave for him. You are running two loops totally exclusively, but in reality they aren't mutually exclusive, and instead, dependent on each other. x swords picked by protagonist means Follower is only left with s-x and he has to choose from them.

»
5 weeks ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Can someone give a binary search approach to problem B, I am not able to implement it, and not getting the function that can be used to find different numbers satisfying the given condition i.e x*(no_of_swords) + y*(no_of_war axes) <= p(or f), or this can't be implemented? Thanks a lot in advance!!

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

    You mean problem B? LINK

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

      Can you explain this please

      you are doing r=mid-1 for first BS l=mid+1 for second BS

      Why not together? How did u come up this unique in time of contest??

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

        Basic idea : There are 2 people : me and my follower. I will brute force on the number of $$$swords$$$ that I take, binary search on the number of $$$swords$$$ my follower takes, and there will be some space left for both of us, we will use that to take as many $$$axes$$$ as we can.

        Problem with binary search : While doing binary search transition to the left or right is the most important thing. In our code $$$mid$$$ represents the number of $$$swords$$$ my follower is trying to take at this moment. If he can't take that much obviously he will try to take less, hence $$$r = mid-1$$$. If he can, then which direction you go next time? You try to take more swords and do $$$mid = l+1$$$, or do you try to take even lesser swords and do $$$r = mid-1$$$? We don't know. That is why I just decided to do both in separate binary searches.

        Doing it in one binary search : Do we try to take more swords or less? Actually we know the answer. If the weight of a sword is greater than the weight of an axe, taking more swords only reduces your chance of getting more items. So a simple greedy will allow you to do it in one binary search. LINK.

        It's just in contest I instantly had the idea of doing 2 binary searches so I just sticked with it.

»
5 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Roms pikmike In Problem E, what is the meaning of "closed", "open", "unclosed" operation?

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

    The operations of the first type are applied to some segments. An "unclosed" operation means that we have started a segment corresponding to some operation of the first type earlier, but haven't finished it yet. To "open" an operation is to start a segment, to "close" it is to end a segment.

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

      Can you please tell what is x passed as parameter in the calc function of the code given for Problem E.

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

      So what does it mean to "close" some operations of the second type and "open" a new operation of the second type?

»
5 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

i cannnot understand the DP solution to problem E, can somebody help me ?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    In case you need other solution than DP.

    Consider a range [l,r].

    For first type of operations: Consider an index x (l<=x<=r) such that a[x] is minimum in that range. If we apply the first operation a[x] times, then each element would be reduced by a[x]. And a[x] becomes 0. Now we can break this range in two parts [l,x-1] ans [x+1, r] and do the same thing.

    When there is a 0 in the range.
    When there are multiple indices whose values are minimum in the range

    For second type of operation: We can delete all elements in this range in no more than r-l+1 operations of second type.

    Code : 91083858

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 11   Vote: I like it +14 Vote: I do not like it

      Problem E . explain the Tag "DP & sorting"

      Now i've get the process by checking out the top div.1 programmer jiangly's solution. It's an implement of The line chart .

      At first, assume the second option is banned .

      This problem == CF1392C — Omkar and Waterslide.

      it indicates that when we go up from the (i-1)th positon to the (i)th position, the new cost =the difference betweem a[i-1] and a[i] ,formally,** a[i]-a[i-1]**. when we go down from the (i-1)th positon to the (i)th position, the new cost =0;

      now consider the second option, it means we can change the num in ith position,(the raw a[i]) to any num less than or equal to a[i], the cost=(new_num<a[i]?1:0)

      note that though we can change a[i] to any new_num<=a[i], but only the n+1 number {0,a[1],a[2],a[3]...a[n]} is effctive. and we sort_unique them to ** m different numbers.**

      denote dp[i][j] as : ** on the ith position of array a[], the cost of the process of 0.1.2....i,** after which we change the number to the jth biggest number(same number not inclusive) in array {a[],0};

      dp[n+1][0] is the answer ,(we make a[n+1]=a[0]=0,then the restrict "all num==0" is matched )

      and then we implement the dp process. simple implement can be O(n^3)

      consider MAX_N==5000;

      we Change the form of the raw dp equation, and use suffix minimum , preffix minimum,the O(n^2) solution can be implemented.

      reference material https://codeforces.com/contest/1400/submission/90933891

      jly&&EI 99

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

      Wow Wow Wow! This is kind of solving it greedily with recursion's help. Amazing observation! I saw a lot of solutions using this method, but most of them passed the entire vector as a parameter to their recursion function. This made it a bit hard for me to understand their logic. After reading this comment, I understand those codes now.

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

      This is the simplest solution here. It belongs in the editorial. Thanks for sharing!

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

      For the second type of operation, you are considering r-l+1 operations but if there are already elements with zeros what about them. Shouldn't we just count the number of non zero elements and use that instead. Or Maybe that case is handled by recursion?

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

        If there is a 0 in range [l,r], then the range would be divided into two without using any operation. Read the first spoiler.

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

In problem B, why we should take at first min(s,w)?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    just greedy , cheaper means more chance to buy more items

»
5 weeks ago, # |
Rev. 7   Vote: I like it -24 Vote: I do not like it

Problem D: Can anyone please tell me what is wrong with my solution? it is not working for this test case:

30

28 30 29 29 30 30 29 30 30 30 30 28 28 28 28 29 29 28 29 29 29 30 29 29 30 28 30 30 28 29 expected : 2618 received output : 41212

#include<bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
#define fo(i,n) for(int i=0;i<n;i++)
#define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define ll long long
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define PI 3.1415926535897932384626
typedef pair<int, int>	pii;
typedef vector<int>		vi;
typedef vector<pii>		vpii;
typedef vector<vi>		vvi;

int n,c;

void solve() {
  cin >> n; int a[n];
  int lef[n+1] = {0}; 
  int rig[n+1] = {0};
  fo(i, n) cin >> a[i];
  c = 0;
  
  for (int j = 0; j < n; j++) {
      for (int k = n - 1; k > j; k--) {
          c += rig[a[j]]*lef[a[k]];
          rig[a[k]]++; 
      }
      lef[a[j]]++;
      fo(i,n) rig[i] = 0;
  }
   cout << c << "\n";
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
      solve();
    }

    return 0;
}
»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

In problem E answer does not exceed $$$n$$$ because we can use $$$n$$$ operations of the second type so we can consider second parameter up to $$$n$$$.

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

For people interested, 3b1b-styled visual editorial for D. Zigzags this time with narration and as always, with visual dry-run of a testcase.

»
5 weeks ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

after reading editorial i feel D was easy i don't know what i was thinking during contest.

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

After seeing the MOD value for problem G, I was wondering, where/how FFT should be applied here. :)

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

https://codeforces.com/contest/1400/submission/90956921 can someone please explain why is this code not working. I have initialized everything as 0 first and then went on making the values which should be 1 as 1.

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

I loved this contest, specially the problems D, E and F, learned a lot of thouse!! DP with Aho-Corasick blow up my mind but after understand it was awesome!!

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

    Can you please explain the DP part(see below) of problem F x-prime substring?

    forn(i, s.size()) forn(j, trie.size()) 
    	  if (dp[i][j] != INF){
               dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);
               int nxt = go(j, s[i] - '1');
               if (!trie[nxt].term)
                  dp[i + 1][nxt] = min(dp[i + 1][nxt], dp[i][j]);
              }
    
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sorry, I didn't understand the autor's solution, I write my own recursive approach that think is easier to understand [http://codeforces.com/contest/1400/submission/91095834](my solution) PD: Also my Aho-Corasik is another implementation

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I hand run your code for the input s = '116285317' and x = 8. I was to able to understand finish and cnt array, but can you please explain the "out" and "link" arrays as they both remain zero for the aforementioned input? I know how Aho-Corasick algorithm works and it would be great if you could relate out and link arrays to equivalent arrays used in the Aho-Corasick link provided would really help me. Can you provide a better input(than mentioned at the top) which can make your solution more clear to me?

        Thank you!!!

        • »
          »
          »
          »
          »
          11 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Sure, these are the values that stores each array of my Aho-Corasik implementation:

          cnt[n] -> amount of words that end in node n
          finish[n] -> id of the word that end in node n (not important in this problem)
          fail[n] -> suffix link of node n
          out[n] -> end word link of node n (also not important in this problem)
          

          As you can see the BFS named buildf() calculate these values, so ALL possible transitions of the automaton are calculated beforehand.

          Hope this help you...

          • »
            »
            »
            »
            »
            »
            11 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thank you Johnny. I have drawn a trie(see below) for 8 prime set (5,3) (3,5) (8)

            xprimed2b930d3445b77c4.jpg

            Suffix link of every vertex is 0 except vertex 4 with suffix link 1 and vertex 2 with suffix link 3. Please correct me if I am wrong.

            When I ran the code for same input s = '116285317' and x = 8, I get :

            Fail[4] = 1 which is perfect.

            My question is why fail[2] = 0 ? Is it because in original string we have substring '53' and not '35'?

            I thought fail[2] should equal 3.

            May I know why you have taken MAXN=1e5+5 ?

            Again thanks Johnny for your time.

            • »
              »
              »
              »
              »
              »
              »
              11 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Man I just ran my code and got fail[2] = 3, don't know why you got 0. Anyway my advice is focus in the dp instead of the Aho-Corasik implementation (I've used it many times and it works fine to me, but you can use whatever you like)

              PD: The MAXN is just a value large enough, nothing special...

              • »
                »
                »
                »
                »
                »
                »
                »
                11 days ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Oh ok. Glad to hear that. It must be a manual error(as I hand run the code) by me. I am so sorry about that.

                The dp part looked magical at first but breaking it into smaller steps really helped.

                Finally, I got it.

                I have learnt a lot from this problem.

                I don't know how to thank you.

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

What language are adedalic's solutions written in?

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

Can someone explain the dp solution given for problem E. I couldn't get it.

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

Can someone please identify the problem with my submission for Binary String Reconstruction. 91054758

The logic is that, if s[i] = '1', I put a value at position i using a map as follows, if i+x and i-x are in range, m[i] = 2 indicating that at one of the two positions '1' has to exist, if one of the value is in range, m[i] = 1, indicating that there has to be one '1', else there is no answer. Now I look at positions of '0' in s and then just put '0' at both i+x and i-x if they exist. Also check that if i+x is now '0', then there could be a '1 at i+x and so i+2*x will be reduced by 1(coz for i+2*x, i+x will be a position of 1), similarly I check for if i-x is now '0', reduce i-2*x. Now if there is any 0 in map m, i.e, there was 1 or 2 and now has become 0, meaning 1 cannot exist at that position, I output -1. Else just output the answer.

Not able to understand the problem with the solution, please help.

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

*****************Why a O(2n) code getting TLE in problm C****************

Can anyone tell me please why this submission 90966915 is showing TLE? It was accepted till final standing and after final standing I've submitted the same code in offline also & which was accepted, see here 91082748. I can't understand whats wrong with me. advance thanks. pikmike Roms

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

    91117140

    I copy-pasted your submission 91117140 and it ran in $$$1918 ms$$$ and then I submitted it again with some comments and got TLE on test 7 91117335.

    Basically your code is slow because of the for loop you make to ans+='0'.

    Instead, using resize makes it run on $$$31 ms$$$.

    You got lucky that your code got accepted at all after the contest. These are minor fluctuations in judging time say ~$$$150ms$$$. Your code is basically slow.

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

      I was unable to identify the bug. thanks for your cooperation. But I've a little bit more to know. If you tell me some more details why ans = ans + '0' in the loop makes my code slow? Isn't it happening in O(n) time complexity? MiFaFaOv0

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

        When adding (concatenating) strings (and almost any object) using the + operator, each operand is copied, after which they are summing and the result is copied to ans. So O (ans.size()) for each addition, due to copying. If you use the += operator, then only the right operand will be copied, push_back works the same way, it will work in O (1) on average.

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

        I am sorry that I did not explain it properly. Khozhaev does it pretty well.

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

          its ok, but u tried much. thanks

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

if the edge <= 10 I will solve it...

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

Editorial not that good! Can be improved...

»
5 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

worst contest ever

»
5 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Yet another solution for G:

There will be at most $$$2m$$$ nodes with nonzero degree, let's call this set of nodes $$$V'$$$, and let $$$k = |V'|$$$. We'll take this part of the graph and solve it independently from the rest. Namely, for each $$$s \in [1..n]$$$, we'll find the subset $$$V_s \subseteq V'$$$ such that these are exactly the nodes $$$v$$$ for which $$$l_v \leq s \leq r_v$$$. For each such subset, we can use meet-in-the-middle and sum-of-subsets DP to calculate, for each $$$j$$$, the number of ways to choose $$$j$$$ independent nodes from $$$V_s$$$, and then multiply this with the corresponding binomial coefficient $$$\binom{z_s-|V_s|}{s-j}$$$, where $$$z_s$$$ is the number of nodes $$$x$$$ satisfying $$$l_x \leq s \leq r_x$$$ in the whole graph. Fortunately, over all $$$s$$$, there can only be $$$2k$$$ different values of $$$V_s$$$, so we do the second phase only a small number of times. Also the sum-of-subsets DP of the first phase needs to be done only once.

Code

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

problem D in c++ code

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

In problem G, how to calculate $$$c_s$$$?

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

    The cnt array serves that purpose in the editorial code.

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

      Thank you very much. But the tutorial didn't mention it. I hope the author can add this to the tutorial.

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

During solving this round, I understood that problem 1400E - Clear the Multiset is similar to 448C - Painting Fence. It's just rephrasing of the problem statement.

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

    But we should notice that: when the input is: 1 0 the output should be 0,instead of 1 This is why I was hacked when I submit the same code as what I submitted in the 448C.

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

In Problem F, how about the string 2222222232222222232...(1000 characters long)? Doesn't it have about 1000 19-prime substrings, each with length 9? Their total length would then be about 9000. What is wrong here?

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

    I thought the total length <= $$$5000$$$ remark is discussing the set of all possible distinct $$$x$$$-prime strings, and not the multiset of all $$$x$$$-prime substrings of the input or anything of that sort. But that can't be the case, as it is easily calculated with a small dp that there are $$$2399$$$ distinct strings which are $$$19$$$-prime, and their total length is $$$13739$$$. But the Trie generated from the $$$19$$$-prime strings still only has $$$4853$$$ nodes, because many prefixes are shared among those strings, and it is this number that determines the number of values of $$$y$$$ and the state space of the dp.

    A short Haskell program that calculates these numbers
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You're right. I misunderstood the remark. Thanks for the explanation!

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

There is a small typo in problem G (the factor of $$$(-1)^{|E|}$$$ is missing from the summation) . Other than that, it is a very nice writeup :)

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

With exact same approach as C, but using Java is giving me TLE. Anything I have missed to optimise? Any solution? My submission: 91120981

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

    Instead of filling w with -1, fill it with 1. Update it's value only when you need to, i.e. when s[i]=0 and you have to make w[i-x] and w[i+x] 0. I copy/pasted your code and made these changes and it got accepted!

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

      Thanks a lot! Actually the problem was in the Java version. I used Java 8, and in that even the changes you suggested gave TLE. In Java 11, both approaches worked fine. Java 11: 91203981, Java 8: 91203767

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

In zigzag the explanation should be i<j(l>k), right?

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

https://codeforces.com/contest/1400/submission/91201352 can anyone tell me why testcase 6 is failing

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

    use (long) instead of (int) for answer.

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

      i have used (long) in the code ,but it is failing

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

      My freind! just take a look at the code

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

        your accepted code in c++ you have to use long long

        include

        using namespace std; int main() { int t; cin>>t; while(t--) { int n; cin>>n; int a[n]; for(int i=0;i<n;i++) { cin>>a[i]; } long left[n+1]={0}; long long ans=0; long right[n+1]={0}; for(int j=0;j<n;j++) { for(int k=n-1;k>j;k--) { ans+=1ll*left[a[k]] * right[a[j]]; right[a[k]]++; } left[a[j]]++; for(int i=0;i<n+1;i++) { right[i]=0; } } cout<<ans<<endl; } return 0; }

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

I am not able to understand the DP solution of problem E, can somebody help me ?

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

In problem E, I have implemented a recursive solution where I compare the second operation ($$$r - l + 1$$$) with applying the first operations — subtracting minimum value of the range which splits the range into possibly multiple ranges with all positive elements and recursing further into those ranges. It passed all tests with 202ms in Java and implementation-wise, it's quite easy. I'm wondering if it's the tests were weak or the solution in practice runs faster. Anyone can reason about the complexity? Here's my solution.

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

Can someone please tell me whats wrong with my code:

	public class Codeforces {
		public static void main(String[] args) {
			Scanner input = new Scanner(System.in);
			int test = input.nextInt();
			while(test-->0) {
				String s = input.next();
				int n = input.nextInt();
				//System.out.println(s);
				//input.nextLine();
				char c[] = new char[s.length()];
				Arrays.fill(c, '1');
				boolean ok1 = true;
				boolean ok2 = true;
				for(int i =0;i<s.length();i++) {
					if(s.charAt(i) == '0' ) {
						 if(i+n<s.length())c[i+n] = '0';
						 if(i-n>=0)c[i-n] = '0';
					}
				}
				for(int i =0;i<s.length();i++) {
					if(s.charAt(i) == '1') {
					if(i+n<s.length() && i-n>=0 && c[i-n] == '0' && c[i+n] == '0') {
							ok1 = false;
						}
						else if(i-n<0 && i+n<s.length() && c[i+n] == '0') {
							ok1 = false;
						}
						else if(i+n>=s.length() && i-n>=0 && c[i-n] == '0') {
							ok1 = false;
						}
						
					}else {
						if(i-n>=0 && c[i-n] == '1')ok2 = false;
						if(i+n<s.length() && c[i+n] == '1')ok2 = false;
					}
				}
				if(ok1 && ok2) {
					for(char it:c)System.out.print(it);;
					System.out.println();
				}else System.out.println(-1);
			}
		}
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me with Question D, its giving me TLE on the 6 test case but i am not able to find where i am going wrong, even though my code almost matches the editorial. my code

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

Can someone explain why simple greedy doesn't work for problem B.

I mean,let's assume s<=w always. Total capabilities we have is p+f. Now take TOT=min(cnts,(p+f)/s) .We are left with (p+f)-(TOT*s).Let this be TOT1.

Now , take as much as war axes as possible.This is given by : min(cntw,(TOT1/w))

Final ans is summation of both results. But I'm getting WA on tes2.

Please HELP

My Solution

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

I can't figure out when will the answer be "-1" in C. Can anyone help me out please?

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

Thank you so much...your tutorial to C & D helped me a lot.

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

Can someone please explain why My Code is not working for problem C.

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

Can someone explain the dp solution of problem F(x-prime substrings) please?