Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

atcoder_official's blog

AtCoder Beginner Contest 314 Announcement
By atcoder_official, history, 11 months ago, In English

We will hold AtCoder Beginner Contest 314.

The point values will be 100-200-300-400-475-475-575-625.

We are looking forward to your participation!

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

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

Can anyone tell me what is "Clar" in "About the New Judge"? I hardly found posts about it in Bing.

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

AtCoder Beginner Contest Pi!

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

I don't know if I can do D this time ):

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

Wow! New judge!

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

...........................

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

    just v* the st*i*g and rea* to pr*n* the ns*e

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

omg , my java codes are working in 40ms , but why did you removed java 8 , it's the best version of the best language on this earth

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

Good contest I was pretty scared that they mentioned it will be harder than usual but I didn't felt this contest is way too different compared to typical atcoder rounds

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

    Nobody has mentioned that before(?) This round is just an ordinary one because I can exactly solve problem G as usual.

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

      I'm sorry my bad I've saw the old blog it got updated just before 15 hours I saw it before that. If I would've known that before contest I would've made it rated ;_;

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

    It is the previous contest (ABC313) that is harder than normal ABC-class contests.

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

yes

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

too funny :) I submitted 4 wrong codes on D, such a easy problem.

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

Whyyyyyyyyy both E and F are expected value based question. Guess its time to practice expected value :(

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

    Yeah same, I tend to quit if the problem is about expected value of something

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

    How delighted I was when I solved D, how frustrated I was when I saw E

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

    $$$F$$$'s expected value was just sum of probabilities for each node. But the main work (in my solution) was how to create a DSU variant to build a tree which can be used the propagate (add) the final answer for each node.

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

      That part was easy just small to large merging was needed to be done. I couldn't debug my code again on time :pain:

      My code

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

Pretty shocked to see that people are discussing ongoing contest in the comment box , some even telling solutions

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

how to solve E?

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

orz chromate00 for the first solve of Ex...

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

How to Solve D?

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

    The problem is solved by considering global operations separately and checking the last update when modifying individual characters.

    Regarding global operations, it is sufficient to record the time and type of the last operation.

    Finally, if the individual update is made after the global update, it is printed directly; otherwise, the last global update is applied to the individual update before printing.

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

    among the operations of type 2 and 3 only the last operation matters

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

Using simulated annealing and passed task Ex, maybe the data is too weak?

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

    no lol the problem is simply convex, that is why

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

Weak tests in D.
https://atcoder.jp/contests/abc314/submissions/44532834 should fail on 7 Atcoder 3 2 0 a 1 3 a 1 3 B

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

This is a tragedy! link

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

Can anyone talk more about problem E? I can hardly understand the editorial. Thank you so much.

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

    I'm not sure if it would help but I'm writing my way of thought anyways. Keep in mind that it is not really formal, I suggest your refer to the editorial for more formality.

    Let $$$E_i$$$ be the expected number of money needed to get $$$i$$$ points when Takahashi adopts the optimal strategy.

    At first Takahashi has $$$0$$$ points. So there are $$$M$$$ points he needs (at least), so the expected number of money needed is $$$E_M$$$. What's left is to compute $$$E$$$.

    Say Takahashi has $$$0$$$ points (i.e needs $$$M$$$ points). At that point and based on his strategy he will choose some $$$k\in\{1, \dots , N\}$$$ and spin the $$$k$$$-th wheel. Doing that, he will pay $$$C_k$$$ (for sure) and will gain $$$S_{k_j}$$$ points ($$$1\leq j\leq P_k$$$) with probability $$$\frac{1}{P_k}$$$. Then he would have $$$S_{k_j}$$$ points, so he will need $$$M - S_{k_j}$$$ more points. That implies that he will then need an average of $$$E_{M - S_{k_j}}$$$ money. So the expected number of money when having $$$0$$$ points ($$$M$$$ points remaining) is

    $$$\displaystyle E_M = C_k + \sum_{j=1}^{P_k} \frac{1}{P_k} E_{M - S_{k_j}}\quad (1)$$$

    (keep in mind that $$$E_i = 0$$$ for $$$i \leq 0$$$, but you can just have $$$E_0=0$$$ and always take the index $$$i$$$ as $$$\max\{0, i\}$$$)

    $$$ $$$
    What about zero elements?
    $$$ $$$
    How replacing the costs makes for an easier solution.
    $$$ $$$
    But how can we know k?

    Similarly to $$$E_M$$$ we can compute all of $$$E$$$. This yields a $$$O(MNP)$$$ solution ($$$P=\max_i P_i$$$), which is basically the editorial's solution looking at it slightly differently. I think understanding one solution will make one easily understand the other.

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

      (The problem is resolved, so kindly ignore this message.)

      Hello judgme_nt,

      I used the exact approach suggested by you. But my code is giving WA on just 1 test case. I can't find the error in my code. I coded a recursive solution and can't find anyone with a similar code. Can you please point out the mistake in my code?

      Submission

      Here, I have used a "cnt" array to store the number of zero elements in i-th wheel. (The code is written clearly enough, so understanding it would not be tough).

      Thank You

      UPD: It got accepted when I changed double to long double.

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

      It is much easier to understand than Editorial.

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

Hi, could someone please take a look at my solution for problem E and point out problems with the approach? I have added comments on the DP state and transition. Would really appreciate your help. The code snippet is not long.

Code Snippet
→ Reply
»
11 months ago, # |
  Vote: I like it -18 Vote: I do not like it

Can you give me a data that makes my code in question D wrong? Thanks!

#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
inline void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
int n;
string s;
int q;
int ALL_UP=0,ALL_LO=0;
map<int,pair<int,int>>a;
signed main(){
    n=read();
    cin>>s;
    s=' '+s;
    q=read();
    for(int i=1;i<=n;i++){
        if(s[i]>='a'&&s[i]<='z')a[i]={0,-1};
        else a[i]={1,-1};
    }
    for(int i=1;i<=q;i++){
        int t=read();
//        cout<<t<<endl;
        if(t==1){
            int x=read();
            char c;
            cin>>c;
            s[x]=c;
            if(c>='a'&&c<='z')a[x]={0,i};
            else a[x]={1,i};
        }else if(t==2){
            read();
            char c;
            cin>>c;
            ALL_LO=i;
        }else{
            read();
            char c;
            cin>>c;
            ALL_UP=i;
        }
    }
    int UPORLO,t;
    if(ALL_UP>ALL_LO)UPORLO=1;
    else UPORLO=0;
    t=max(ALL_LO,ALL_UP);
//    cout<<UPORLO<<' '<<t<<' '<<s<<endl;
//    for(int i=1;i<=n;i++){
//        cout<<a[i].first<<' '<<a[i].second<<endl;
//    }
    for(int i=1;i<=n;i++){
        if(UPORLO){
            if(UPORLO==a[i].first){
                if(s[i]>='a'&&s[i]<='z')cout<<(char)toupper(s[i]);
                else cout<<s[i];
            }else{
                if(a[i].second>t)cout<<s[i];
                else{
                    if(s[i]>='a'&&s[i]<='z')cout<<(char)toupper(s[i]);
                    else cout<<s[i];
                }
            }
        }else{
            if(UPORLO==a[i].first){
                if(s[i]>='A'&&s[i]<='Z')cout<<(char)tolower(s[i]);
                else cout<<s[i];
            }else{
                if(a[i].second>t)cout<<s[i];
                else{
                    if(s[i]>='A'&&s[i]<='Z')cout<<(char)tolower(s[i]);
                    else cout<<s[i];
                }
            }
        }
    }
    
    return 0;
}
→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

New judge seems much faster?

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

/* It can be proved that the sought expected value is always rational. Also, the constraints of this problem guarantee that if the sought expected value is expressed as an irreducible fraction x y ​ , then x is not divisible by 998244353.

Now, there is a unique integer z between 0 and 998244352, inclusive, such that xz≡y(mod998244353). Report this z. */

can anyone show me the code to achieve that within timelimit?

→ Reply