Codeforces Round #776 (Div. 3)

4 months ago, # |

Vladosiya's Div 3 rounds are really good. Looking forward to some great problems in the contest.

→ Reply

Vafo

4 months ago, # |

+11

Nice gift for 8th of march , and here's my best wishes to you on International Women's Day 2022 ! Wishing a very happy Woman's Day to strong, intelligent, talented and simply wonderful women of this world! Don't ever forget that you are loved and appreciated. And also good luck on Div 3 !

→ Reply

betao

4 months ago, # ^ |

Good luck also for mediocre and normal women (not only talented and strong ones) which also deserve respect

→ Reply

Vafo

4 months ago, # ^ |

maybe (simply wonderful) means also means what you said :) ?

→ Reply

Vadmanbat

4 months ago, # |

How long have I been waiting for this moment...

→ Reply

Another Mar.8th Round click here

4 months ago, # |

Can anyone help me understand why untrusted people will not be included in the rankings? The round is rated for anyone having a rating less than 1600 anyway so how is the decision having any effect on rating changes?

→ Reply

kalDima

4 months ago, # |

-8

Good luck at International Women's Round #1!

→ Reply

READUS.md

4 months ago, # ^ |

Actually this is not round #1 lol

→ Reply

4 months ago, # |

← Rev. 2 →

→ Reply

return-zero

4 months ago, # |

Lets Rock!! newbies

→ Reply

cf_iamaditya

4 months ago, # |

Finally** DIV 3** contest :)

→ Reply

Hamroz_JONN

4 months ago, # |

Plz, no number theory in problems

→ Reply

tro_phy

4 months ago, # ^ |

Plz, number theory in problems

→ Reply

ItsEZ

4 months ago, # |

+13

Finally my first participation as unrated one.

→ Reply

drkcodr

4 months ago, # ^ |

-8

how to check if I am doing unrated one?

→ Reply

shiro

4 months ago, # |

implementation forces

→ Reply

vietdoo

4 months ago, # |

It took me 20 minutes to understand the statement output 2 numbers in next n lines of the problem C

→ Reply

sergeev.PRO

4 months ago, # |

+13

Really cool round. Thanks to creators

→ Reply

Amrit_4343

4 months ago, # |

Logic for C please?? is it implementation based problem

→ Reply

sergeev.PRO

4 months ago, # ^ |

Take 2 * n minimums and after sort them by coordinate

→ Reply

Armita.Alimardani

4 months ago, # ^ |

how can we sort the array in a way that we would know the index of every element before sorting with O(n log n) solution ?

→ Reply

_icy_

4 months ago, # ^ |

Just store indexes somewhere, for example make a tuple (x, w, index)

→ Reply

sergeev.PRO

4 months ago, # ^ |

I used map, where key is w and value is index in not sorted vector

→ Reply

4 months ago, # |

I hate test case 27 of G.

→ Reply

Jhin

4 months ago, # |

when i read E I thought it's too easy but then i realized there are things i didn't count in my solution and it was too late

→ Reply

sirearsh

4 months ago, # ^ |

i thought too what ever i was thinking should work but it didn't. then i changed my perspective and did some implementation with multiset to check what would be answer if i change $$$i^{th}$$$ exam date.

→ Reply

Jhin

4 months ago, # ^ |

I think you should only change the smallest value but I didn't check that maybe if i delete a1 for example and put it somewhere else then maybe a2-a0 is the new smallest value

→ Reply

sirearsh

4 months ago, # ^ |

yes you are right only difference can be made by removing minimum gaps. also need to make sure there are two ways to remove each gap that is not the left most. and also the way i implemented it didn't hurt to check every index, so to keep code a bit simple i didn't think of optimizing on that

→ Reply

variety-jones

4 months ago, # |

← Rev. 2 →

+23

Problem G: Counting Shortcuts is a great extension of ABC211: Number of Shortest Paths

In fact, you only need 5 to 6 lines of code changes in the Atcoder version to get it working.

I've summarized my approach for ABC211: D in this comment

How to extend it to this version?

First, break it into 3 parts. If the shortest path is of length $$$\delta$$$, we need to compute paths of length $$$\delta - 1$$$, $$$\delta$$$ and $$$\delta + 1$$$. Computing $$$\delta - 1$$$ is a trick question, you should figure that out yourself. Computing $$$\delta$$$ is same as ABC211:D. So, we just need to compute paths of length $$$\delta + 1$$$.

As mentioned in the previous comment, edges in a BFS tree can only exist between nodes of same level (horizontal edges) or consecutive level (vertical edges). If we observe a shortest path, it needs to descend the tree at each stage, i,e, it can only contain vertical edges. A path length of $$$\delta + 1$$$ implies that we added one extra edge in our shortest path. Notice that this extra edge cannot be a vertical edge, as we will miss the target vertex by 1 height. So, we are allowed to add one edge between nodes on the same level. This simplifies it to,

How many paths from source to target are present such that you are allowed to use EXACTLY 1 edge at same level.

Let's rename the DP of the previous problem to $$$dp\_tight$$$, and the DP array of the new problem to $$$dp\_loose$$$.

$$$dp\_tight[node]$$$ is the number of ways to reach $$$node$$$ from $$$source$$$ when you are not allowed to use unnecessary edges.

$$$dp\_loose[node]$$$ is the number of ways to reach $$$node$$$ from $$$source$$$ when you are allowed to use exactly one extra edge.

To compute $$$dp\_loose[node]$$$, we need to consider every edge on the same level (horizontal edges), and increment the $$$dp\_loose$$$ of one vertex by $$$dp\_tight$$$ of the other vertex. Since we should precompute the DP values of all nodes on the same level before populating DP values of next level, we can use a temporary queue for each level (Although I think we can do it in one pass too).

Time Complexity: $$$O(N)$$$

Code

queue<int> bfs;
vector<int> level(n, -1);
vector<long long> dp_tight(n, 0), dp_loose(n, 0);


level[source] = 0;
dp_tight[source] = 1;
dp_loose[source] = 0;
bfs.push(source);

while(not bfs.empty()) {
	int q_size = bfs.size();
	queue<int> wait;
	while(q_size--) {
		auto now = bfs.front();
		bfs.pop();
		wait.push(now);

		for(auto child : adj[now]) {
			if (level[child] == level[now]) {
				add(dp_loose[child], dp_tight[now]);
			}
		}
	}
	
	while(not wait.empty()) {
		auto now = wait.front();
		wait.pop();
		
		for(auto child : adj[now]) {
			if (level[child] == -1) {
				level[child] = level[now] + 1;
				add(dp_loose[child], dp_loose[now]);
				add(dp_tight[child], dp_tight[now]);
				bfs.push(child);
			} else if (level[child] == level[now] + 1) {
				add(dp_loose[child], dp_loose[now]);
				add(dp_tight[child], dp_tight[now]);
			}
		}
	}
}

long long res = dp_tight[target] + dp_loose[target];
res %= mod;
cout << res << "\n";

→ Reply

Penguin07

4 months ago, # ^ |

I think you mean Problem G.

→ Reply

variety-jones

4 months ago, # ^ |

Thanks, corrected.

→ Reply

boldcounselor

4 months ago, # |

+12

Feel like output for C could have been simplified without taking away from problem difficulty. But pretty fun contest anyways.

→ Reply

4 months ago, # ^ |

Took me eternity and 2-3 wrong submissions to figure that out on my own

→ Reply

4 months ago, # |

+18

Anyone else ? Who wasted 10 minutes thinking about output in C because of poor language

→ Reply

bratezz

4 months ago, # ^ |

yeah, if it weren’t for the useless output of indexes in C, I wouldn’t get a bunch of execution errors and would have passed 20 minutes earlier, perhaps there would have been enough time to solve task D

→ Reply

I_Hate_This_Contest

4 months ago, # ^ |

← Rev. 2 →

+1
30 minutes*

→ Reply

loser_complex

4 months ago, # ^ |

I got the logic really early, but spent 30 minutes after misreading allotment of index i to coordinate. I alloted them according to their position of number line and spent a lot of time there :(

→ Reply

qwi

4 months ago, # |

I will reach expert if not hacked.

→ Reply

4 months ago, # ^ |

Congrats

→ Reply

4 months ago, # ^ |

Can you explain your approach for E?

→ Reply

NerfThis

4 months ago, # ^ |

← Rev. 5 →

use a sorted map, such as TreeMap in Java, then maintain all the gaps' count;
Try to remove a[i] for i in [1, n — 1], you will have 2 cases: case 1. insert a[i] in a gap where it has exams on both ends; you will pick the largest gap maxGap and put it in the middle to get a new gap of (maxGap — 1) / 2; case 2. insert a[i] at d with a new gap of max(0, d — a[n] — 1);

take the better one of the above 2 cases and compare it with the smallest key and update answer. During step 2, remember to update your map accordingly: first remove deleted gaps and add newly generated gaps. After processing a[i], restore the map for the next element.

I had this idea but forgot to take care of the special case where if we put a[i] at the end on d, it is just d — a[n] — 1 instead of (maxGap — 1) / 2. Feels bad :(

I've added some comments in my submission, the idea is fairly straightforward: 148911439

→ Reply

notwatermango

4 months ago, # ^ |

← Rev. 2 →

i tried using map in C++.... my last brain cell is trying to figure out why my code mutates the map in each iteration, tried using delete when key's value is 0, but when i add some value to it, keys are not appearing back.........

edit: i mistakenly deleted the value of the map not the key T_T, still got WA tho

→ Reply

NerfThis

4 months ago, # ^ |

I ran into a similar key not found error during contest. I think it is because the way I updated the sorted map.

→ Reply

4 months ago, # ^ |

but would'nt the complexity become more O(n*n) or O(n*nlogn)? That should give tle. You are doing this O(n) computation for every a[i].

→ Reply

NerfThis

4 months ago, # ^ |

← Rev. 2 →

it is O(N * logN), each iteration we uses 6 map operations (3 insert, 3 removal). Building the maps takes O(N * logN) then for each iteration, it takes 6 * log(N) time.

→ Reply

qwi

4 months ago, # ^ |

I binary searched the answer (maximum μ possible by shifting the element with minimum rest days before it). You can see that for some μ: all smaller values are possible to achieve, this forms an array of True and False: T T T T T F F F F ...

So now you can apply binary search to find the last T (Last T is maximum possible μ). Now, to find if the current candidate for μ is T or F. You can write a function F(M) which will return True/False if rest days before A[i] <= M for all i. You can try to achieve this by removing the element E with smallest rest days before it and placing it in between any two elements with maximum rest days.

My implementation for F() is very bad and I believe you will find much better code for understanding in top standings. Please ask if there is anything you didn't understand.

→ Reply

osource

4 months ago, # |

← Rev. 2 →

C is the one of the worst questions I have seen in a while. The last paragraph of the problem is so confusing, even looking at samples didn't help. I had the idea in 5 minutes, but took 4 WA's on test 1 just because the output formatting is wrong. Also, what does this line have anything to do with anything?

The order in which you output the endpoints of a segment is not important — you can output the index of the left endpoint first and then the number of the right endpoint, or the other way around.

This just makes the problem even more confusing. And lastly, would it kill you guys to give the initial points as sorted? So much extra implementation just to print the indices of the points in original order after god knows how many times I used sort().

On the other hand, the problem itself and the idea behind it is nice. I just don't like the fact that I have to spend 10 minutes on thinking about the solution + implementations and then 30 minutes to properly format the output just so that it passes samples.

→ Reply

4 months ago, # ^ |

agree

→ Reply

rhymehatch

4 months ago, # ^ |

Well, if you look at the shortest solutions the problem is very simple to code.

I also did not find the simplest solution and ended up needing 60+ lines of C++.

I had prefix sum array, suffix sum array, set when calculating the sums (dealing with inserting the biggest element or the same element in the heap), and then had to rediscover the pairs after finding the minimum.

The complexity was $$$O(m \log{m})$$$ for initial sort, and then $$$O(m \log{n})$$$ for the suffix sums and then $$$O(m)$$$ for min, and then again $$$O(m \log{n})$$$ for discovery of pairs.

I have no idea how I can simplify my thinking for the future.

On every contest I participated I wrote too much code, even if it was correct, it was just too much unnecessary stuff.

→ Reply

adeeb.hs1

4 months ago, # |

+17

Question C was worded so poorly!

→ Reply

podvalchik

4 months ago, # |

amazing problems) going to become a pupil

→ Reply

4 months ago, # |

too heavy implementations

→ Reply

ayushluthra2001

4 months ago, # |

-8

I am beginner and Today i am able to solve one problem first one. is it good for me

→ Reply

dvaravind

4 months ago, # ^ |

If you at least got idea of question 2 then you are at par with average pupil I guess!

→ Reply

octobuss

4 months ago, # |

ImplementationForces

→ Reply

VietHuy1

4 months ago, # |

Really amazing contest. Thanks for creating this.

→ Reply

4 months ago, # |

Open hacking means if I fail in hacking a solution it would not negatively affect me?

→ Reply

spookywooky

4 months ago, # ^ |

Yes, by hacking you can only win.

→ Reply

4 months ago, # ^ |

thanks.

→ Reply

Manikm

4 months ago, # |

Can we get -1 in D?

→ Reply

Penguin07

4 months ago, # ^ |

No. It is always possible to sort the array. Think of it as bubble sort, but use rotates instead of swaps. Every time we move the greatest element to the right, and repeat the same process on the remaining elements until the array is sorted.

→ Reply

llc5pg

4 months ago, # ^ |

Can you elaborate on what do you mean by Every time we move the greatest element to the right ?

→ Reply

bluescorp

4 months ago, # ^ |

Go in reverse. Think about how many rotations are required to move n back to the last index. Now look at the array till n-1 index only and do the same thing.

→ Reply

Dr_John_WATSON

4 months ago, # ^ |

no, it is always possible to sort an array by rotating its prefix. actually what i have observed, this fact is used in quite some problems. For instance, this problem

→ Reply

asawa.harsh

4 months ago, # ^ |

Thanks for sharing. I wrote a -1 condition in the contest without thinking much

→ Reply

4 months ago, # ^ |

It's better to have it and don't need it than need it and don't have it.

→ Reply

Alpha-Go

4 months ago, # |

Is it necessary for the answer of Problem G to module 1000000007?

→ Reply

satyam_343

4 months ago, # ^ |

+12

Yes

It is easy to construct a test case for which answer is $$$2^k$$$ if $$$n=3k+1$$$.

→ Reply

MinumCoklatPanas

4 months ago, # |

is there a solution for E that does not involve too many caseworking? my solution had to consider like 6 cases to pass.

Also, props to the very strong sample case that actually helped a lot

→ Reply

Len

4 months ago, # ^ |

Binary search, to check if x is okay find first gap with length < x and try to remove one of endpoints of the gap. Try to place the removed exam in midpoint of gaps, or at the end of session.

→ Reply

clams

4 months ago, # ^ |

you don't really need binary search tho

→ Reply

cr0w

4 months ago, # ^ |

you can check out my solution, I made it pretty similar to yours. solution

→ Reply

Sakura_mw

4 months ago, # |

← Rev. 2 →

Problem G is very similar to this problem, with the subject of weighted directed graph;

Additionally, more sophisticate version is NOIP2017-S P3953, with the restrict of weighted directed graph($$$w_i \ge 0$$$), to calculate the number of ways of path length no more than minimum_path + k.

→ Reply

saarang

4 months ago, # ^ |

← Rev. 2 →

It is the exact same as the problem [here](https://github.com/T1duS/CompetitiveProgramming/blob/master/Olympiad/IOITC/2020/AlmostShortestPaths%20(EN).pdf ). The same link contains the intended solution as well.

→ Reply

timreizin

4 months ago, # |

+32

It's funny that there is no pretest with answer >=998244353 in G:)

→ Reply

Alpha-Go

4 months ago, # ^ |

Yes, ridiculous

→ Reply

TanayMaheshwari

4 months ago, # |

Is there an O(n) time complexity solution for D?

→ Reply

limbutimbu

4 months ago, # ^ |

misread D's constraints, for almost 1.5 hrs was trying to find O(n) for D but couldn't:(

→ Reply

kartik_pal

4 months ago, # ^ |

same bruh :( wasted lot of time

→ Reply

wakaranai

4 months ago, # ^ |

Dunno, but you can do it in O(nlogn) with implicit treap.

→ Reply

Anjaneyrai

4 months ago, # |

is anyone else getting TLE on problem C??

→ Reply

TrieMaster

4 months ago, # ^ |

← Rev. 3 →

You got TLE because every time , u input a point , u are sorting the vector again and again

Here is the accepted submission : 148914881

Also avoid using unordered_map(directly without any custom hash), You can read more about it here : https://codeforces.com/blog/entry/62393

Accepted submission with map instead of unordered_map : 148914850

→ Reply

Macho2

4 months ago, # |

How to solve G? any hints?

→ Reply

Beyrad

4 months ago, # ^ |

dp on Bfs tree

→ Reply

codemastercpp

4 months ago, # |

-8

Video Editorial for A-E for anyone looking

→ Reply

__AhmedSamir__

4 months ago, # |

← Rev. 2 →

I try to hack c but i got Unexpected verdict what is this mean ?!

→ Reply

TwentyOneHundredOrBust

4 months ago, # |

+32

There is an issue with the problem G: the variable $$$t$$$ has been reused. Please fix immediately. Highest priority.

→ Reply

_DEXTER__

4 months ago, # |

Hints for problem E ?

→ Reply

misteg168

4 months ago, # ^ |

← Rev. 4 →

I think the way I solve wasnt the expected solution but try this:

hint 1

hint 2

Solution

→ Reply

kartik_pal

4 months ago, # |

can we do d in o(n)?

→ Reply

Vladosiya

4 months ago, # ^ |

As we think it can't be solved faster than O(n * log(n))

→ Reply

liangruichen

4 months ago, # |

← Rev. 2 →

hope to be Specialist

Oh, I submitted B for three times. I might not be Specialist

→ Reply

CCPSDCGK

4 months ago, # |

+80

The pretests of G were so weak that I used 998244353 as the modulo in this problem and passed them!

But today I was hacked!

→ Reply

Forza_Ferrari

4 months ago, # ^ |

+24

fun fact:the answers to pretests after 12 are all 1 :)

→ Reply

daaris

4 months ago, # |

did rating change for anyone? pls ack (myself new to codeforces) It hasn't changed for me yet

→ Reply

adityagamer

4 months ago, # |

My rating is 1200. Why was this round unrated for me?

→ Reply

4 months ago, # |

-10

Is there any indication that the match has been unrated? My friends and I have found that this match is Unrated for us. A lot of thanks if you could reply to me. :(

→ Reply

imtiyazrasool92

4 months ago, # ^ |

after system testing it will be rated

→ Reply

4 months ago, # ^ |

But I remembered that it used to show 'System Testing' rather than 'Finished' ?

→ Reply

adityagamer

4 months ago, # ^ |

What is system testing?

→ Reply

4 months ago, # ^ |

That is testing your code with all successful-hacking datas.

→ Reply

adityagamer

4 months ago, # ^ |

thanks. how long does this usually takes?

→ Reply

cdmsm17

4 months ago, # ^ |

I actually participate in the edu model for the first time，when usually does the rating change after the open hack？

→ Reply

4 months ago, # ^ |

But why today System test came so late unlike before? XD

→ Reply

cdmsm17

4 months ago, # ^ |

Forgive my poor English. It works as the "Educational Codeforces Round"，so you do not need to get through the System test and you cannot hack others through the contest too. However,after the contest,everyone's submissions will open to the public 12 hours.Then everyone can make a hack. But the open hack has already ended long time ago,so i don't know why either.

→ Reply

4 months ago, # ^ |

← Rev. 2 →

→ Reply

Edric_Albert

4 months ago, # |

Why this round i have unrated?

→ Reply

Real_potatohead0

4 months ago, # ^ |

← Rev. 2 →

same...my rating hasn't changed.

→ Reply

BrilliantWilliam

4 months ago, # ^ |

same either...

→ Reply

fyzzz

4 months ago, # ^ |

me too……

→ Reply

4 months ago, # |

In this contest, I found an act of unfair means where the user D_K_307 hacked his solution from a fake account to increase his score. Is there a way to report such things ? Proof here

→ Reply

moonhero

4 months ago, # ^ |

In div.3 contest you can't increase your score with hacking

→ Reply

4 months ago, # ^ |

Cool, but still it's a wrong practice and will be effective for some contests. I have seen some users in past too doing this.

→ Reply

D_K_307

4 months ago, # ^ |

I did not have any Idea about hacking So I just tried it in div.3 contest Beacause I don't know this. Sorry For that.

→ Reply

Edric_Albert

4 months ago, # |

After the system testing. Still didn't change the rating...

→ Reply

4 months ago, # ^ |

Waiting for the same. Expecting increase in rating but not scared if it goes unrated or something :(

→ Reply

Edric_Albert

4 months ago, # ^ |

ya same bro :(

→ Reply

cschill

4 months ago, # ^ |

Man I was about to go expert, why this rating haven't changed yet

→ Reply

4 months ago, # ^ |

I would be close too. :(

→ Reply

cschill

4 months ago, # ^ |

The rating predictors ain't couting out the not-trusted participants.

So, I think +10 extra will be definitely there.

Hope we both get the DARk BLUE.

→ Reply

4 months ago, # ^ |

<3 <3

→ Reply

4 months ago, # ^ |

It's there in the unrated graph ;(

→ Reply

yangzhibo123

4 months ago, # |

Everyone's rating hasn't been changed yet.I hope I can get to green.

→ Reply

Applepi_228

4 months ago, # |

Mr. Vladosiya I think it is your best contest.Make more contests

→ Reply

yangzhibo123

4 months ago, # ^ |

I agree with you.I hope that Codeforces can hold more div.3 contests.

→ Reply

loser_complex

4 months ago, # |

← Rev. 2 →

Waiting for rating changes with 29138 others :)__ Edit: Released yaay

→ Reply

ZBHRuaRua

4 months ago, # |

The system told me that I cheated because of my Problem G solution coinciding with others. However, this problem had a same version on http://poj.org/problem?id=3463 ,and I had finished the problem with the help of a blog https://www.cnblogs.com/xingxing1024/p/5224363.html .So I use the code to finish problem G.Is it illegal?

→ Reply

ZBHRuaRua

4 months ago, # ^ |

The blog was posted in 2016,I cant understand why i am cancelled in this round...

→ Reply

varnit238

4 months ago, # ^ |

my problem d is coinciding with others but i did it on my own what can i do in that case !?

→ Reply

lovessp

4 months ago, # |

The system told me to cheat because my g question is highly similar to others, but this question is written with reference to a board written before. The link is: https://www.acwing.com/problem/content/385/ , I did this question six months ago. I hope I can get a reply. Thank you.

→ Reply

ImplementingForces

4 months ago, # |

← Rev. 2 →

-12

[deleted]

→ Reply

rafatoa

4 months ago, # |

Nice contest, I really liked it! I went from newbie all the way up to specialist :D!

→ Reply

yusufmalikul

4 months ago, # |

I got my first rating from this contest :) Thanks for creating Div.3!

→ Reply

liangruichen

4 months ago, # |

is there an Editorial?

→ Reply