Diksha_goyal's blog

By Diksha_goyal, history, 5 weeks ago, In English

Given an array A of size n i.e., A = {A_1, A_2, ... A_n}

you are given K. you can choose any K integers (not necessarily from the given array)
i.e, X_1, X_2, X_3 .... X_K
Now, we define a function F for each A_i, such that F_i = min(abs(A_i - X_j)) where 1<= j <=K.

find the min value of max (F1, F2, F3 ..... F_n).

for example,
for 

n = 3, k = 1
A = [1,7, 12]

output is 6



for n = 6, k = 3
A = [9, 63, 22, 2, 15, 58]

output is 4

constraints:

1 <= n <= 10^5
1<= K <= n

Read more »

 
 
 
 
  • Vote: I like it
  • -17
  • Vote: I do not like it

By Diksha_goyal, history, 5 weeks ago, In English

Given an array A of size n i.e., A = {A_1, A_2, ... A_n}

you are given K. you can choose any K integers (not necessarily from the given array)
i.e, X_1, X_2, X_3 .... X_K
Now, we define a function F for each A_i, such that F_i = min(abs(A_i - X_j)) where 1<= j <=K.

find the minimum value of F_1 + F_2 + .... F_n.

constraints:

1 <= n <= 10^5
1<= K <= n

Read more »

 
 
 
 
  • Vote: I like it
  • +18
  • Vote: I do not like it

By Diksha_goyal, history, 5 weeks ago, In English

Today in a coding interview my friend was asked to find the largest palindrome which is pretty straightforward. but the next version of the problem is what I can't think of. It was asked about finding the largest paloindromic square matrix. for the matrix of size N x M.


example a a b e a a c e d e f e the answer is 2 for: a b c d e f g h i the answer is 1.

the constraints are

1 <= N, M <=50

If you have an approach... Please come up with a code implementation.

Read more »

 
 
 
 
  • Vote: I like it
  • -14
  • Vote: I do not like it

By Diksha_goyal, history, 7 weeks ago, In English

In the problem; https://codeforces.com/contest/1586/problem/B m < n; how to solve the same problem if there is no restriction on m only just 3 <= m, n <= 2*10^5 and print -1 if such a tree is not possible

Read more »

 
 
 
 
  • Vote: I like it
  • +9
  • Vote: I do not like it

By Diksha_goyal, history, 2 months ago, In English

I tried the problem https://codeforces.com/contest/763/problem/A on codeforces and was able to solve it using the idea given in the tutorial. But what actually attracted my attention in this submission 131241329 Because of all the submissions for this problem, it was different and looks the most delicate one please someone explains to me this solution, the motive behind the approach, and how she is able to think like that. Thanks.

Edits: I got how this algorithm, works, but I'm not able to think like that

Read more »

 
 
 
 
  • Vote: I like it
  • -16
  • Vote: I do not like it

By Diksha_goyal, history, 2 months ago, In English

I'm having a hard time understanding the editorial: https://atcoder.jp/contests/abc221/editorial/2732

for the problem: https://atcoder.jp/contests/abc221/tasks/abc221_e

I want to know how fen-wick tree is actually working in this problem. specially this block

for(int i=0; i<N; i++){
        ans += bit.sum(A[i])*modpow(2,i);
        ans %= mod;
        bit.add(A[i],modpow(div,i+1));
    }

I'm actually very new to CP and have no peers to seek help. So, I directly ask my problem through the blogs. please help me if you have an explanation to get me through it. Thanking you.

Read more »

 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it

By Diksha_goyal, history, 3 months ago, In English

I'm very much confused, why my memoized solution 129162014 for the problem https://codeforces.com/contest/38/problem/E

#include <bits/stdc++.h>
using namespace std;
 
 
 
int  main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n; cin>>n;
    long long inf = 1e18 + 5;
    auto fun = [&](auto self, vector<pair<int, long long>> v, int n, int pos, int pinned_pos, vector<vector<long long>> dp, long long inf)->long long
    {
        if (pos > n - 1){
            return 0LL;
        }
        if (dp[pos][pinned_pos] != inf){
            return dp[pos][pinned_pos];
        }
 
        long long Selected = v[pos].second + self(self, v, n, pos + 1, pos, dp, inf);
        long long Not_selected = abs(v[pos].first - v[pinned_pos].first) + self(self, v, n, pos + 1, pinned_pos, dp, inf);
        return dp[pos][pinned_pos] = min(Not_selected, Selected);
    };
 
    vector<pair<int, long long> > marbles(n);
    for(int i = 0; i<n; i++){
        cin>>marbles[i].first>>marbles[i].second;
    }
    sort(marbles.begin(), marbles.end());
    vector<vector<long long> > dp(n+1, vector<long long>(n+1, inf));
    long long ans = fun(fun, marbles, n, 1, 0, dp, inf) + marbles[0].second;
    cout<<ans<<'\n';
    return 0;
}

is not working in limited time, I think, its time complexity is reasonably correct for the given constraints... can someone suggest to me, where I'm going wrong and how can you please modify my code so that It can work for the given problem. I'm sorry, for causing trouble, But I'm new to puzzle-solving and I have only you guys when I am stuck in some problem. So, please help me, guys.

Read more »

 
 
 
 
  • Vote: I like it
  • -5
  • Vote: I do not like it

By Diksha_goyal, history, 3 months ago, In English

I tried to solve ARC125 problem B: https://atcoder.jp/contests/arc125/tasks/arc125_b but I couldn't solve it. I saw the editorial, who said some pretty insignificant things that I agreed with, and then I saw some submissions. in which everyone iterate from 1 to sqrt(N) and use some formula like ans+=(N-i*i)/2*i+1; I was perplexed as to how they arrived at this formula; others had arrived at a different formula. Could you please explain how to solve this problem and obtain these formulae? I need a good tutorial for this problem, explaining me every single thing so, in the future I can solve similar problems or at least understand editorials.

Read more »

 
 
 
 
  • Vote: I like it
  • -10
  • Vote: I do not like it