atcoder_official's blog

AtCoder Beginner Contest 412 Announcement
By atcoder_official, history, 15 months ago, In English

We will hold AtCoder Beginner Contest 412.

We are looking forward to your participation!

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

Comments Comments (36)
| Write comment?
»
15 months ago, hide # |
 
Vote: I like it -13 Vote: I do not like it

Why did the Rated Range is 0-2799 some days ago but 0-1999 now?

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

Why is the color above bule ?

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

Why is the colour above blue? (I don't like blue,so do anybody know how to switch it back?)

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

F is a very good expectation question.

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

D is a trash idea

→ Reply
»
15 months ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

Segmented sieve is new for me. Pretty cool approach!!

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

Someone please help me with question C :( I tried greedy with binary search, it didn't pass 12/32 cases.

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

    why binary search, I just iterated until the next element doesn't fall, keeping idx pointer. But for the edge case with n=2, I wrote 0 instead 2, that was my WA, lost 30 minutes

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

      yea but it shouldn't matter right?? Could you check my solution with some test case??

      int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vi arr(n);
        map<int, vector<int>> index;
        loop(i,0,n) {
            cin >> arr[i];
        }      
        vi newarr = arr;
        sort(newarr.begin(), newarr.end());
        loop(i,0,n) index[newarr[i]].pb(i);
        int valid = 1;
        int i = index[arr[n-1]][0];
        int count = 1;
        //loop(i,0,n) cout << newarr[i] << " ";
        int y = index[arr[0]].size();
        while(i > index[arr[0]][y-1]){
            count++;
            int x = newarr[i];
            auto idx = lower_bound(newarr.begin(), newarr.end(), (x+1) / 2);
            //cout << idx - newarr.begin() << " ";
            if(idx == (newarr.begin() + i)){
                valid = 0;
                break;
            }
            else{
                i = idx - newarr.begin();
            }
        }
        if(!valid)  {
            print(-1);
            continue;
        }
        else    print(count);
      → Reply
  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    You could check THIS out. Might not be a very well written code, but good enough.

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

I am pretty sure that problem D or something very similar has already occur somewhere with much stricter constraints.

I solved it today with MCMF on a graph: s -> v of capacity 2 cost 0, (v + n) -> t capacity 2 cost 0, and u -> (v + n) capacity 1 cost (1 if there were no such edge initially and -1 otherwise). Answer == (m * 2 + mincost) / 2.

However, this approach is kinda hard to prove, because it is not necessary that if edge (u -> (v + n)) is taken to the flow, then (v -> (u + n)) is also taken. If the graph is directed, then there is no issue, problem solved. However, it also works for undirected(i mean that the answer is correct, not that the flow is built in a way that all edges are taken in pairs). But i cannot prove it. Can anyone?

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

    What an overkill)

    I solve it following way. Degree of all vertices is two, hence the graph is set of cycles. There is a bijection between such graphs and permutations (edges are $$$(i, a[i]) \; \forall i \in [1, n]$$$). Iterate on permutations. We need to just check, that there is no loop $$$i = a[i]$$$ and no multiedge $$$i = a[a[i]]$$$.

    Let $$$X$$$ be the number of edges in permutation, that are given, and $$$Y$$$ be the number of edges in permutation, that are not given. Then the possible answer is $$$(m - X) + Y$$$.

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

In problem F editorial I can't understand anything. Can someone, please, explain it more adequately?

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

    Let $$$p_x$$$ = expecting number of sock draws if now we have sock of such a color that occurs exactly $$$x$$$ times among all socks. Since $$$x \leq 3001$$$, one of the solutions is to construct SLE on these variables and solve it.

    The answer is $$$p_{t}$$$ where t = number of socks of color C among all socks.

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

    Consider using "total number of socks have same color as the one on your hand" (include the one on your hand), then you would switch to another sock you draw only when that one have more number in total, so "total number of ..." would be non-decreasing in the whole process, and you can find the probability to transit from $$$u$$$ to $$$v$$$ for every $$$u \le v$$$, then let $$$E[u]$$$ be the expected number of times we need to draw to have a pair when start with a sock have $$$u$$$ in total. Then we have $$$E[u] = 1 + \sum\limits_{v \gt u} Pr[u \rightarrow v] E[v] + Pr[u \rightarrow u]E[u]$$$ so $$$E[u] = \frac{1 + \sum\limits_{v \gt u}Pr[u \rightarrow v] E[v]}{1 - Pr[u \rightarrow u]}$$$, then just dp in decreasing order of $$$u$$$.

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

D in $$$ O(n!.n log(n)) $$$ Link

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

I think E is very hard.I noticed that the prime solving,but I got a TLE...........Because my algorithm for factoring prime factors is not good.......

But I think D is an easy problem , It just use a DP

C is a problem to practice thinking,I got the solution in 18min。I use a Binary search and greedy to solve it.

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

i am getting WA in C submission any testcase where it will fail

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

I think I can say that, here we go again, for today's problem F.

:D https://codeforces.me/blog/entry/142558#comment-1272566

It seems that ABC really likes this kind of dp, which asks to find out max or min of some expectation.

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

In F, if two drawers have the same no. Of socks, the expectation should be the same, right??

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
constexpr int mod = 998244353;

int binpow(int a, int b, int m)
{
	int res = 1;
	a = a % m;
	while (b != 0)
	{
		if (b & 1)
		{
			res = (res * a) % m;
		}
		a = (a * a) % m;
		b = b >> 1;
	}
	return res;
}

void solve()
{
	int n, c;
	cin >> n >> c;

	vector<int> a(n);

	int sum = 0;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		sum += a[i];
	}
	sum++;
	sum = sum % mod;
	c--;
	a[c]++;


	sort(a.begin(), a.end());

	int pp = 1e18;
	int sum1 = 0, kk = 0;
	map<int,int> dp;
	int z = (sum - 1 + mod) % mod;
	for (int i = n - 1; i >= 0; i--)
	{
		sum1 += a[i];
		int y = (sum - sum1) % mod;
		//cout << y << " " << a[i] << " " << z << endl;
		int mm = (y * binpow(z, mod - 2, mod)) % mod;
		mm = (1 - mm + mod) % mod;
		//cout << kk << endl;
		mm = binpow(mm, mod - 2, mod);
		//cout<<((1 + kk) * mm) % mod<<endl;
		dp[a[i]] = ((1 + kk) * mm) % mod;
		int oo = (a[i]) % mod;
		oo = (oo * binpow(z, mod - 2, mod)) % mod;
		kk = (kk + (dp[a[i]] * oo) % mod) % mod;
	}

	cout << dp[a[c]] << endl;

	return;
}

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	// cin >> t;

	while (t-- != 0)
	{
		solve();
	}
	return 0;
}

also if someone can tell me what's wrong in this edit: got it I think I need to sleep

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

Can somebody explain me the problem E please i tried to follow the editorial but that didn't helped me . Somebody please explain in simpler terms Thankyou

→ Reply