ch_egor's blog

By ch_egor, 2 months ago, translation, In English

Thanks for the participation!

1379A - Acacius and String was authored by ch_egor, _meshanya_ and prepared by ch_egor, vintage_Vlad_Makeev

1379B - Dubious Cyrpto was authored by jury and prepared by DebNatkh

1379C - Choosing flowers was authored and prepared by grphil

1379D - New Passenger Trams was authored by Helen Andreeva and prepared by KiKoS

1379E - Inverse Genealogy was authored and prepared by voidmax and I_love_myself

1379F2 - Chess Strikes Back (hard version) was authored by 300iq and prepared by isaf27

Tutorial is loading...
vintage_Vlad_Makeev code
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it
  • +107
  • Vote: I do not like it

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

Thank you for the fast editorial.

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

pretest 2 was a nightmare. but anyway thanks for the fast editorial

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

I used binary search for B.

Here's my submission: 87322797

I basically fixed my lower bound and upper bound to M+(R-L) and M+(L-R). Let them be up and lo respectively. Now, we need some values of A.N such that the inequality lo <= A.N <= up is satisfied. As we know that a lies in the range L-R and that some value of N for some value of A always exists, for every value of A I used binary search to find for every A if some value of N exists.

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

    Explain pls!

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

      Here's my submission: 87322797

      I basically fixed my lower bound and upper bound to M+(R-L) and M+(L-R). Let them be up and lo respectively.
      Now, we need some values of A.N such that the inequality lo <= A.N <= up is satisfied. As we know that a lies in the range L-R and that some value of N for some value of A always exists, for every value of A I used binary search to find for every A if some value of N exists.

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

Can someone point out the flaw in my code? 87334189

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

My video Solution For Problem A And Problem B. Hope you like it

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

Difficulties are not seems like it is div2. Thanks for the fast editorial

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

If you are still getting WA in A, this is an edge case you probably missed.

1
13
abacab?bacaba

Output: No

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

This contest was a Nightmare for me.

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

My approach in C was almost the same as the editorial's approach.
If anyone wants to check the implementation, check out my submission 87337116. :)

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

Questions are quite interesting after many contest.

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

Please make others submission visible.

UPD they are visible now.

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

Were these problems supposed to be solved by 5-8 grade students?

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

    Maybe they were practicing for very similar problems. but still, I agree with you, it seems odd.

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

"Wrong answer on pretest 2" The contest summarized in 5 words

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

Why does it say that the blog was made 3 days ago?

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

Was it Div 1???

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

Fastest editorial, system testing and least submissions.. records been broken here.

Thanks to iynaur87 for the key update! :-)

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

Very similar problem to F has appeared on the 2019 Canadian Mathematical Olympiad before, you can check it out here.

Edit: you can check the solution to that problem here.

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

    Funny coincidence! I haven't seen this problem. I was inspired by the problem "Grid Guardian" from the GP of America, where you had to count the generalized version of grids from my problem.

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

Plz,tell my mistake for A Code: 87298100

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

    Consider this case

    1

    15

    abac?bacabac?ba

    Your output has two occurrences of "abacaba"

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

my approach to C:

find the maximum element among a[] and b[], if one of the maximum is a[i] then decrease n by 1, add a[i] to the answer, and change a[i] to b[i].

if not, then iterate over all sort and find out the maximum a[i]+(n-1)*b[i].

however this approach is getting WA on pretest 4, can anyone tell me why?

thanks in advance qwq

Update: found hack test case.

1
2 3
100 1
100 1
1 101
»
2 months ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

Extra fast tutorial

Extra level question(Difficulty similar to div1)

Extra ranks(3K rank after doing just 1 question)

Hope extra rating :)

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

For D, it is also very helpful, that an optimal starting time can always be selected, so that either the trains departure or arrival, coincides with some existing freight train.

Therefore, we can just check all those 2n possibilities, and obtain quite an easy solution, as then we just have to get the number of freight trains in 2 ranges.

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

Many of them solved C using Convex Hull Trick. Is it a standard problem?

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

It could be more balanced, if removed D, shift ABC to BCD and paste easy A.

By the way, problems are insanely amazing!!

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

This contest is too damn hard for Div.2. Aren't you Shaco?

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

Can F1 be solved with maximum bipartite matching and binary search?

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

    I thought of it too, but couldn't reach up to a solution.

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

Here's my approach for B:

We know that we need an $$$a$$$ such that $$$(m+x)/a=n$$$ where $$$n$$$ is any positive number and $$$x$$$ is just any number in between $$$r-l$$$ and $$$-(r-l)$$$. Now fix $$$a$$$ by looping from $$$l$$$ to $$$r$$$. Then $$$x$$$ will have 2 possibilities computed by using the modulo operator as follow:

$$$md1 = m \mod a$$$
$$$md2 = a-md1$$$

Where $md1$ is the number that must be subtracted from $$$m$$$ for the module to be zero and $$$md2$$$ is the number that must be added to $$$m$$$ for the modulo to be zero.

Now $$$b = l+md1$$$ and $$$c = l$$$ if and only if $$$md1 \leq r-l$$$ and $$$m-md1 \neq 0$$$

Or, $$$b = l$$$ and $$$c = l+md2$$$ if and only if $$$md2 \leq r-l$$$

Else, continue iterating on $$$a$$$

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

    can you explain, why two possibilities of x ? md1 and md2 ? can u elaborate this part ?

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

      As I said in the post, $$$m \mod a$$$ is essentially just the number you need to subtract from $$$m$$$ in order for $$$m$$$ to be divisible by $$$a$$$ so if that value is less then $$$r-l$$$ you can always choose $$$b$$$ and $$$c$$$ such that $$$b-c$$$ is your $$$md1$$$.

      But sometimes you need to add to $$$m$$$ rather then subtract from $$$m$$$ and thus the number to try here would be $$$a-md1$$$ and do the same as above.

      I hope it's more clear :)

      E: Submission with idea: https://codeforces.com/contest/1379/submission/87346264

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

    Yeah thank you Ahmad45123 , it's clear now

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

HELP Someone please tell me what's wrong in my code of C . Failed on Test 4 . https://codeforces.com/contest/1379/submission/87346998

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

Hi Guys, could somebody please help me to understand why this simple brute force solution for problem A gets WA on the 4th pretest? Thank you very much in advance!

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

    Found my mistake, just in case someone is interested, here is my accepted solution.

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

It would have been better if the contest was of 2:30 hrs.

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

    yes, however I would get "Wrong answer on pretest 2" for 30 more minutes :)

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

Problems were very nice! B was easier than A and A was definitely very tricky unlike usual A. Took me more than 30 minutes! I wonder if the partication was less due to unusual timing or difficult problems. C finally looked like as a usual C from the past (hard).

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

I had a bit different solutions for B and D.

For B, I tried all possible values of a, and then let $$$d = b - c$$$ , $$$z = m \ mod \ a$$$

Then $$$na + d = m \Leftrightarrow \ n = \frac{m - d}{a} \Leftrightarrow d = ka + z$$$

I checked only $$$k = 0$$$ and $$$k = -1$$$ to make shure that $$$n > 0$$$

Code

For D, lets solve problem for $$$ m \leq 10^5$$$. For fixed $$$t$$$ all segments where no freight trains are allowed to depart and should be canceled are in segments $$$[t - k + 1 + i\frac{m}{2}; t - 1 + i\frac{m}{2} ]$$$ for some $$$i$$$. Lets create array $$$a$$$ and add 1 to time when some freight train departs. Then answer is $$$t$$$ whith minimum sum of segment $$$[t - k + 1 ; t - 1]$$$. Let $$$d_i$$$ — time when i-s train departs. Now, lets check not all t from $$$0$$$ to $$$\frac{m}{2}$$$, but only $$$d_i + 1, d_i-1, d_i+k, d_i-k$$$ for all $$$i$$$. Instead of counting sum we can count number of trains in segment with upper_bound.

Why is it correct? I thought, if we can find better answer for another t, we can move this segment to the left or to the right and answer won`t change until we hit some train. So, this solution is also $$$O(n \log n)$$$

Code

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

Can Any Please One tell me what is the problem with the test case 42 in Problem A? 87356615

»
2 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Check out the detailed explanation of Problem A

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

Can somebody please explain B ?? Not able to understand what to do after fixing some arbitrary value of a.

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

can someone help me whats wrong in my code CPP- problem B 87357784

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

I am unable to understand the solution for Problem c. Can anyone explain it?

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

    Hi!

    Let's consider both arrays sorted in non-increasing order(greatest element first).

    The main idea is that we can take only one-type of an element of type-b at max ( why? because if you can take the current element of b why go for an element-b that has a lower value). (think).

    Now, let's iterate over all b's from start and see what is the max value we can take with them!

    How to do that? Let's say the current b[i] is bi , (note that array b and is sorted)

    It's understandable that we should take all the a's that are greater than this bi ( think). So we first calculate all the a's that are greater than bi. let's say the count is x and the total sum they provide is val

    Now, if ai (the type-a for our current bi) is not in that x, we'd have no choice but to take it if we want to use current bi.

    Hence we have two cases:

    • If ai >= bi (means ai is in those x) : ans = (n - x)*bi + val , because it's better to take x elements that have value greater than bi.
    • If ai < bi (means ai is not in x) : ans = (n-x-1)*bi + val + ai , because we'd have to take our ai if we want to use bi.

    Also, note that if we have x >= n it's just dumb to take any bi (think).

    So, all we need to do is iterate over all b and take max amount we can take.

    Here's my submission : 87331654

    Thanks!

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

      Wow Sir, Very elegant approach.

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

      @Dsxv @vjudge6 Can you help me with a test case which can point out what is wrong in my approach?

      My approach: Take the max b[i] (lets call it maxB), add all a[j] >= maxB to the val. Then go through all a[i] and if a[i] is already included, then update ans = max(ans, val+(n-x)*b[i]) else ans = max(ans, (n-x-1)b[i]+a[i]+val).

      Difference is that I think maxB will always give optimal result (which is wrong). Can anyone please give a hack test for this?

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

      Better explanation than the official tutorial. Thanks!

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

      @Dsxv, bro I tried to code what you explained in your post but I am getting a WA at TC5. I have been trying to debug it since last night but was unsuccessful to get my code AC. Please, go through my code and let me know where am I going wrong.

      link to my solution: https://codeforces.com/contest/1379/submission/87395143

      Your help and time would be much appreciated.

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

        Hi! Sorry for the delayed reply

        It's happening when, m-n-1 has value < 0.

        Here's your AC submission: 87406888

        Thanks!

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

          Thank You for the help, bro. I was not expecting any reply since as a sports programmer everyone of us has lot of problems of ourselves that needs to be debugged, but you talking out time to actually debug someone else's code was very generous.

          Keep on doing this great job, wish you high rating!!

          P.S: We all know how irritating it is to not get an AC even after brainstorming the logic.

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

      Hi.I am having a confusion if ai<bi(the largest b). Eg:- 7 4 1 5 If n=4, first element is seven.Now considering remaining three elements. According to you we will select 1 5 5 (sum is 11).But, if we take 4 4 4 (sum is 12).So, in this case we should not take the largest b. Am I doing something wrong? Please explain. Thanks!

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

        Not really! I will check my answer for every bi. Hence when I'll reach bi = 4 I'd have already visited my ai = 7 and that is the only value greater than me! so my answer would be bi*(n-1) + pref, where pref = 7. If I misinterpreted your doubt, feel free to ask again! Thanks!

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

          I did this for just largest value of b and calculated the max sort sum for remaining values.This is failing on Test Case 2. I got your approach which is the correct one but how this one is failing?

          include<bits/stdc++.h>

          using namespace std; vector<pair<long long ,long long> > v; vector v1; bool comp1(long long a,long long b) { if(a>b) return true; return false; }

          bool comp(pair<long long,long long> p1,pair<long long,long long> p2) { if(p1.first>p2.first and p1.first>p2.second) return true;

          if(p1.second>p2.first and p1.second>p2.second)
              return true;
          return false;        
          

          } int main() { int t; long long a,b,n,m;

          cin>>t;
          
          while(t--)
          {
              cin>>n>>m;
              v.clear();
              for(int i=1;i<=m;i++)
              {
                 cin>>a>>b;
                 v.push_back(make_pair(a,b));
              }
              sort(v.begin(),v.end(),comp);
          
          
              long long c=0;
              for(int i=0;i<v.size();i++)
                 c=max(c,v[i].second);
          
              long long sum=0;
              int pos=0;
          
              for(int i=0;i<v.size();i++)
              {
                 if(v[i].first>=c)
                 {
                    sum+=v[i].first;
                     pos=i;
                 }     
              }   
              n=n-(pos+1);
          
              v1.clear();
              for(int i=0;i<v.size();i++)
              {
                 if(i<=pos)
                   v1.push_back(n*v[i].second);
                 else v1.push_back(v[i].first+(n-1)*v[i].second);  
              }
              sort(v1.begin(),v1.end(),comp1);
          
              sum+=v1[0];
              cout<<sum<<endl;
          }
          
          return 0;
          

          } Thanks!

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

            I'm sorry but I am not here to debug codes! If there's anything wrong with logic feel free to ask.

            Also, use some links while sharing code :p

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

      hey, i dont think ur logic will hold...... in case 2 where ai<bi,what if n=x+1,would u still go for ai,or would u choose any b[i],from already chosen a[i]'s

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

        I'd leave this case upon your imagination! (note that you can choose to take no bi)

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

Approach to problem D: squeeze all m_i to a circle of length m/2. For all points with coordinate p in the circle, (p, p + k) represent locus of points where t cannot be 'inside' it. Then, the problem is equivalent to removing minimum number of points on that circle such that there'll exist two consecutive points of distance at least k. To find it, we can keep track of # (say ins[] )points inside (p,p+k) for all p using pointers (87364059). Then, we can take the point p with minimum ins and delete all point inside (p,p+k). However, I couldn't pass it. Can you find mistakes in this approach?

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

Can someone help me understand where my code is giving wrong answer.Thanks in advance https://codeforces.com/contest/1379/submission/87357034

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

I think Div2 B has weak test cases, my solution got AC https://codeforces.com/contest/1379/submission/87373765, but it should be TLE at this simple test case:

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

Problem A and B has same difficulty rating but problem B has far more points than A. Even(for me) B seems easier than A...Is it fair? Would get more (+) if started with B... :(

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

Can someone share in what topic/concept question C belong? I want to practice more such problems, but I am unable to get where exactly does this belong.

P.S: Contest time should have been 2:30 mins.

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

Can anyone tell me what's wrong with this submission? Implements the same idea as the editorial but gets WA on test 5;(

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

Did anyone else waste time trying to solve problem A in O(n)? :|

In case the count of 'abacaba' was 0 (>=2 or 1 are easy cases) I did the following:

Created a list of starting indexes of occurrences of possible 'abacaba'.

Then I iterated over the list, realizing the that a problem can occur only in the following: If the next possible starting index is +4 or +6, and after the current occurrence there is 'caba' or 'bacaba' respectively.

For example, 'abac???caba' is a problem, and 'abacab?bacaba' is a problem. These are the only types of problems, if this doesn't happen, you've found your starting index.

In the meantime the solution was to just plug the substring and count the number of occurrences :<

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

There are a lot of grammatical errors in the tutorial.

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

Can anyone check this code for me , I get WA on test case 179 in pre test 2 :< ( Problem A )

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

    If you get num == 1 after the first iteration answer will be "YES". It should not depend on "codinh"

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

    Sir, you can check for this test case:

    1
    19
    abac???cabaz???????
    

    It prints out No, but the answer is possible: abaczzzcabazabacaba

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

Why was the time limit for problem F so tight? My $$$\log^2$$$ solution wasn't able to fit in the 2s time limit (but should pass given 3s).

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

    Our bad, none of us wrote a solution with 2d tree. All our AC solutions use 1d tree which work $$$\leq$$$ 0.4 s

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

    hey, can we do problem c using concept of unbounded knapsack?? thanks in advance..

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

We can also solve D by dynamic segtrees .. its very much intutive (just like brute force) that way.

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

I made a greedy strategy for Problem C but it's giving the wrong answer but I can't figure out where it's going wrong.

I find the pair with max Bi (if there are multiple Bi's with max value) than I select the one with highest Ai. Now we have 1 Ai and n — 1 Bi. Next for every Ai greater than my chosen Bi, I replace that one Bi with Ai. This should be optimal, apparently, it's not. Can anyone help me out here? I know this explanation is messed up and hence I am sharing the link to my unsuccessful submission, hope you'll get an idea.

https://codeforces.com/contest/1379/submission/87394947

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

    Max Bi isn't always optimal:

    1
    2 2
    1 10
    7 8
    
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks man.. I'll try again.

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

    hey, can we do problem c using unbounded knapsack??

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

      I have no idea man. That's too advanced for me. Pls ask someone else.

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

can someone explain editorial of problem, I am not getting it?

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

One of the most difficult division 2 contest I ever participated. even the first problem was of 1500 rating.

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

A seriously awesome contest after a long time. This one Makes you learn the importance of time where a single question require high implementation and multiple concepts.

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

Why codeforces site is getting shrink every time i am opening it in google chrome? What's wrong with the site is happening I can't figure it out?

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

I usually use java to solve problems. So I was using Java to solve Problem B today and got TLE. This has never happened to me in codeforces before. Can anyone help me figure out what might causing the problem? Java : Solution(TLE) C++ : Solution(AC)

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

Explanation for problem B

m = n*a + (b-c) Let us say x = (b-c) Then it becomes m = n*a + x which is of the form, Dividened = Quotient * Divisor + remainder Then range of a, b, c is [l, r] So then range of x becomes [l-r, r-l] We need to observe that (m-x) % a should be equal to 0. Then only we can get a quotient n. So we iterate a from [l, r] We calculate mod = m % a.

Case 1:

when we get mod i.e; (x as <=r-l) which is in the required range also the (m-x) != 0 because when it is zero, then n is 0 which is not we want. Then b = r and c = r — rem because x is b-c = rem <= r-l We can also have b as l + rem and c as l.

Case 2:

Sometimes we get (m-x) as <= a or (m-x) == 0. in that case, we add a to make (m-x+a)>=a. Here (x-a) is obviously negative then only (m-(x-a)) >= a. We take (m-x+a) and we check whether our rem = (x — a) <= r-l If it is true, then our c>b, rem = (b-c) = (x-a) if b = l then c = l — x + a or if c = r then b is r + x — a

(c — b) = (a — x) < = (r-l)

Code Link

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

I am getting wrong answer in test case 5 in problem C. Can Someone please tell me where i am wrong? Submission

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

    You do not handle the case where n is smaller than m. With such input the binary search can return an index bigger than n, and then your formulars are not correct because they calculate with some negative flower count.

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

I had a different solution 87485483 in 1379A - Acacius and String. Since the length of n and the length of "abacaba" is small. I bruteforced all possible variations of "abacaba" with '?'. Then I try all possible places those variations can occur and check if it create another "abacaba".

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

can someone explain question no 1 ACACIUS AND STRING? string "a?b?c" can be transformed into strings "aabbc" and "azbzc", but can't be transformed into strings "aabc", "a?bbc" and "babbc". THIS LINE MAKE NO SENSE TO ME .it's fine for the first part but after that i can't make sense.. how those strings are not possible.

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    • "aabc" — not possible because one of the '?' was not converted to any alphabets.
    • "a?bbc" — not possible because the in the output string all the '?' must be changed to an alphabet.
    • "babbc" — not possible because we cannot change a character in the input string which not a '?'.
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm both bad at English and Russian.

Everytime I see the problem I need comoputer to help me. That's fun!

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

It is better to write "In the form of $$$2^n-1$$$" than "almost a power of two".

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

Can anyone point out my mistake in div2-C-"Choose Flowers" question. I have commented my code for better understanding.My code

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

https://codeforces.com/contest/1379/submission/87865452

Can anyone tell me mistake in this code?(Problem A)

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

    Hi, you can check for this test case:

    1
    19
    abac???cabaz???????
    

    It prints out: abacabacabazzzzzzzz, it has two occurrences of abacaba.

    But the answer could have been something like: abaczzzcabazabacaba

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

88386178 Can someone help me to find my mistake?

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

I have tried to make editorial for questions A-D . please have a look. Language :- Hindi

programming Language :- C++ https://www.youtube.com/watch?v=Omy25cs6JY8&list=PLrT256hfFv5UiRIzkAk6iSHwpwJrJKGMz

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

can anyone please explain why (i — remainder)(where i is the value from l to r) is being done in question b?

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

hey, can we do problem c using unbounded knapsack??