shishyando's blog

Codeforces Round #708 Editorial
By shishyando, history, 14 months ago, translation, In English

We are really sorry to make the round unrated. Anyway, we hope that you enjoyed the problems!

1497A - Meximization

Idea: shishyando

Tutorial
Implementation

1497B - M-arrays

Idea: Artyom123

Tutorial
Implementation

1497C1 - k-LCM (easy version)

Idea: shishyando

Tutorial
Implementation

1497C2 - k-LCM (hard version)

Idea: isaf27

Tutorial
Implementation

1497D - Genius

Idea: shishyando

Tutorial
Implementation

1497E1 - Square-free division (easy version)

Idea: Artyom123

Tutorial
Implementation

1497E2 - Square-free division (hard version)

Idea: isaf27

Tutorial
Implementation
 
 
 
 
  • Vote: I like it
  • +334
  • Vote: I do not like it

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

SpeedForces

→ Reply
»
14 months ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

Point distribution was weird imo but Questions were really good tho.

→ Reply
»
14 months ago, # |
  Vote: I like it +22 Vote: I do not like it

For C2 — legend+ary

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

Problem A — Implementation based

Problem B — Implementation | Constructive (Great Problem)

Problem C1,C2 — Intuitive | Constructive (Make Cases and you are done with both problems)

Problem E1 — Simply Math | Implementation (Prime factorization)

A great Round shishyando and Artyom123 with great and interesting problems. Hope to see your next round soon !!

→ Reply
»
14 months ago, # |
  Vote: I like it +3 Vote: I do not like it

E2 and D are interesting problems overall.

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it -68 Vote: I do not like it

    Lesser number of submissions doesn't make a problem interesting

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

    I think so. I am not able solve the problems, but reading the resulotion helps me a lot in understanding usage of DP. Love this round so much!

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

Really liked the problems.

→ Reply
»
14 months ago, # |
  Vote: I like it +418 Vote: I do not like it

Though I'm a tester, I want to say that C1 is the very beautiful hint for C2! Without C1, C2 can be the hardest problem in the contest.

→ Reply
  • »
    »
    14 months ago, # ^ |
    ← Rev. 2   Vote: I like it -9 Vote: I do not like it

    Agreed, I literally copied my code from C1, made minor changes, then submitted C2.

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

    Yes, The magic number of the problem, 3, seems rather arbitrary and unintuitive at first.

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

    lmao i gave 1.5 hours in upsolving yesterday and couldn't get C2 as i didn't look at C1 First. Now after reading the editorial i can see how intuitive it is.

    → Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain in detail math behind C1?

→ Reply
  • »
    »
    14 months ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

    It was simple first if n is odd then just print 1 n/2 n/2

    if n is even then check for if n/2 is even then print n/2 n/4 n/4 if n/2 is odd then print (n/2)-1 (n/2)-1 2

    we can extend this same logic in C2 by simply printing 1 , (k-3) times then taking n=n-(k-3) in C1

    → Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

    No math just you have to figure out basic logic that's it the one who did it can easily get through

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

    n can be of the form 4*k , 4*k+1 , 4*k+2 , 4*k+3 (for some k>=0) case 1: n = 4*k ans = k ,k, 2*k LCM = 2*k

    case 2: n = 4*k+1 ans = 1 ,2k ,2k LCM = 2k

    case 3: n= 4*k+2 ans = 2 , 2k , 2k LCM = 2k

    case 4: n = 4k+3 ans = 1 , 2k+1 , 2k+1 LCM = 2k+1

    → Reply
»
14 months ago, # |
  Vote: I like it +72 Vote: I do not like it

I went straight to C(hard) without looking at C(easy) since I didn't want to be misled by some simple solution that only worked for simple testcases but not hard ones... instead I fumbled around for an hour looking for a general solution without realizing the k=3 case is all you need. That really backfired on me.

→ Reply
  • »
    »
    14 months ago, # ^ |
    ← Rev. 2   Vote: I like it +2 Vote: I do not like it

    The scoring distribution: 500 — 750 — (750 + 500) — 1750 — (1500 + 1500) It was pretty much clear, C1 was supposed to be harder

    → Reply
»
14 months ago, # |
← Rev. 4   Vote: I like it +22 Vote: I do not like it

At the risk of my submission soon being systested, I think E2 can be solved greedily.

Construct the greedy intervals from E1. Then, at most K times, consider all pairs of adjacent intervals. Compute the number of changes needed to merge all pairs of adjacent intervals in $$$O(n)$$$ and then just merge the best one, and update the array so that excess is put at impossible values.

It works because in the solution you will never remove a value completely from an interval. So taking suboptimal merger will never help since it isn't actually going to reduce a merging cost.

Since you always make at least one change, you repeat at most $$$k$$$ times so it is $$$O(nk)$$$. I think it can be optimised to $$$O(n)$$$.

UPD: I think it cannot be optimised to $$$O(n)$$$, sorry. I thought that maybe you could save computation by only calculating the effect of the merger rather than recalculating every cost, but that's still $$$O(n)$$$.

UPD2: WA47, I wonder if greedy is just wrong here or it's a problem with the code...

UPD3: Assuming that you are merging intervals, the solution is optimal. However, it is also possible to split up an interval, so it does not work.

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

    Can you explain a bit more in detail about splitting intervals? I had the same reasoning and (theoretical) solution as you as well as WA47 and would like to know what the logical error is.

    → Reply
    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      Say there are just three intervals originally. The greedy solution wants to subsume the middle interval into either the left or the right interval. However, it is also possible to subsume the left part of the middle interval into the left interval and the right part of the middle interval into the right interval. It is possible that this is less costly.

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

    what do you mean by best one? does it mean that bigger the interval, the better it is? or anything else? btw approach is nice. Thank you !!

    → Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for the problems!

→ Reply
»
14 months ago, # |
  Vote: I like it +20 Vote: I do not like it

even despite unrated, this was the best round ive taken in a while. clean and concise problem statements. thank you so much for the round. :D

→ Reply
»
14 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Checkout this problem for a variant on problem A.

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

    I recalled the problem while giving the round today, lovely coincidence.

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

Video Tutorial B:https://www.youtube.com/watch?v=l9RQpnyIOXw

Video Tutorial A:https://www.youtube.com/watch?v=-CK_6lqs1hc&t=5s

→ Reply
»
14 months ago, # |
  Vote: I like it +1 Vote: I do not like it

What are "constructive" problems? can anyone tell. how to become good at these?

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Even though I am just starting out, I must say I loved this contest! Great work shishyando

→ Reply
»
14 months ago, # |
  Vote: I like it +23 Vote: I do not like it

"...it is easy to see that..."

Writing that sentence is like begging for downvotes. Remember, editorials are written for those not able to solve the problem. Telling them how easy it is is no good idea.

→ Reply
»
14 months ago, # |
  Vote: I like it +11 Vote: I do not like it

From problem D: "Then in binary form weight has its k-th bit set true if and only if j < k < i" Shouldn't it be j <= k < i ? Because we have for example 10000 — 00100 = 01100

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the round, although I couldn't participate.

Problem D is beautiful.

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it ok that i got TL in E2 with O(nk log n + max(a_i)) complexity ?

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

    Is your max(a_i) per test case, or in total? If it's per test case, then it would be O(nklogn+max(a_i)t) which is too much

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

      it's in total, I need it to precalculate prime numbers which are less than 1e7, I passed E1 that way.

      → Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Help needed 110230087 for problem 1497B - M-arrays

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

    Your Solution is failing for testcase:

    1
4 7
3 4 3 4 
Your Output: 0
Correct : 1

    Corrected 110257624,
    Just changed m/2 to (m+1)/2 in FOR loop

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

    You also have one more mistake.

    If i=0 => m-i=m, but m can not be a reminder by mod m. So you have to check v[i] and v[(m-i)%m].

    → Reply
»
14 months ago, # |
  Vote: I like it +5 Vote: I do not like it

For me C2 strikes so fast even I hadn't thought of it...it just dropped from the sky :)

Simply, considering 1 1 1 1 ... upto k-3 and the C2 becomes C1

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

    I think if there was no C1 then people may have a hard time coming to this solution for C2.

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

I used binary search for C1 & C2, didn't think it can be done in O(1) too :( My solution Great contest though! <3

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

    I am curious while doing binary search how you got the idea that low is the ans instead of mid ??

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

      See, the thing about binary search is that is always drifts towards the right answer. Similar thing is happening here.

      Initially, high = ⌈n/2⌉-1, low = 1 and during first iteration, mid = ⌈n/2⌉/2.

      Now if you look carefully, for first case (when n is odd) and for second case (when n is even but not divisible by 4) the answer is actually, (n-2*(⌈n/2⌉-1), ⌈n/2⌉-1, ⌈n/2⌉-1) and for third case(when n is even as well as divisible by 4) the ans is (n-⌈n/2⌉, ⌈n/2⌉/2, ⌈n/2⌉/2).

      So you must have already observed that for 1st & 2nd case, the ans is initial value of high, (n-2*high, high, high) and for third case ans is the initial value of mid, (n-2*mid, mid, mid)

      For the first two cases, the if condition will execute only once when mid=high, i.e., low=high=mid, and when this happens high will become less than low and it'll come out of the loop, so the ans will be low, [n-2*low, low, low] and for the third case, the if condition will execute only once, when mid is the ans, let's say value of initial mid is mid1, so for all further iterations, the if condition will never execute since high = mid1-1 and the value of low will keep on increasing until it becomes equal to high+1, i.e., low = high+1 = mid1, so again the ans is [n-2*low, low, low].

      → Reply
»
14 months ago, # |
  Vote: I like it +1 Vote: I do not like it

The dp of E2 can be solved in O(nk). https://codeforces.com/contest/1497/submission/110252728

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the reason for the unusual memory limit in Problem D?

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

    I'm assuming the reason was to prevent the more obvious solution with a dp[n][n] table, which would need to store up to 25,000,000 ints = 100 megabytes.

    → Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why it is necessary to use map instead of unordered_map in 1497B - M-arrays? I submitted both versions but only map got AC but unordered_map one got WA on test 3. map version-> 110262091 unordered_map version-> 110262159

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    It's happening mostly because of collision, refer this to use a custom hash for unordered map. I've used the same in my submission.

    → Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Using cnt[i] may create a new element (cnt[i]=0) in map. And it may cause rehashing of unordered_map, iterators are invalidated (see "Iterator invalidation" here), and for-loop continues working with invalid iterators, which causes undefined behaviour. In usual map creating new element does not invalidate iterators, so UB won't happen. But u still got lucky that these extra zeroes in your map don't change result of your program.

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

      thanks for the above link I learned a new thing...

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

    My solution by using unordered_map 110274693. I just avoid new insertion and deletion or such kind of invalidate iterator operations that mentioned in this Your text to link here... given by KostasKostil.

    → Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I really like how C1 is a hint for C2.

→ Reply
»
14 months ago, # |
  Vote: I like it +3 Vote: I do not like it

C1 750pts

C2 500pts

→ Reply
»
14 months ago, # |
  Vote: I like it +54 Vote: I do not like it

Problem E is similar to this problem.

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If Only I submitted C1 after My C2 was accepted!

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i am curious while doing C1,C2 problem how people were able to come up with the idea of for n%2 == 0 ans is n/2,n/2,2 and for n%4 == 0 ans is n/2-1,n/2-1,2 and so on.During the contest I made a pattern for 1 to 11 but i was unable to intutively guess this solution .Can anyone recommend the problems that i can do for increasing my intution for doing this type of problems thanks

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

    sorry for late response.I made a patter up to 23 before getting the right answer. My cases was if n is a multiple of 3 we done (n / 3, n / 3, n / 3), and it was difficult after that. I sais to myself it the limit is n / 2 i will try to be near to n / 2. and for each number i put n / 2 and see what can be done. I think the best is to go up to a limit (say 50) and if you don't see a pattern maybe it's not the right solution.

    → Reply
»
14 months ago, # |
  Vote: I like it +3 Vote: I do not like it

There is an $$$O(nk)$$$ dp solution in Problme E2.

At first, we can let $$$a[i]=mask(a[i])$$$. Assume $$$dp[i][j]$$$ denotes we consider the first $$$i$$$ positions, after making $$$j$$$ changes, the minimum answer we can get and the maximum position where the begining of the last segment at. So we can just maintain $$$last[i]$$$ which denotes the maximum position $$$j$$$ where $$$a_j=a_i$$$ (expecially, if $$$a_i=0,last[i]=i-1$$$) and make transfers.

The key observation in the solution is that if we change the number $$$a_i=x$$$, and for the first $$$j>i,a_j=x$$$, we should let $$$last[j]=last[i]$$$. But actually, there is no need to do that, we can still get the right answer.

See the code for details.

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

    Stuck in E1. In sample test case 1, should't answer be 2 ? Isn't it valid -> (18, 6, 4), (2, 1) ?

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

      We can't change the order of the sequence while dividing.

      → Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me how to reach to the solution for $$$C2$$$. I am asking this because $$$C1$$$ made a path for $$$C2$$$. So, can someone give some mathematical proof or logical way to approach such problem

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

    Achieving lcm of n / 2 lead intuitively (to me) to take n / 2 everywhere. now we can see that we can put n / 2 at most 2 time and i will remain a 1 case left.(that leads to k = 3 case). you can also think i put the same number some number of time and i put 1 everywhere since 1 does not increase the lcm. But i think it's very difficult to figure out alone without a hint.

    → Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

for the tutorial for c2,

(1+1+...+1)+(a+b+c)=(k−3)+(n−k−3)=n.

shouldn't it be (k-3) + n-(k-3) or (k-3) + n — k + 3?

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

Here is another $$$\mathcal{O}(nk)$$$ solution to 1497E2 - Square-free division (hard version).

For the first part, after normalization, instead of left[i][j] which is a bit bothering, we only need to find pre[i], which is the rightmost index to the left of the current index that shares the same value as the current index. This is very simple.

Then for the second part, for each change number j, we store best[j] denoting the minimal pair (segs,-last_start), and second_best[j] denoting the second minimal pair (segs,-last_start). Here last_start is the start index of the last open segment, and segs is the number of segments.

During the DP, if the last open segment can contain the new element, everything remains the same. Otherwise, we choose either to start a new segment (so that j does not change), or to change the current element (so that j becomes j+1).

Note that there would be cases that second_best becomes better than best, in which they should be swapped.

Code: 110279809

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

    Can we solve it using binary search + greedy?

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

      I do not know whether it is possible, but I think that would be hard.

      → Reply
      • »
        »
        »
        »
        14 months ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        Like we will fix the max number of elements per segment and then try to put the elements greedily. Whenever we find a repeated value we will replace it with a very big prime number.(of course considering the restriction of k)

        If it is possible then we set lo=mid+1 else hi=mid-1 Then the answer would be ceil(n/hi)

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

    You may solve our problem here using your observation.

    → Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain how left[i][j] is calculated in E2. I am not too comfortable with two pointers, perhaps there is any other way to calculate it? I understood the second part of the solution, the first part bothers me.

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

    Umm.............anyone? It will be really helpful if anyone could.

    → Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is there any way to solve E1 problem using binary search??

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

    No need of binary search just fill the elements greedily, you will get the answer

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

      BhanuPratap Stuck in E1. In sample test case 1, should't answer be 2 ? Isn't it valid -> (18, 6, 4), (2, 1) ?

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

        You cannot reorder the elements. The first test case is 18 6 2 4 1

        → Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For C1 wasn't there suppose to be a case when n % 3 == 0.The answear would be then n / 3 , n / 3, n / 3?

→ Reply
  • »
    »
    14 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    You could analyze that, but that is not needed. The solution explained in the editorial says if n is odd you do A and if n is even you do B, no need to add more cases. This is a typical bad practice from beginners.

    If n is a multiple of 13 you could answer 6*n/13, 6*n/13, n/13. But it would be silly to add such a case

    → Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Now let's relax dp values. When we consider an edge {i,j},tagi≠tagj we try to solve problem i after solving dpj problems ending with j, and problem i after solving dpi problems ending with i. It means that dpi=max(dpi,dpj+p), dpj=max(dpj,dpi+p) at the same time, where p=|si−sj|.

Can anyone explain this part of the editorial of problem D?

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

    An important part that the editorial misses is that we can only jump back once that is from j to i ;j>i, try to prove it yourself.

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

    Even i am not able to get this part....

    → Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am getting wrong answer for E1 in test 3. I cannot find out where I am making a mistake. Can someone please help? my submission is : 110286186

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

    Can you tell me why (18, 6, 4), (2, 1) are not valid sequence for first test case of E1??

    → Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for C1 and E1 which give me some ideas about hard version

→ Reply
»
14 months ago, # |
  Vote: I like it -14 Vote: I do not like it

include<bits/stdc++.h>

using namespace std; int main(){ int t; cin>>t; while(t--){ int n; cin>>n; int tag[n]; int i,j; for(i=0;i<n;i++){ cin>>tag[i]; } int s[n]; for(i=0;i<n;i++){ cin>>s[i]; }

long long int ans=0;
  for(i=1;i<n;i++){
     for(j=0;j<i;j++){
        if(tag[i]!=tag[j]){
           ans=ans+abs(s[i]-s[j]);
        }
     }
  }
  cout<<ans<<endl;

} return 0; }

//can some one explain why logic is not true. for the same test case i am attaching a picture

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

    if j1 is greater than j2 then 2^j1-i is always greater than 2^j2-k for all i and k less than j2 .if someone still didn't get the logic you can message me but please help me

    → Reply
»
14 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Guys I'm really sorry I know posting your code and asking why it's giving me an error is a sure-fire way to get downvoted but I really have no choice, I have commented neatly and explained the code for problem D, but I keep getting a run-time error on TC-2, can anyone please help me out

Here is the code : Python 3

Thank you in advance :)

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

    it's because in your code first of all you didn't memoized all the states and 2ndly recursion tree for your code does not form a DAG(because yours is cyclic) which is necessary condition for any dp/recursion problem. In simpler words you end up calling a state which initially made you call these states.

    → Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For a case where n = 3z ,z being an odd natural number, isn't the answear (z, z ,z), not (1, n / 2, n/ 2) as it is specified in the editorial ?

→ Reply
»
14 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Guys is there an algorithm involved in B problem. Or is it an only math based problem? What should be said ?

→ Reply
»
14 months ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

I can't understand what is the wrong here can you help me 110316296

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello Everyone, Can some one tell me, where I am getting wrong in problem E2? I am getting WA on 8th testcase.
My solution.
Thank you in advance !!

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone provide better explanation for D and E2?

→ Reply
»
14 months ago, # |
  Vote: I like it -15 Vote: I do not like it

C1, C2 sucks :((

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

Hi, guys! May u help pls find out why do I have TL in E1 ?

I run the sieve to get least devisors of all numbers from 1 to 1e7. Which is 1e7 * log(log(1e7)) Then for each a[i] I get mask whish is 2*1e5 * log(1e7) in worst case.

So totally it is less then 1e9. But what's wrong?

My submission: https://codeforces.com/contest/1497/submission/110540450

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain the reason why am i getting TLE on test case 102 on this submission but the exact same code gets AC here when i change 'long long' to 'int' with no other changes for problem E1.

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain this line in editorial of div2 B "In this array the amount of x and the amount of m−x should differ not more than by 1, that's why we need to make max(0,|cntx−cntm−x|−1) arrays, containing a single number (x or m−x) that is more common."

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In div2B why the counterpart of x is m-x. If m=5 and x=13 then counterpart of x will be 5-13 = -8 but we know that we need only 2 to add to 13 to make their sum divisible by 5. Instead it should be m-(x%m). Can anyone tell whether I'm correct or going wrong ??

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

    its actually m-(x%m),that's why it is written that take each number modulo m.

    → Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Omg. I was amazed when I read the tutorial for Problem C2. I accepted C1. After that, I tried to think and find solution for C2 for 1 hour before I gave up. That's amazing. That's unbelievable. That's incredible.

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

Can somebody tell why my submission for problem E1 fails on test case 2:

https://codeforces.com/contest/1497/submission/113704368

Thank you!

Edit: I found my mistake. The function returning the reduced integer was wrong. A silly mistake!

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For B, why is it $$$max(0, |cnt_x-cnt_{m-x}|-1)$$$? If the counts differ by 1, won't we have one additional array? Shouldn't this be $$$max(1, |cnt_x-cnt_{m-x}|)$$$?

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

    If the counts differ by 1 we can always include that extra element in our array. It will not violate the rules since we need adjacent sum to be divisible

    → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem {1497B — M-arrays} I think unordered_map works well instead of map but it gives wrong answer , don't understand why?

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The idea behind E is https://www.geeksforgeeks.org/count-of-pairs-in-an-array-whose-product-is-a-perfect-square/

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

1497C1 — k-LCM (easy version) shishyando I tried problem and found a solution which is best and easy to understand

include<bits/stdc++.h>

using namespace std;

define ll long long int

define rep(i,a,b) for(int i = a; i < b; i++)

void solve() { int t; cin>>t;

while(t--){
    int n,k;
    cin>>n>>k;

    int res[k];

    if(n == 3){
        res[0] = 1;
        res[1] = 1;
        res[2] = 1;
    }
    else if(n %2 == 0){
        if((n/2) % 2 == 0){
            res[0] = n/2;
            res[1] = n/4;
            res[2] = n/4;
        }
        else{
            res[0] = (n/2)-1;
            res[1] = (n/2)-1;
            res[2] = 2; 
        }
    }
    else if(n%2 != 0){
            res[0] = n/2;
            res[1] = n/2;
            res[2] = 1;
    }
    for(int i=0;i<k;i++){
        cout<<res[i]<<" ";
    }
    cout<<endl;
}

}

int main() { solve(); return 0; }

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why my code is giving TLE, I think it is completely right Time Comlecity is O(n*sqrt(a[i])) ->
<=10power 9 Please Help me

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

void solve(){
    // int MOD=998244353;
    int n,k;cin>>n>>k;

    map<int,set<int>>vertices;
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        vertices[a].insert(b);
        vertices[b].insert(a);
    }
    if((n%2==0 and k>=n/2) or (n%2!=0 and k>n/2)){
        cout<<0<<endl;
        return;
    }
    
    while(k--){
        for(auto it:vertices){
            if(it.second.size()==1){
                int a=it.first;
                int b=*(it.second.begin());
                vertices[a].clear();
                auto i=vertices[b].find(a);
                vertices[b].erase(i);
            }
        }
    }
    int c=0;
        for(auto it:vertices){
            c+=it.second.size();
            
        }
    cout<<c<<endl;
    
    return;
}

int32_t main(){
    int t;cin>>t;
    while (t--){
        solve();
    }
    return 0;
}
→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please help me understand why this solution for E2 works on all tests except 47?

→ Reply