Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

atcoder_official's blog

AtCoder Beginner Contest 475 Announcement
By atcoder_official, history, 2 months ago, In English

We will hold AtCoder Beginner Contest 475.

We are looking forward to your participation!

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

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

gl&hf

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

Hope I can solve 4 problems and get >=800 perf

UPD: I solved 3 problems, and got 1139 perf

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

I hope I can solve 6 problems at least and get 2000+ perf,please

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

I hope to answer 5 questions A, B, C, D, and E

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

NOW, MY RANKING IS 915TH!!!

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

I solved A, B, D in 40 mins

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

I solved A,B,C,D!!!!I solved D for the first time!!!!

Good luck to everyone!

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

    D is very easy, isn't it?

    I have no word but

    这次 ABC，简称：AB 大水题，CE 大模拟，D 板子题，被大模拟弄死了

    ...
    → Reply
»
2 months ago, hide # |
 
Vote: I like it -10 Vote: I do not like it

I cannot laugh again because I just only solve ABCD

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

Nice contest but I couldn't solve G on time.

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

I'll post EFG here.

E

Notice $$$K \le 200$$$, and answer can be only o or x, so a 01trie is expected.

Then we found that $$$O(QK)$$$ is reasonable to pass, so just brute forcce and modify the trie each time, and maintain the subtree-size fo querying rank.

There's a trap that one can pass if he got atleast an o.

F

Classical $$$HW \le 2 \times 10^5$$$, so let's come up with an $$$O(H^2 W)$$$ algo.(assume $$$H \le W$$$)

Let's brute force the up and down border, and count the valid left and right border. So to make sure we don't count sth twice, we'll make sure that all the borders have a ..

Then we find out that it's hard to count for up and down border, but we see that counting it inversed is just simple, so let's use the inclusion-exclusion principle, and that's ok.

G

Magically easy. Just brute force like we're searching for the maximum number of divisors in a given range.(prefix.) How about that $$$D$$$?

Well, it's simple, just select a prime factor and force its exponent to be less than $$$D$$$'s. If then, ignore this prime factor when we're enumerating the next exponent.

Sorry for bad English.

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

trashABC abcd is easy but e is hard e>>>d

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

Was C harder than D?

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

Solved $$$A, B, C, D$$$ but too many penalties and $$$E$$$ is too hard :(

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

How can I solve E with 01-Trie?

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

Hello

I solve problem C without correction :)

Can you please translate the editorial in english ?

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

how much you want to overkill D ? me: yes.

EDIT: i just read the editorial for D and realized my approach was the inteded.. WHAT how is segmented sieve easier than brute forcing like this ?

also if anybody was wondering, here is the solution in O(N) for C with the two pointer mentioned in the editorial.

→ Reply