AtCoder Beginner Contest 164 Announcement

5 лет назад, # ^ |

← Rev. 2 →

+34

I'm 1400~1500 on Atcoder.

If 1999 on Atcoder means 1800~1900 on CF.

Than I'm 1200~1300 on CF.

Hello everyone I'm a beginner.

→ Ответить

Trgt_2021_explosion

5 лет назад, # ^ |

Common, it might not be your saturation level (might not have attended enough contest)

→ Ответить

aramun_haesulla

5 лет назад, # ^ |

In AtCoder, when you participate in only a few contests your rating is much lower than your actual strength. You need to participate in at least 10 contests in order to get accurate rating.

→ Ответить

okwedook

5 лет назад, # ^ |

I just participated in a few contests and now have around 1550. Are you sure what you're telling is true?

→ Ответить

WaterColor2037

5 лет назад, # ^ |

It will need a little more contest for your rating to be converged enough to your "actual" rating, because the rating shown is actually the lower bound of ninety-something-percent confidence interval of rating. Generally it needs about 14 times of participation to rated contests until the rating shown becomes high enough. (The "provisional" hint shown on the left of your rating also suggests this)

→ Ответить

towhid1zaman

5 лет назад, # |

+16

hope everything will be fine this time!

→ Ответить

ShineEternal

5 лет назад, # |

hope everyone will get full marks this round！

→ Ответить

mycontest

5 лет назад, # |

Hope it will never have problems(like 163) this time...

→ Ответить

aramun_haesulla

5 лет назад, # ^ |

+10

why, what was problem with problems of 163?

→ Ответить

solvemproblr

5 лет назад, # ^ |

Just read this blog

→ Ответить

5 лет назад, # |

+59

I hate Matrix Construction.

→ Ответить

5 лет назад, # ^ |

+13

I have given up.

F is too hard to solve for me.

→ Ответить

box

5 лет назад, # ^ |

← Rev. 2 →

Am I the only one who did a randomized solution for F?

My method was like this:

First, decompose the matrix into 64 layers, with one layer for each bit, since bits on different layers don't affect each other.
Then, for each enforcement that's "AND = 1" or "OR = 0", set the corresponding row/column to 1 or 0.
If there are collisions (one cell set to both 1 and 0) then immediately return impossible,
Otherwise, for each of the cells that were neither assigned 0 nor assigned 1, randomly assign it 0 or 1.
Check if the resulting matrix fulfills requirements.
If not, randomly assign them again. If you have assigned them enough times (100000) and each time it failed, return impossible,

Code

→ Ответить

WaterColor2037

5 лет назад, # ^ |

Unfortunately your solution fails against the following test case. Your solution outputs -1, but a valid answer exists.

Test Case

50
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Similar input with larger input leads to TLE too.

→ Ответить

box

5 лет назад, # ^ |

Ah, I see — this is one of the test cases with exactly one solution? Thanks for hacking my wrong method!

I initially expected that there would either be a lot of possible outputs or none at all. Turns out I was wrong :)

→ Ответить

5 лет назад, # ^ |

I like problem F last time. But I have to give up this time.

→ Ответить

Lmntrix11

5 лет назад, # |

How did you think of D?

→ Ответить

Abhinandan_Arya

5 лет назад, # |

← Rev. 2 →

-94

E is much difficult

→ Ответить

5 лет назад, # ^ |

+22

Don't you realize you calculate the same pair twice

→ Ответить

5 лет назад, # ^ |

1-indexed, for

$$$1 \leq i \leq j \leq |S|$$$

instead of

$$$0 \leq i \leq j \le |S|$$$

→ Ответить

5 лет назад, # ^ |

+11

Usually the discussion starts after the contest finished.

→ Ответить

5 лет назад, # ^ |

Haven't you seen the restrictions?

→ Ответить

Abhinandan_Arya

5 лет назад, # ^ |

oh by mistake i have get the result with bruteforce with array starting indexing convention . so sorry for that

→ Ответить

HBM88

5 лет назад, # |

+14

My first Atcoder contest...wow, this is beginner? I'm stuck on D. Feel like an idiot.

→ Ответить

towhid1zaman

5 лет назад, # |

+17

How to solve E?

→ Ответить

5 лет назад, # ^ |

+18

it's easy to show that $$$5000$$$ silver coins is enough to go to every city,because you can go through every edge with them.so just break one city into $$$5000$$$ points $$$(city,money)$$$ and use dijkstra.

→ Ответить

errorgorn

5 лет назад, # ^ |

isnt the maximum 2500

→ Ответить

5 лет назад, # ^ |

+19

$$$2450$$$

→ Ответить

5 лет назад, # ^ |

actually $$$2450$$$ is enough because the longest shorest path is not longer than $$$49$$$.

→ Ответить

5 лет назад, # ^ |

but i was silly so i used $$$5000$$$ XD

→ Ответить

Agnimandur

5 лет назад, # ^ |

Just to be safe, I used up to 10000 silver coins, then did a state dijkstra.

→ Ответить

ExplodingFreeze

5 лет назад, # ^ |

10000 got AC? At first I also wrote 2 * sum of edges (10000 at worst) to be safe but got TLE, then changed to sum of edges and got accepted.

→ Ответить

raja1999

5 лет назад, # ^ |

The edges will be of the order N*5000*5000 when all c[i] are 1. Will dijksta run in time for this number of edges?

→ Ответить

cheissmart

5 лет назад, # ^ |

← Rev. 4 →

+32

You don't need that many edges. Just connect (node, coins) -> (node, coins + c[i])

→ Ответить

Agnimandur

5 лет назад, # ^ |

-19

No, the problem specifically says that the maximum number of edges is 100. Therefore, in the state graph the maximum number of edges is 100*5000 = 500000.

→ Ответить

5 лет назад, # ^ |

why so many edges?only $$$5000\times(n+2m)$$$ edges needed

→ Ответить

raja1999

5 лет назад, # ^ |

yes, my mistake.

→ Ответить

5 лет назад, # ^ |

But can $$$O(n^4 logn)$$$ pass???

→ Ответить

ILoveBitches

5 лет назад, # ^ |

Shortest path -> state [N][K] -> minimum time to reach node N with silver coin K. we can take Maximum K as 2500. since the max cost of an edge is 50. and we will at most take N-1 edges to reach target.

→ Ответить

cheissmart

5 лет назад, # ^ |

← Rev. 2 →

+19

I think my E is $$$O(A_{max}^2 * N^3)$$$. link to submission

→ Ответить

hitch

5 лет назад, # ^ |

← Rev. 2 →

could someone spot the mistake in my code for E? been losing sleep over it submission

→ Ответить

hitch

5 лет назад, # ^ |

nvm, fixed it.

→ Ответить

haishand

5 лет назад, # ^ |

how did you fix code? i met the same WA.

→ Ответить

hitch

5 лет назад, # ^ |

my INF was too small

→ Ответить

Ugnwd

5 лет назад, # |

How to solve D ?

→ Ответить

aj54

5 лет назад, # |

+18

The English Commentary for Problem D: Multiples of 2019 is here

→ Ответить

ritik_patel05

5 лет назад, # ^ |

Thanks a lot! That explanation helped me.

→ Ответить

5 лет назад, # ^ |

There must be simpler way, this is not level of D.

→ Ответить

dalip_patra

5 лет назад, # ^ |

This may help. https://atcoder.jp/contests/abc164/submissions/12378162

→ Ответить

jhjfbsbfkbjfnfnfjfj

5 лет назад, # ^ |

for a string 2114 pref[0] would give us 4%2019 pref[1] would give 14%2019 pref[2] would give 114%2019 and pref[3] would give 2114%2019. right? then you afterwards what you implemented using map is unclear to me. please explain this.

map<ll,ll>mp;
ll ans = 0;
for(ll i=0;i<n;i++)
{
    if(pref[i]==0)ans++;
    ans+=mp[pref[i]];
    mp[pref[i]]++;
}

→ Ответить

dalip_patra

5 лет назад, # ^ |

It is just prefix sum logic.

→ Ответить

aKILLL

3 года назад, # ^ |

← Rev. 2 →

Can anyone help with problem D?
I somehow arrived at if the range (i,j) should be divisible by 2019 then
$$${(1,j)}/{10^j} \equiv {(1,i-1)}/{10^{i-1}} (\mod 2019)$$$
where (i,j) is the base 10 representation of the number $$$S_i S_{i+1}....S_j$$$
Idk how to solve it further. Please help. I have also read the editorial and saw various solutions but I don't understand how are they reaching the final form?

→ Ответить

youtsuha

5 лет назад, # ^ |

thanks a lot

→ Ответить

Chodermal1

5 лет назад, # ^ |

Bro i had a time complexity doubt since 10^8 takes 1 sec ,so 2019*2e5 =403800000 which should take 4 sec but soln is accepted.Can u explain ?

→ Ответить

aj54

5 лет назад, # ^ |

Hi, I think for simple operations, the order 9 per second will execute instead of order 8. So,I think that works, https://mirror.codeforces.com/blog/entry/17799?#comment-226617 have a look at their discussion!

→ Ответить

Chodermal1

5 лет назад, # ^ |

thanks!!

→ Ответить

aziz17_01

5 лет назад, # |

-8

How you solve D? I used brute force but it gave me TLE? Do you have any ideas?

→ Ответить

Trgt_2021_explosion

5 лет назад, # ^ |

← Rev. 3 →

+10

Just construct number from start contiguously and store frequency of remainder. If $$$n$$$ is length of string at stage $$$i$$$ number will be $$$\,\,\,N\,= \,d_0*10^{n-1}+d_1*10^{n-2}+...+d_{i-1}*10^{n-i-1}$$$

let $$$R_i= N\mod2019$$$

So at any stage if remainder is $$$R_i$$$ see how many time this remainder has occurred previously excluding current one and add this to final result. For this you ca just use an array or Map whatever.

→ Ответить

5 лет назад, # ^ |

That is nice explanation, thanks!

→ Ответить

shahil_005

5 лет назад, # ^ |

I can't understand the logic that if for an index i,if the remainder is equal to the remainder at any other index j,then how the number formed by the elements between i& j would be divisible by 2019? Can someone please explain.

→ Ответить

Matuagkeetarp

5 лет назад, # ^ |

Can you please provide me the code of this approach, I'm getting WA.

→ Ответить

Trgt_2021_explosion

5 лет назад, # ^ |

Sure.this.

And to explain his doubt. let's say remainder $$$r$$$ is same for two indices $$$i\,and\,j\,(i<j)$$$ so number formed at index $$$i\,and\,j$$$ will be of the form $$$N_i=2019*k_1+r\,\, and\, N_j=2019*K_2+r$$$ so number between segment $$$[i,j]$$$ will be $$$(N_j-N_i)$$$ whose remainder got canceled out and we got $$$2019*(K_2-K_1)$$$ which is clearly divisible by 2019.

→ Ответить

gaurav1903

5 лет назад, # ^ |

thanks man,that helped a lot

→ Ответить

akulenok

5 лет назад, # ^ |

Can you please explain why your code to this input 12019 gives this output 2, but 12019 mod 2019 != 0?

→ Ответить

shahil_005

5 лет назад, # ^ |

← Rev. 2 →

The number formed from i=2&j=2 is divisible by 2019,so there are 2 pairs:(1,5) &(2,2). https://atcoder.jp/contests/abc164/tasks/abc164_d In the constraints ,you can see i can be equal to j.

→ Ответить

akulenok

5 лет назад, # ^ |

Thanks.

→ Ответить

WaterColor2037

5 лет назад, # ^ |

By the way all the digits are guaranteed to be between 1 and 9 in the original problem.

→ Ответить

akulenok

5 лет назад, # ^ |

Thanks, my bad :(

→ Ответить

alex223

5 лет назад, # ^ |

← Rev. 6 →

My explanation + code

Take for example divisor = 13 and S = 39262.

Reminder of 2 / 13 is 2, save it.
Reminder of 62 / 13 is 10, save it.
Reminder of 262 / 13 is 2, but we have already seen this reminder. What does it mean?

(262 - 2) % 13 = 260 % 13 = 0, so 260 is a multiple of 13. But we are interested only in 26. Turned out if x * (any power of 10) mod divisor = 0, then x % divisor = 0 if divisor isn't 2 or 5.

For 39262 / 13 reminder is again 2 and we have seen it two times: (39262 - 262) % 13 == 0 and (39262 - 2) % 13 == 0, so add them both.

→ Ответить

Matuagkeetarp

5 лет назад, # ^ |

Hey, thanks for the detailed explanation. This problem is similar to ABC(atcoder beginner contest) 158E but I'm getting WA in 158E problem which is a general case. Here's my code Can you help in that?

→ Ответить

alex223

5 лет назад, # ^ |

← Rev. 2 →

1st test is for P = 2 (you can see all test cases here). And for 2 and 5 "if x * 10^k % divisor = 0$, then x % divisor = 0" doesn't work. For example, 7 * 10 % 2 = 0, but 7 % 2 = 1.

→ Ответить

Matuagkeetarp

5 лет назад, # ^ |

So what how should I check divisibility for p=2 and p=5?

→ Ответить

Hepic_Antony_Skarlatos

5 лет назад, # ^ |

A number is divisible by 2 if and only if its lowest digit is even.

A number is divisible by 5 if and only if its lowest digit is 0 or 5.

Storing a prefix counter of the appearances of $$$S_i$$$ such that $$$S_i == 0 \; (mod \; P)$$$ for $$$P = 2$$$ or $$$P = 5$$$ is enough.

→ Ответить

a14789654

5 лет назад, # ^ |

← Rev. 4 →

What is the name of this kind of alg?

→ Ответить

gaurav1903

5 лет назад, # ^ |

It has a brilliant application of prefix sum algorithm https://www.geeksforgeeks.org/find-if-there-is-a-subarray-with-0-sum/

this helped me a lot. hope it helps

→ Ответить

a14789654

5 лет назад, # ^ |

I got the "sum", but not the "multiple".

→ Ответить

shenxy13

5 лет назад, # |

+54

Am I mistaken in saying that today's ABC D has an identical solution to ABC 158E? The two problems seem to be asking for exactly the same thing.

→ Ответить

JKLover

5 лет назад, # ^ |

Actually today's problem is easier, for the modulo is given as 2019, which is a relatively prime of the base, 10.

→ Ответить

lemongrab

5 лет назад, # ^ |

I remembered that I had seen it, couldnt solve it neither then nor now.

→ Ответить

dunjen_master

5 лет назад, # ^ |

Same XD !!

→ Ответить

PRESS_F_2_PAY_RESPECT

5 лет назад, # ^ |

We just need to take the extra case of p=2 and p=5 in problem 158E. Rest is all same:)

→ Ответить

5 лет назад, # |

← Rev. 2 →

-18

Are standings hidden ?

→ Ответить

towhid1zaman

5 лет назад, # ^ |

→ Ответить

5 лет назад, # ^ |

This is what I see during the whole contest and still it is showing the same.

→ Ответить

Norrius

5 лет назад, # ^ |

+20

Click on the dropdown to the right of "Customize" and see if you have overly restrictive filters.

→ Ответить

5 лет назад, # ^ |

You are right, Thanks.

→ Ответить

kashita

5 лет назад, # |

What's the approach for D ? I used the stoi and substr function , got WA.

→ Ответить

aj54

5 лет назад, # ^ |

Hey! You can refer the commentary here

→ Ответить

amane-ame

5 лет назад, # |

+68

The problem F can be easily solved by maximum-flow with lower bounds. See this submission.

→ Ответить

amane-ame

5 лет назад, # ^ |

← Rev. 2 →

+55

→ Ответить

pavel.guskov

5 лет назад, # ^ |

Nice one :)

→ Ответить

O_E

5 лет назад, # ^ |

can you please elaborate more i don't understand is this graph for the first sample? i understand that you solve for each bit independently but how do you add the edges?

→ Ответить

spar5h

5 лет назад, # ^ |

I thought of this but I didn't have enough time to implement it :( Should it pass considering there can be around $$$64N^2$$$ vertices/edges?

→ Ответить

amane-ame

5 лет назад, # ^ |

← Rev. 2 →

There are only $$$\mathrm O(n)$$$ edges not weighted $$$1$$$. I think the Dinic algorithm still runs in $$$\mathrm O(m+\sqrt mn)=\mathrm O(n^2)$$$ time although I can't proof it.

→ Ответить

wingman__7

5 лет назад, # |

My approach

This is my approach which got me TLE I pre-computed all the modulo values but to find (L, R) pairs I had to use a nested for loop. Can someone please tell me how do I find the number of (L,R) pairs in O(n) time ?

→ Ответить

lohit_97

5 лет назад, # ^ |

Hi, read problem 158E from this. https://img.atcoder.jp/abc158/editorial.pdf

It is almost similar but instead of 2019 you have to solve it for generic number P.

→ Ответить

saksham9575

5 лет назад, # |

My D approach
k starts from 0
Iterate from right and calculate (10^k%2019+digit at i-th index)%2019
store this in map and for every element in map calculate NC2 of that frequency

This problem is like calculating number of subarrays having sum%m as 0

→ Ответить

Ahmed_Allawati

5 лет назад, # ^ |

can you please explain why this problem is like calculating number of subarrays having sum%m as 0 ??

→ Ответить

saksham9575

5 лет назад, # ^ |

You are given a array you calculate prefix sum at every i-th index mod m
Now if prefix sum at two index(suppose i & j) is same then there is a subarray from (i+1,j) whose sum will be zero. So we can store each sum in map and choose any two index having same sum in NC2 ways. In this question instead of prefix we calculate suffix sum + power of 10. And we can choose indexs in NC2 ways.

→ Ответить

stefdasca

5 лет назад, # |

Video Tutorial for D

→ Ответить

5 лет назад, # ^ |

You could use vector.swap(v) instead of memcpy, which basically copies nothing but a pointer.

→ Ответить

stefdasca

5 лет назад, # ^ |

indeed, the runtime would have been even smaller, but at this point, it's still very fast.

→ Ответить

ADJA

5 лет назад, # |

+62

Why $$$0 <= a_{i, j} < 2^{64}$$$ in problem F? For some weird unsigned long long practice? :)

→ Ответить

2018LZY

5 лет назад, # |

I made me nervous that my codes were always CE. Actually,it's the "time" keyword that made this problem. Hope you all learn from my lesson.(How silly I was!) GL and HF.

→ Ответить

praktice

5 лет назад, # |

Can someone explain easy to implement solution for E?

→ Ответить

stefdasca

5 лет назад, # ^ |

$$$dp[i][silver]$$$ = shortest path from $$$1$$$ to $$$i$$$ such that you're left with $$$j$$$ silver coins.

$$$silver$$$ is at most $$$2500$$$ — $$$(N * 50)$$$

→ Ответить

siddharthabhi30

5 лет назад, # ^ |

← Rev. 2 →

I am not able to understand how 2500*50 states can be minimized by n*m*2500 iterations (n is vertex). If we see bellman ford , n*n iteration is required to minimize all n vertexes.

→ Ответить

https://atcoder.jp/contests/abc164/submissions/12395345

5 лет назад, # |

← Rev. 3 →

HELP!!!

For problem E:

I used dp.

$$$dp[i][j][k]$$$ means now standing at the $$$i-th$$$ node ,and have $$$Min(600,j)$$$ silver coins the $$$minimal$$$ time to go to k.

We can use $$$dp[i][j][k]$$$ to update other situation as follow.

$$$dp[i][j][k]+d[i]$$$ to update $$$dp[i][max(j-c[i],0)][k] $$$
$$$dp[i][j][k]+(the—time—from—it—to—i)$$$ to update $$$dp[it][Min(600,j+(the—number—of—silver—coins—required—from—it—to—i))][k] $$$

And I used shortest path to update it,but I fail in the second test which is line(pass all of the others!),what's wrong?

→ Ответить

lohit_97

5 лет назад, # ^ |

I am sorry I can't help you with the issue but why 600 ?

→ Ответить

5 лет назад, # ^ |

I see

→ Ответить

lohit_97

5 лет назад, # ^ |

I am not sure of what you see but is good to see that you can see something.

→ Ответить

5 лет назад, # ^ |

I'm wrong , 600 is too small.Thank you very much.

→ Ответить

JKLover

5 лет назад, # ^ |

Is 600 sliver coins enough?

→ Ответить

5 лет назад, # ^ |

No ,I fix it ,but I get TLE now...

Can you tell me if $$$O(n^4logn)$$$ can pass?

→ Ответить

5 лет назад, # ^ |

← Rev. 2 →

You can try the following :

dp[i][j] denotes minimum time to go to the ith node with j silver coins from 1.

Now repeatedly update this dp (n+1) times, as in bellman — ford. ( + 1 because initially I don't initialize it )

UPD : There is a case where this gets Wrong Answer. Sorry. Theoretically it requires O(m*m) iterations.

→ Ответить

ccsu_deer

5 лет назад, # ^ |

Can I see your code, thank you

→ Ответить

5 лет назад, # ^ |

Here you go

→ Ответить

ccsu_deer

5 лет назад, # ^ |

thanks bro

→ Ответить

haishand

5 лет назад, # ^ |

← Rev. 2 →

why iter n+1 times? for bellman-ford, it repeats at most n-1, plus 1 init should be n.

→ Ответить

5 лет назад, # ^ |

← Rev. 3 →

Thanks for pointing this. I tried to figure out what went wrong and I found that my solution is wrong as it requires O(n*n) iterations.

It passed due to weak testcase.

Testcases where I get WA : (An extension to 3rd sample case)

→ Ответить

haishand

5 лет назад, # ^ |

thanks bro. so do you mean the iteration should be num of edges? i'm curious how you figure it out? i have tried the whole day but no clues found.

→ Ответить

5 лет назад, # ^ |

It is O(n*n) because,

1) To reach node 1 to node t, You will buy coins O(n) times.

2) Among above O(n) cities, it takes O(n) edges to move to node where we buy the coins next.

→ Ответить

5 лет назад, # ^ |

Your submission can pass with given time complexity, but you are using much memory so it increases the time.

→ Ответить