74TrAkToR's blog

Codeforces Round 954 (Div. 3) Editorial
By 74TrAkToR, history, 5 days ago, In English

Thanks for the participation!

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +153
  • Vote: I do not like it

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

Fast Editorial♥

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

Can anyone tell me what's wrong with my solution for problem D? 267065372. It's a simple brute force solution but I still got WA on test case 2.

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

    64-bit integer i assume

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

      Are you saying that the default 32 bit int isn't big enough? If so: I resubmitted and replaced everything with long long, and it got the same WA. So the error is for another reason.

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

    your code is wrong

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

      Could you be more specific? I know that the code is wrong, but I'm trying to find where I made an error.

      → Reply
      • »
        »
        »
        »
        4 days ago, # ^ |
          Vote: I like it +4 Vote: I do not like it 
        else { // not at edge, ops is less than 2
    int first = s[0] - '0';
    int last = s[s.length() - 1] - '0';
    cout << first * last << "\n";
    printed = true;
    break;
}

        I think this is what causes WA, in this case n=3 and s[1]='0', so there are 4 total variants: if string s='a0b', then the variants are 10*a+c, a+c, 10*a*c, a*c. You always chose variant a*c, but if for example s=303, then your code outputs 9, but the correct answer is 6 (a+c).

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

          Ah, you're totally right. Thank you for catching this!

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

for problem A you can brute force it

→ Reply
»
5 days ago, # |
  Vote: I like it -26 Vote: I do not like it

E was awesome!!

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

why does my submission give TLE on test 3 , for problem B

https://codeforces.com/contest/1986/submission/267087342

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

    pass the matrix by reference instead of value

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

    bool testCondition(vector<vector>matrix, int i, int j, int n, int m)

    Use pass by reference here,

    bool testCondition(vector<vector>&matrix, int i, int j, int n, int m).

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

    I think the problem is that you are passing the $$$matrix$$$ array to $$$testCondition()$$$ by value, which creates a whole new $$$matrix$$$ object. What you need to do is pass it by reference, using the & operator

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

    Hey, every time you run testCondition() you end up copying over the entire matrix, which is slow. To avoid this you can do place a & before the matrix, so instead of passing over the entire matrix, you're just passing over the pointer to it. This changes your function from

    bool testCondition(vector<vector<int>> matrix, int i, int j, int n, int m)

    To

    bool testCondition(vector<vector<int>> &matrix, int i, int j, int n, int m)

    Submitted and it worked 267088502

    → Reply
»
4 days ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

I wondering for G, the constraint on n of hard version differ from the the easy very with only 5 as muplicatif factor. As in the editorial the complexity of hard is nlogn what's the expected complexity of the easy version?

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

    I think it's about accuracy. you must write a code with good constant to pass hard version

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

    It's a memory thing. My solution for G1 takes around 70MB so on G2 it gives MLE

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

    There are $$$O(n \sqrt n)$$$ and $$$O(n \sqrt n log \ n)$$$ solutions that pass the easy version

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

Had fun! Thanks.

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

super fast editorial

→ Reply
»
4 days ago, # |
  Vote: I like it +6 Vote: I do not like it

The problem setter is very clever i mean look at the constraints(n=20) of problem D which forces you to think a some bruteforce or some DP approach so no one will go to the logical part of that which is easy at all.

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

    Oh yes I fell into that trap :( I spent a good 15-20 minutes trying to optimize iteration using bit mask meanwhile the O(n) solution is not that difficult to realize at all...

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

    I wrote the logical, O(n) solution during contest but later found the bruteforce easier

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

    same i spent 30 min for writing dp, as i am practising dp already these days , but i was not able to write correct recurssion , can anyone give solution using dp ?

    `int f(int i, string s, int canSkip, int k) { // Base case if (i == s.length()) { return k + 2 == s.length() ? 1 : 1e9; }

    int ans = LLONG_MAX;

// Handling two-digit numbers
if (i + 1 < s.length()) {
    int no2 = stoi(s.substr(i, 2));
    ans = min(ans, no2 * f(i + 2, s, 0, k + 1));
    ans = min(ans, no2 + f(i + 2, s, 0, k + 1));
}

// Handling single-digit numbers
int no1 = s[i] - '0';
ans = min(ans, no1 * f(i + 1, s, canSkip, k + 1));
ans = min(ans, no1 + f(i + 1, s, canSkip, k + 1));

return ans;

    }

    void solved() { int n; cin >> n; string s; cin >> s; cout << f(0, s, 1, 0) << endl; }`

    This was my code please correct it ,not memorzied it but then its the easy part , can u just correct my recurssive code

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

    Yeah, even I spent $$$40$$$ min thinking of a bitmasking approach, but I kept calculating how much time it would take. When the bitmask I ran locally took $$$15600$$$ ms for $$$t=10^4, n=20$$$ for all $$$t$$$, I decided it must be a greedy approach.

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

    TRUE!!!!!!!!

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

    brute force approach o(n*n) https://codeforces.com/contest/1986/submission/267238262

    → Reply
»
4 days ago, # |
← Rev. 2   Vote: I like it -7 Vote: I do not like it

Detailed Video Editorial English

C : https://youtu.be/w7yaIcNz_1w

D : https://youtu.be/UZ-zb7NZrRU

E : https://youtu.be/dCtiB_TRfms

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

https://codeforces.com/contest/1986/submission/267100334 [My submission]

I am getting WA on 2nd test case ? Why

Edit -> Solved by another algo

→ Reply
»
4 days ago, # |
  Vote: I like it -10 Vote: I do not like it

Good round! I enjoyed it.

→ Reply
»
4 days ago, # |
← Rev. 2   Vote: I like it +65 Vote: I do not like it

Why the sooooooo tight memory limit in problem G? I didn't see any reason to reject solutions on the memory constant factor!! Or do you really have a meaningful $$$O(n)$$$ memory solution? Anyway, if an acceptable solution uses $$$1\cdot n\log n$$$ memory, why to reject $$$2\cdot n\log n$$$?

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

    +1

    → Reply
  • »
    »
    3 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I actually find the time limit is super tight. With the same core idea, it takes me dozens of iterations to make my Java solution be accepted, with lots of optimizations to reduce runtime and a special handling for the scenario of test 76. A time limit of 4 second instead of 3 would be better. The tight memory limit prevent me from using more time-efficient lookup table but is relatively less critical than time limit in my case.

    → Reply
    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Yeah also the same issue for me. my cpp submission was running between 3.0 and 3.1s (checked in gym clone Contest) and not being able to pass after experimenting a lot with using maps instead of vectors and vice versa, adding pragmas etc. At the end i managed to get AC by starting my sieve from 2, since i don't need the info that 1 divides every number and got AC in 2.9s.

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

No sample code?

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

    the algorithm is easy enough for you to implement yourself. so do it as a challenge

    PS: first time 5 ac before system tests on a div3 :))

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

Can anyone please tell me why my solution 267122161 for Problem D is giving Wrong Answer on test case 2?

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

can someone explain how to solve problem B? I was really stuck in problem B, especially thinking if the a[i][j] is a corner piece, edge piece, or neither. Thanks, really appreciate it!

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

    are we just trying to find the minimum of maximum adjacent cells of a[i][j]?

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

      We have to modify the array in such a way so that there's no element greater than either of its adjacent cells, and return the total number of such modifications we might have done to form the required array. You might not have to write different code for corner/edge/center piece, you can write code such that it wouldn't matter. I think you'd gain clarity if you see someone's submission

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

    for the corners just increase the size of the grid by at least 2 like if it's 5 5 you make it 7 7 and also start indexing from 1 not from 0

    that way you don't have to worry about i+1 or i-1

    → Reply
»
4 days ago, # |
  Vote: I like it +50 Vote: I do not like it

For problem F, I used a unique method yesterday to find the bridge edges in this graph (which seems to be an undirected graph). While some parts may be a bit technical, I want to record and share it with everyone.

First, I used a union-find data structure to find a valid spanning tree (assuming that edge weights are directly assigned to the child nodes). Then, for the remaining edges $$$(u_i, v_i)$$$ that are not in the tree, I increment the path $$$(u_i, v_i)$$$ by one, because this forms a cycle, and cycles do not have bridge edges. This can be achieved through the LCA (Lowest Common Ancestor) and tree difference methods.(maybe this name, sorry for my poor English.)

Here is the submission. 267081057

However, after careful consideration, I realized that we can use a hashing and xor approach. Each time we cover a path, we assign a random value in the range $$$[0, 2^{64})$$$. Due to the properties of xor, the values will cancel out above the LCA, which is equivalent to checking if the path has been covered. Finally, we just need to calculate the subtree sizes in the tree and update the answer accordingly. This method eliminates the need to find the LCA.

Here is the submission. 267125590

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

    Why not use Tarjan's algorithm?

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

      It can solve the problems more than find bridges.And this method is interesting.

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

    damn!!!

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

    An alternative way to avoid LCA is finding a DFS tree instead of a spanning tree, in such a way that all the extra edges go from a node to one of its ancestors.

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

    Your both solutions are very interesting. Thank you.

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

Very interesting problemset .

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

my lazy brain could only thought of the dp solution for the problem E. Am I too dumb to realise the claver and O(N) soln of author ??

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

    i use dp to tackle the case of odd numbers :))

    didn't wanna use prefix/suffix sums cause i don't wanna go that way

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

      can you explain a little bit your dp code ?

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

      Can you explain how you used DP for that? I am unsure how to use a prefix/suffix array to find which odd index to remove. Can anyone explain how to do it optimally

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

        this is my code: 267060049

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

          for clarification!! (cause most are confused by the dp)

          here i define "legal" as a legitimate way to insert elements into the array, which means that an element cant be used twice.

          dp[i][0] is the optimal cost if we chose vv1[i] dp[i][1] is the optimal cost if we chose vv2[i]

          this is to make sure all moves are legal, cause vv1 and vv2 are seperated.

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

Man, I overthinked a lot on D and at last ended up doing it with DP, i got tle because i was using n^4 * t, but just with a simple change (removing prev index and using a bool at its place, as partition can be either of size 2 or 1 I was able to Pass it)

Code here
→ Reply
  • »
    »
    4 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    what is prev ?? I feel it's the same as can skip

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

      ok I got it I think you can also convert canskip to third value to ensure that we don't take 2 NEIGHBOURING numbers twice which will make it 3 states only and also we don't need left because you can check at the end if canskip is used or not

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

        ah yes sure i can also remove canskip and just make it a 2*n dp, prev here is a bool which checks if we are making this partition as a 2 sized partition or not and as we can do that once i used canskip for that, but it's redundant as you said

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

Either codeforces has a bigger stack or I suspect weak tests for problem F. My recursive DFS got AC and locally I am able to segfault it with giving it a path on 10^5 vertices.

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

.

→ Reply
»
4 days ago, # |
  Vote: I like it -12 Vote: I do not like it

the Editorial Is not listed within the contest

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

problem c has a similar idea to this

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

Can someone explain problem G

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

C has been hacked? How?

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

Fast Editorial!

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

What is actually the "count array" in G2?

→ Reply
  • »
    »
    4 days ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    since no one replied let me try...

    for A/B, C/D...; count array keeps track of D-s of C-s which is divisible by B. here B is the fixed b_i in the editorial; A=a_i, C=a_j, D=b_j. then to calculate their contribution to the answer you go through divisors x_1, x_2, x_3... of A and sum all count[x_1]+count[x_2]+... for the final answer. because for each B; you search for C which is divisable by B such that D from C divides A.

    lets say you have 6 at index 7, 14 at index 3, 19 at index 7 and 21 at index 9(by taking gcd-s this will become 7/3). so actually you have 6/7, 14/3, 19/7 and 7/3.

    as said in the editorial you iterate through b_i-s, so actually you iterate through denominators {7,3,7,3} and let's say you are at the first 7.

    (so the input corresponding to 6/7)

    you wanna check how many other fractions exist which have a number divisible by 7 in nominator and number which divides 6 in denominator. to do that you go through all the elements whose nominator is divisable by 7 i.e. {14/3,7/3}. then for each element you mark their denominator with count array, so in this case you process count[3]++ two times so you get count[3] = 2. count[x] = 0 for every x except 3.

    as a next step (the part with "Now, for a fixed b_i" in the editorial); you go through all nominators which have 7 in denominator so through {6/7, 19/7}. for every such element go through their divisors; so for 6; you go through 1,2,3,6; and you update your answer with count[1]+count[2]+count[3]+count[6].

    check my submission which passed in 2999ms (シ_ _)シ check unordered_map <int,int> count in my code 267200592

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

    check out my latest comment below

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

In problem E, why is it advantageous to consider only the odd indices for removal if $$$m$$$ is odd?

Edit: I get it now. Choosing even indices makes the answer worse because you are now pairing up non-adjacent elements, which makes the answer larger.

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

    yeah, This was the only observation I missed during contest, literally did everything else.

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

      Same. My Idea was that it was optimal to remove either the very first element or the very last element, but by the time I realised middle elements could also be removed for an optimal answer, it was too late.

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

    Was going through the comments, was pretty sure someone might've asked the same question. Thanks for explaining it as well.

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

Why my problem B solution is still in queue☠️, Although I remember that it was accepted last night

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

    system test going on The submissions are being judged again with more test cases(all the hacks are included in the new set)

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

      So, the Solutions will now also run for the Successful Hack Test Case for all Participants? Does that mean if I got an AC now my solution was not hackable in the hacking phase?

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

        Yes. Thats the whole point for open hacking phase. If you get AC now that means no successful hack could have been used to hack your submission

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

in problem E I'm sorting the array and matching each element with the closest one but this greedy is giving wrong at test 10 my answer is 15 but the correct is 14 is this approach really wrong ???

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

    It would be better to include your submission in the comment. I guess this test case will help you explain. Assume n as 5 and k as 1 elements are 1,8,3,20,19. sort it you get 1,3,8,19,20 by your approach you will pair 1 and 3 then 8 and 19 but optimal pairing is 1 and 3 then 19 and 20. You may fix this but this method would still give tle.

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

      Yes because I have to exclude one element if the size is odd I'm trying to come with an approach to exclude that one element in O(1) instead of the O(n) am I close ?

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

        You are actually calculating it in O(n2). (Excluding every element and trying to get the number of operations). Your approach seems incorrect or very high complexity. If possible include your submission

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

          https://ideone.com/xHwj6U this is O(n^2 logn) I know but am I even on the right way like can I optimize this ? or my whole approach has to be changed ?

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

            I suggest you to read the editorial. You may try grouping elements based on ai%k (Obviously two numbers with different remainders can't be paired). If more than one group has odd number of elemnts then return -1 or proceed with your original approach for each group (here you wont have to check if the numbers can be paired or not cause it will always be possible to pair numbers in the same group) for even size groups just pair b1 and b2 b3 and b4 and so on. For one odd size group if it exists you have to find that one element which you need to exclude.

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

If anyone searching for dp solution for problem D. Here is my solution that got accepted: 

ll dp[21][21][101];
ll helper(ll i, ll cnt, string s,string a1){
    ll n=s.size();
    if(a1.size()>2){
        return 1e9;
    }
    else{
         if(cnt>n-2 || i>n){
        return 1e9;
    }
        ll y=stoi(a1);
        //debug(a1);
        if(cnt==n-2 && i==n){
        return stoi(a1);
    }
    if(dp[i][cnt][y]!=-1){
        return dp[i][cnt][y];
    }
    ll a=INF,b=INF,c=INF;
    string x="";
    if(cnt<n-2 )a=stoi(a1)+helper(i+1,cnt+1,s,x+s[i]);
    if(cnt<n-2 )b=stoi(a1)*helper(i+1,cnt+1,s,x+s[i]);
    c=helper(i+1,cnt,s,a1+s[i]);
    return dp[i][cnt][y]=min({a,b,c});
    }
}
void solve()
{
    ll n;
    cin>>n;
    string s;
    cin>>s;
    string a="";
    a+=s[0];
    memset(dp,-1,sizeof(dp));
    //<vector<vector<ll>>>v(n+1,vector<vector<ll>>(n,vector<ll>()))
    //debug(help("2+3+3+11"));
    //map1[a]=1;
    ll ans=helper(1,0,s,a);
    //debug(map1);
    print(ans);
}
→ Reply
  • »
    »
    4 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you brief about your DP solution? what are the params of the recursive function and the recursive function?

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

      dp[i][j][k] represent minimum value till the ith index and operation used is j and the integer value of previous string is k . Actually since we have to do exactly (n-2) operation, the previous string's size can go to max 2 and that we can store by assigning maximum value of k =100.

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

I think in Problem-D solution the case where a "0"(zero) exists the answer must be zero, is missing a case where n==3 because you will see p0q, which will not lead to zero, it will lead to min(p*10+q,p+q,p*10*q). Else everything is fine

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

For Problem D : Simple DP solution in O(N)

Hint 1
Hint 2
Code for Reference
→ Reply
  • »
    »
    4 days ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    Can you please review this code and help me debug.

    CODE

    Update : Final AC code:)

    Spoiler
    → Reply
  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    do you have dp for E

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

    u doing dp[i-1]* val

    but if if u have ( a1 + a2 + a3 * a4 )

    a4 will be multiplied by a3 only , but in ur code u r checking multiplied by the prefix

    how this leads to the correct answer ?

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

      i think i got, bcz we only do the multiplication if a[i] == 1

      so only this case will be covered and this is what we want

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

Why did i get a run time error for C? 267036690

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

The cheating is going out of hand,I refuse to believe that more than 6k did D.

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

    but considering that only 25% of people got A also got D, i'd say it's pretty reasonable (and also, this is div3, second easiest division)

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

      I'll say around 500-800 people cheated there way to D.It's kinda disheartening,my positive delta keeps shrinking even with similar ranks, and negative delta keeps on increasing. In the last div2,I did first 2 in 17mins,got a rank of 5700, and a delta of -5,even when my rating was just 1203, we are now expecting pupils to do div2 C too now,to just remain a pupil?

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

        im afraid so :). even when i do C on a div2 (as a pupil), the rating bump is almost nonexistent.

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

Man dropped editorial as soon as the contest ends. Nice work.

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

F was amazing! Please add more graph problems in Div3

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

Can the F one be done using DSU?

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

why did i get runtime error for problem d? Please help me out 267184148

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

74TrAkToR There is a mistake in the Problem-D editorial.

You mentioned If there is at least one 0 , the answer is 0 . We can simply place all signs as ×.

This is not true even for a given test casen=3 and s='901' whose answer will be a 9 and not a zero.

→ Reply
  • »
    »
    4 days ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    yes if number of operations are 1 or n=3 then the answer would be zero only if the 0 is at the ends of number.

    → Reply
  • »
    »
    4 days ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    If all numbers are 1, the answer is 1. We can simply place all signs as ×.
    This is incorrect as well. Simple test case would be s = "111" and the answer should be 1 * 11 = 11

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

    First, let's iterate through the position $$$i$$$ , such that we do not place a mathematical sign between the $$$i$$$ -th and $$$(i+1)$$$ -th elements.

    Next, we have the following task — we have $$$n−1$$$ numbers and we need to place a + or × sign between each pair of neighboring numbers to minimize the result.

    You did this process after you had $$$n-1$$$ numbers.

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

I think in D if all numbers are 1 then answer should be 11 not 1 because we will need to concatenate two numbers.

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

    If all numbers after the concatenation are 1, then the answer will be 1. We can't consider this before the concatenation.

    → Reply
»
4 days ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

why such tight memory constraints on G? why cannt they give more memory???? I got G1 accepted, and G2 was MLE on 43rd testcase... sad life...

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

Problem 1986D - Mathematical Problem solution:

Key observation: As we can use only n-2 sign (+, x), so there must be at least one two-digit number. Then just find the minimum answer as asked.

-Time Complexity O(n ^ 2) 

        int n; 
	string s;
	cin >> n >> s;
	int ans = INT_MAX;
	for(int i = 1; i<n; i++){
		int num = stoi(s.substr(i-1, 2)); 
		for(int j = 0; j<n; j++){
			if(j==i-1 || j==i) continue;
			int cur = s[j]-'0';
			num = min(num*cur, num + cur);
		}
		ans = min(ans, num);
	}
	cout << ans << '\n';
→ Reply
  • »
    »
    4 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Solution is the same, just brute force without heuristics.

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

      I didn't able to guess it at the contest time! Sad Life!

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

    I don't think the reasoning is correct, although the algorithm will yield correct outputs accidentally.

    1. The algorithm reorders the numbers, it can never search the possibility of 1 + 2 * 34, since 34 goes first.
    2. The algorithm does not respect the order of operations, it can only search (12 + 3) * 4 but not 12 + 3 * 4.

    However, the algorithm yields correct outputs since it follows the correct reasoning by accident.

    1. If there are 0, num will be 0.
    2. If there are 1, num will be unchanged.
    3. Otherwise, num += cur.
    → Reply
    • »
      »
      »
      4 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In case of minimization, it's always correct. Because the intuition behind is that You never want to multiply number that gives greater result than just adding those two numbers. And that's what asked in the problem statement.

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

can tell me anyone what is wrong in my code 267195219 // i have basically find every 2 digit pair and min number towards left and towrards right and then left — central — right 4 cases * * + * * + + + it is frustrating

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

Why this contest is showing in unrated?

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

Can anyone tell me what's wrong with my solution for problem D? 267205625 It's a simple brute force solution but I still got WA on test case 2.

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

Clean and fast Editorial

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

Can someone explain for F. How to Find if a edge is a bridge or not.

→ Reply
»
4 days ago, # |
← Rev. 8   Vote: I like it 0 Vote: I do not like it

Can anyone please review my Dp soln and tell what is wrong here, either any logical error or overflow. The output seems like it is an overflow, if it is then how should i avoid it?

CODE

Update-1: The Base case was wrong and in if(taken){} there should be "true" in further recursive calls. Base case: 

 if(i == 1 && taken == false){
        return stoll(s.substr(i - 1, 2));
    }
    if(i == 0) return (s[0] - '0');

This helped in avoiding overflow and correct output on many test cases but for few test case the answer was wrong.

Update-2: Final Accepted code :)

Code
→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me whats wrong with my prefix and suffix handling in problem in case of odd length 267095361

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

Can someone explain me F better? I can find the bridges, but can't go any further. Run a single dfs in each bridge will get TLE. I didnt get the size of subtree part.

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

    Ok, I managed to understand that. If I have an edge (u,v) that is a bridge, then when I pass from u to v in the dfs, I cannot go back to u anymore, so the number of nodes visited after v is the number of vertices in the other component after a disconnection.

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

    Lets say you found the bridges between i and j. But we also need to find the sizes of the components i and j which we can be done efficiently by maintaining a subtree size where every subtree size of a node can be calculated during the dfs traversal. This way we dont need to calculate subtree size individually for each bridge.

    After that the size of component i will be subtree[i] and j will be n-subtree[i] or subtree[j]. Now we just need to minimize the ans which is (subtree[i]*(subtree[i]-1))/2 + (subtree[j]*(subtree[j]-1))/2.

    My submission : 267232116

    → Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E any one can help on how to approach the idea of excluding one element using DP

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Changing map to a sorted vector of elements + binary search works in G2, the time complexity is the same but i can't figure out why it removes the MLE i get with map, since intuitively, i am storing count in map and elements in vector, the storage in map is more sparse, is this happening because in testcase 43 the array values are such that, it leads to lower count values in map and thus, reducing the advantage of sparseness?

Map submission

Vector submission

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

why show node for us? still have questions

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone pls provide cpp code for E problem , doing the same thing but got tle

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

    you can filter search the submissions section

    → Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

/* https://codeforces.com/contest/1986/submission/267290277

can anyone help me ?I am getting TLE in test case 27. Thanks in advance/* ~~~~~

include <bits/stdc++.h>

using namespace std;

define pi (3.141592653589)

define mod 1000000007

define ll long long int

define all(c) c.begin(), c.end()

define min3(a, b, c) min(c, min(a, b))

define rfl(i, a, n) for (int i = n — 1; i >= a; i--)

define fl(i, a, n) for (ll i = a; i < n; i++)

define ct(x) cout << x << endl

define rd(a, n) fl(i, 0, n) cin >> a[i]

define wrt(a, n) fl(i, 0, n) cout << a[i] <<

define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

// char Array to int Using atoi() like string s // C++ string to int Using stoi() like char str[50]

int main() { fast int t = 1; cin >> t; while (t--) {

ll i,
    j, k, n;
cin >> n >> k;
ll arr[n+5];
rd(arr, n);
unordered_map<ll, vector<ll>> mp;
sort(arr, arr + n);

fl(i, 0, n) mp[arr[i] % k].push_back(arr[i]);

ll ans = 0;
ll odd = n % 2;

ll oc = 0;
for (auto it : mp)
    if (it.second.size() % 2)
        oc++;

if (n % 2 < oc)
{
    cout << -1 << endl;

continue; } for (auto &it : mp) { int sz = it.second.size(); if (sz % 2 == 1) {

ll s = 0;

            vector<ll> pref(it.second.size() + 5, 0);
            for (int i = 0; i < it.second.size(); i++)
            {
                if (i % 2)
                    s += (it.second[i] - it.second[i - 1]) / k;
                pref[i] = s;
            }
            // cout<<endl;

            s = 0;
            ll temp = 1e18;
            for (int i = sz - 1; i >= 0; i--)
            {
                if ((i % 2))
                {
                    s += (it.second[i + 1] - it.second[i]) / k;

                    // pref[i]=s;
                }
                else
                {

                    temp = min(temp, pref[i] + s);
                }
            }

            ans += temp;
        }


    else
    {

        for (int i = 1; i < sz; i += 2)
        {
            ans += abs(it.second[i] - it.second[i - 1]) / k;
        }
    }
}

cout << ans << endl;
}
return 0;

} ~~~~~

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

    maybe the unordered map. it's been mentioned before that unordered_map can run in O(1), but in worst case O(n^2). this can be used in hacks.

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

      my solution got AC with the same algorithm, and i used map.

      → Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone tell the problem with my code on D 267075434 it was wrong on test case 4 https://codeforces.com/contest/1986/submission/267075434

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

    i'm not too sure, but it seems like tha algorithm is wrong

    using your algorithm (sorry if i'm wrong, that'd be embarrsaing) and the test 1117

    the smallest 2 digit number is 11 the optimal cost if u use 11 is 11 x 1 + 7 = 18

    but the optimal cost is 1 x 1 x 17 = 17

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

      upd: just realized i'm wrong here.

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

      nope it will take 17 as optimal number and cost 17. try another test case it might give wrong it is wrong for 500 something number in test case 4

      → Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

my submission for B. works on my computer but not here :267313352 Help.

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

Would like to add some of my thoughts on G to the discussion, this might be a more intuitive approach.

The first step is still to simplify $$$\frac{p_i}{i}$$$ to $$$\frac{a_i}{b_i}$$$. Now we can write out the following brute force pseudocode:

$$$\texttt{for } a_i:$$$

$$$\quad\texttt{for } b_j | a_i:$$$

$$$\quad\quad\texttt{for } a_j:$$$

$$$\quad\quad\quad\texttt{for } b_i | a_j:$$$

$$$\quad\quad\quad\quad\texttt{res += } f(a_i,b_i)f(a_j,b_j)$$$

Where $$$f(a,b)$$$ counts the number of datapoints with simplist form $$$\frac{a}{b}$$$. This is sparse with at most n entries, so we can use something like $$$\texttt{std::vector<std::map<int, int> >}$$$ to represent it.

Now we can reduce the number of loops by precalculating a "factor prefix sum" on the table $$$f$$$. The idea is very similar to prefix sum. Let's denote $$$g(a,b) = \Sigma_{b'|b}f(a,b')$$$. Then

$$$\texttt{for } a_i:$$$

$$$\quad\texttt{for } a_j:$$$

$$$\quad\quad\texttt{res += } g(a_i,a_j)g(a_j,a_i)$$$

An elegant form! Unfortunately it doesn't work. Aside from the double loop, we now have a dense table $$$g$$$ (just consider the edge case that $$$f(a,1) = 1$$$ for any $$$a$$$, then $$$g$$$ would have positive value for every $$$(a,b)$$$ pair). So even building the table would take $$$O(n^2)$$$ space and time.

The trick is to change the subscript that we perform the sum operation. Let's first rearrange our original brute force algorithm:

$$$\texttt{for } b_j:$$$

$$$\quad\texttt{for } b_j | a_i:$$$

$$$\quad\quad\texttt{for } b_i:$$$

$$$\quad\quad\quad\texttt{for } b_i | a_j:$$$

$$$\quad\quad\quad\quad\texttt{res += } f(a_i,b_i)f(a_j,b_j)$$$

So we first loop over each $$$b_j$$$, then all multiples of $$$b_j$$$, then each $$$b_i$$$, then all multiples of $$$b_i$$$.

Similar to $$$g$$$, define the prefix sum table $$$h(a,b) = \Sigma_{a|a'}f(a',b)$$$. Then we have

$$$\texttt{for } b_j:$$$

$$$\quad \texttt{for } b_i:$$$

$$$\quad\quad \texttt{res += } h(b_j,b_i)h(b_i,b_j)$$$

The difference between $$$h$$$ and $$$g$$$ is that $$$h$$$ is sparse: we can see that each $$$(a,b)$$$ adds its $$$f$$$ value to exactly $$$\sigma_0(a)$$$ points (the number of divisors of $$$a$$$), so in total the space complexity is $$$O(nlogn)$$$.

Finally because the table is sparse, we can optimize the double loop as well, by just looping over the keys with positive value:

$$$\texttt{for } b_j:$$$

$$$\quad \texttt{for } b_i \texttt{ in } [b_i | h(b_j,b_i) > 0]:$$$

$$$\quad\quad \texttt{res += } h(b_j,b_i)h(b_i,b_j)$$$

If we are use map here, the time complexity would be $$$O(nlog^2n)$$$. This solution should be good enough to pass G1. implementation

However, the $$$O(nlogn)$$$ time is not good enough to pass G2 (or maybe it is, just that map has a big constant, but let's just push for the best solution). How do we optimize this? A natural thing to do for those 2D tables is to optimize away one of the dimensions, usually the row dimension. However, currently our algorithm uses values from both $$$b_i$$$ and $$$b_j$$$ row, so for one of the rows, we need to sacrifice some extra time to calculate the prefix sum from the raw $$$f$$$ table directly. Since we are looping in $$$b_j$$$ first, let's replace $$$h(b_i,b_j)$$$ with its definition (based on $$$f$$$):

$$$\texttt{for } b_j:$$$

$$$\quad \texttt{for } b_i:$$$

$$$\quad\quad \texttt{for } b_i | a_j:$$$

$$$\quad\quad\quad \texttt{res += } h(b_j,b_i)f(a_j,b_j)$$$

Now $$$h(b_i,b_j)$$$ only uses information from the current row, $$$b_j$$$. To illustrate this, let's change its notation to $$$h_{b_i}(b_j)$$$ (this is in fact the "count array" the official editorial is referring to), so it becomes a 1D table.

Change the order of loop:

$$$\texttt{for } b_i:$$$

$$$\quad \texttt{for } b_i | a_j:$$$

$$$\quad\quad \texttt{for } b_j:$$$

$$$\quad\quad\quad \texttt{res += } h_{b_i}(b_j)f(a_j,b_j)$$$

This order change allows us to utilize the sparsity of table $$$f$$$:

$$$\texttt{for } b_i:$$$

$$$\quad \texttt{for } b_i | a_j:$$$

$$$\quad\quad \texttt{for } b_j \texttt{ in } [b_j|f(a_j,b_j)=1]:$$$

$$$\quad\quad\quad \texttt{res += } h_{b_i}(b_j)$$$

This algorithm should pass G2. implementation The time complexity is $$$O(200n + nlogn)$$$, where $$$200$$$ is the max number of divisors for numbers <= 5e5. Space complexity is $$$O(n)$$$.

Note that in the implementation you also need to take care of some duplicate cases.

Hopefully this helps those who are strugglign with this problem.

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

https://codeforces.com/contest/1986/submission/267420939

G2 Question can anyone help me, how to get rid of TLE.

→ Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Sorry for asking. Why doesn't my code work on problem E? Here's the submission.

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

    I think the issue is with the odd number of elements (where the middle element is matched with itself). In this case, you cannot place any element in the middle, you need to choose one optimally.

    5 3
10 28 4 1 22

    For the above testcase, it is optimal to place to place 10 as the middle element but your code uses 28 as the middle element.

    → Reply