Codeforces Round #584 (Dasha Code Championship Elimination Round) (div. 1 + div. 2)

5 years ago, # |

+68

Huge thanks to ... and me for testing

lol

→ Reply

5 years ago, # |

+42

Hope I get up early tomorrow for the contest!

BTW, I found “Small help” funny, it made me laugh.

→ Reply

mkagenius

5 years ago, # ^ |

wake up now..its about time

→ Reply

Ivan__Zaytsev

5 years ago, # |

← Rev. 3 →

+68

Don't get offended :)

→ Reply

JiaZeWei

5 years ago, # |

+16

"publish it on Youtube" reminds me of Codeforces Round #543.

→ Reply

VivaanGupta

5 years ago, # |

-10

Wish everyone high rating GL HF

→ Reply

tribute_to_Ukraine_2022

5 years ago, # |

+12

1410 appearing in sample output O_o. Errichto I love you.

→ Reply

rlajkalspowq

5 years ago, # |

-248

What's wrong with tourist today? He didn't perform well! And even a student from our school, aged $$$14$$$, has got a better rank than him!

→ Reply

PolarFlea

5 years ago, # ^ |

-9

It's not you who got a better rank than tourist, why R U so excited?

→ Reply

5 years ago, # |

-11

How to solve E2?

→ Reply

5 years ago, # ^ |

← Rev. 2 →

E1 was bitmask dp with complexity $$$O(3^n*m)$$$, I tried to improve it to $$$O(2^n*m+3^n*n)$$$ by only considering top 12 results for every bitmask, but somehow got TLE.

→ Reply

5 years ago, # ^ |

-8

Wow, could you outline the idea? My solution is O(mn + n^n), unfortunately...

→ Reply

5 years ago, # ^ |

Oops, my solution is $$$O(4^n*n)$$$. The idea is: for a prefix of columns and bitmask of rows store the answer.

→ Reply

5 years ago, # ^ |

Did you also consider we have $$$t \leq 40$$$ as the number of test cases. I had a same idea but I didn't start implementing it. Considering the number of test cases, I assumed such an idea would have no chance to pass the system tests.

→ Reply

_overrated_

5 years ago, # ^ |

I passed pretests in E1 with $$$O(t * (n * m ^ 3 + m * n ^ 2 * 2 ^ n))$$$

code link

→ Reply

5 years ago, # ^ |

+29

First realize you'll need at most N columns (with the N largest elements), then do a DP on all columns:

f(x,mask) = max sum you can do for rows in mask (it is a bitmask), starting from column X

→ Reply

5 years ago, # ^ |

Does it hold if some of the largest N is in the same column?

→ Reply

5 years ago, # ^ |

I meant this: sort columns by their largest number, and take the N biggest.

→ Reply

5 years ago, # ^ |

Okay, now it makes sense.

→ Reply

5 years ago, # ^ |

Could you prove it? Sorry for my dumb mind...

→ Reply

5 years ago, # ^ |

← Rev. 2 →

Yes, if you get these maximal columns, you're sure that you can rotate them in such a way that you get the maximal number of each column in its own row. Like:

2 1

1 4

So, if you took one more row, its maximal value would be less than the maximal values for each of those columns. So, with the above configuration, you can't use it to improve the configuration.

→ Reply

5 years ago, # ^ |

Got it, thank you.

→ Reply

Roundgod

5 years ago, # ^ |

+24

I think I solved it in $$$O(2^n n^3)$$$, by taking only the $$$n$$$ columns with largest maximum, and during a bitmask dynamic programming, transferring grid by grid.

→ Reply

Rpd-Strike

5 years ago, # ^ |

I have a solution in $$$O(3^n*n)$$$, what was your optimization to make the base $$$2$$$?

→ Reply

Roundgod

5 years ago, # ^ |

← Rev. 2 →

Transfer grid by grid instead of column by column.

→ Reply

5 years ago, # ^ |

+13

cell by cell*

And it's called broken profile, https://cp-algorithms.com/dynamic_programming/profile-dynamics.html

→ Reply

5 years ago, # ^ |

+16

Same as E1, just notice that you only need to sort columns by their maxima and take the top min(N, M) (if the sorted order isn't unique, just pick one). Proof: let's assume $$$M > N$$$, assign a column to each row maximum in the final solution and look at the smallest of these columns (in the picked order) that's not among the top $$$N$$$. If there's just one row maximum in this column, you can replace it by a column from the top $$$N$$$, suitably shifted. If there's more than one, you've chosen less than $$$N$$$ columns, so you can just add a column from the top $$$N$$$ and move one row maximum to it. Both cases result in one more of the top $$$N$$$ columns being chosen, so if you repeat this as long as possible, you'll either end up with the top $$$N$$$ columns all containing row maxima or no other columns containing row maxima. However, the former also implies there are no other columns containing row maxima, since there are just $$$N$$$ of them.

→ Reply

5 years ago, # ^ |

Got it, thank you.

→ Reply

VadymKa

5 years ago, # |

+23

Give us more problems next time pls.

→ Reply

https://www.youtube.com/watch?v=IaViSV0YBog

5 years ago, # |

+31

How are you sure that your solution to H is numerically stable?

→ Reply

Azret

5 years ago, # ^ |

-31

While Errichto didn't answer you, try watching his video of preration of problem H.

→ Reply

Petr

5 years ago, # ^ |

← Rev. 2 →

My solution involves division only at the beginning and at the end, the rest is obviously numerically stable:

Code

private double solveOne(List<TaskH.Segment> segments) {
            int n = segments.size();
            for (int i = 0; i < n; ++i) {
                TaskH.Segment s = segments.get(i);
                s.ptr = i;
                s.curEnergy = 0.0;
                s.maxEnergy = (s.right - s.left) / s.s;
                s.minEnergy = -(s.right - s.left) / (s.s + 2);
            }
            List<TaskH.Segment> segmentsByS = new ArrayList<>(segments);
            Collections.sort(segmentsByS, new Comparator<TaskH.Segment>() {
 
                public int compare(TaskH.Segment o1, TaskH.Segment o2) {
                    int z = Double.compare(o2.s, o1.s);
                    if (z == 0) {
                        z = Integer.compare(o2.left, o1.left);
                    }
                    return z;
                }
            });
            TreeSet<TaskH.Segment> available = new TreeSet<>(new Comparator<TaskH.Segment>() {
 
                public int compare(TaskH.Segment o1, TaskH.Segment o2) {
                    return o1.ptr - o2.ptr;
                }
            });
            available.addAll(segments);
            for (TaskH.Segment s : segmentsByS) {
                if (s.s == 0.0) break;
                s.alive = false;
                available.remove(s);
                NavigableSet<TaskH.Segment> after = available.tailSet(s, false);
                double capacity = s.maxEnergy - s.curEnergy;
                double spent = 0.0;
                while (!after.isEmpty()) {
                    TaskH.Segment t = after.first();
                    if (t.alive) {
                        double t1 = t.curEnergy - t.minEnergy;
                        double t2 = capacity - spent;
                        double transfer = Math.min(t1, t2);
                        spent += transfer;
                        t.curEnergy -= transfer;
                        if (t1 <= t2) {
                            available.remove(t);
                        } else {
                            break;
                        }
                    }
                }
                s.curEnergy += spent;
            }
            double res = 0.0;
            for (TaskH.Segment s : segments) {
                double v = (s.right - s.left - s.curEnergy * s.s) / (s.right - s.left + s.curEnergy);
                res += (s.right - s.left) / (s.s + v);
            }
            return res;
        }

→ Reply

Azret

5 years ago, # ^ |

Can you wrap that in a spoiler? :)

→ Reply

5 years ago, # ^ |

-9

Spoiler

if (t1 <= t2) {
    available.remove(t);
} else {
    break;
}

How is this numerically stable?

→ Reply

Petr

5 years ago, # ^ |

It doesn't matter how this comparison is resolved when t1 and t2 are close.

→ Reply

5 years ago, # ^ |

I can say the same about all the 14 codes I submit, but they do occasionally receive different verdicts, so I'm trying to understand why.

→ Reply

5 years ago, # ^ |

← Rev. 2 →

In short, there is no issue with catastrophic cancellation because incorrectly computing some sum as $$$S + e$$$ instead of $$$S$$$ gives us a new value $$$V - e$$$ instead of $$$V$$$ and the errors cancel out. And the formal proof of the whole thing should use absolute errors only but that's fine because we never get huge numbers.

→ Reply

5 years ago, # ^ |

60573091 this gets WA 19. You can press "Compare" and look at the changes from solution that gets WA 15. Really?

→ Reply

5 years ago, # ^ |

← Rev. 2 →

I'm not sure what you're talking about. My solution is different, it doesn't use any epsilon (well, only to check if something is 0 or greater than 0.1).

EDIT: I want to compute energy computed/saved for every walkway. I build a segment tree over that. Sort walkways by speed and in this order maximize energy used there without getting below $$$0$$$. I use a segment tree to get prefix sum and min prefix sum.

→ Reply

5 years ago, # ^ |

-17

Does your solution use sets, comparisons of doubles, or something similar?

→ Reply

5 years ago, # ^ |

+11

No, it doesn't.

code

#include <bits/stdc++.h>
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

using ll = long long;

struct Walkway {
	int start, end;
	double speed;
	void read() {
		scanf("%d%d%lf", &start, &end, &speed);
	}
	int len() const {
		return end - start;
	}
	bool is_zero() const {
		// any precision better than the one from the input
		return speed < 1e-11;
	}
	double max_saved() const {
		if(is_zero()) {
			return 0; // we walk at least 1m/s on 0-speed walkways and thus save no energy
		}
		else {
			return len() / speed; // energy saved while just standing on this walkway
		}
	}
	double max_used() const {
		return len() / (speed + 2); // energy used on running 2m/s here
	}
};

struct Node {
	double sum, min_pref;
	void init(double delta) {
		sum = min_pref = delta;
	}
	void merge(const Node& L, const Node& R) {
		sum = L.sum + R.sum;
		min_pref = min(L.min_pref, L.sum + R.min_pref);
	}
};
vector<Node> tree;
int BASE; // tree base (power of 2)

//const double eps = 1e-6;

int main() {
	int n, L;
	scanf("%d%d", &n, &L);
	vector<Walkway> walkways;
	int last_end = 0;
	for(int i = 0; i < n; ++i) {
		Walkway nxt;
		nxt.read();
		assert(last_end <= nxt.start);
		if(last_end < nxt.start) {
			walkways.push_back(Walkway{last_end, nxt.start, 0});
		}
		walkways.push_back(nxt);
		last_end = nxt.end;
	}
	if(last_end < L) {
		walkways.push_back(Walkway{last_end, L, 0});
	}
	n = walkways.size(); // because some new 0-speed walkways appeared
	BASE = 1;
	while(BASE < n) {
		BASE *= 2;
	}
	tree.resize(2 * BASE);
	for(int i = 0; i < n; ++i) {
		tree[BASE+i].init(walkways[i].max_saved());
	}
	for(int i = BASE - 1; i >= 1; --i) {
		tree[i].merge(tree[2*i], tree[2*i+1]);
	}
	// sort by speed
	vector<pair<double, int>> indices;
	for(int i = 0; i < n; ++i) {
		indices.emplace_back(walkways[i].speed, i);
	}
	sort(indices.begin(), indices.end());
	double answer = 0;
	for(pair<double, int> pp : indices) {
		int me = pp.second;
		double pref = 0; // sum over delta[0..me-1]
		for(int i = BASE + me; i > 1; i /= 2) {
			if(i % 2 == 1) {
				pref += tree[i-1].sum;
			}
		}
		debug() << imie(pref);
		// assert(pref >= -eps); // non-negative
		double min_pref = pref;
		for(int i = BASE + me; i > 1; i /= 2) {
			if(i % 2 == 0) {
				min_pref = min(min_pref, pref + tree[i+1].min_pref);
				pref += tree[i+1].sum;
			}
		}
		// spending more than 'min_pref' energy would put as below 0 at some point
		// min_pref could be negative what means that this walkway needs to provide savings
		double wanna_spend = min(min_pref, walkways[me].max_used());
		debug() << imie(wanna_spend);
		tree[BASE+me].init(-wanna_spend);
		for(int i = (BASE + me) / 2; i >= 1; i /= 2) {
			tree[i].merge(tree[2*i], tree[2*i+1]);
		}
		// energy spent = (s - 1) * t where s is my walking speed and t is time
		// t = len / (s + me.speed)
		double X = walkways[me].speed;
		debug() << imie(X);
		// (s-1)/(s+X) = en_spent / len
		// 1 - (X+1)/(s+X) = en_spent / len
		// (X+1)/(s+X) = 1 - en_spent / len
		double s = (X + 1) / (1 - wanna_spend / walkways[me].len()) - X;
		debug() << imie(me) imie(wanna_spend) imie(X) imie(s);
		// assert(-eps <= s && s <= 2 + eps);
		double t = walkways[me].len() / (s + X);
		answer += t;
	}
	printf("%.12lf\n", answer);
	// assert(tree[1].min_pref >= -eps);
}

→ Reply

NeiH

5 years ago, # |

← Rev. 4 →

-52

poor:<

→ Reply

sevlll777

5 years ago, # |

← Rev. 2 →

this problem is simillar to D https://mirror.codeforces.com/gym/102268/problem/F (code which got AC at D got AC at this problem)

→ Reply

Agnimandur

5 years ago, # |

+19

Bessie the Cow has come to Codeforces :)

→ Reply

eanacra

5 years ago, # |

-21

Very nice problemset! Thank you for the contest.

→ Reply

Agnimandur

5 years ago, # ^ |

-8

Could E1 have been solved entirely with implementation, or did it require dp?

→ Reply

5 years ago, # ^ |

It could. I found the 4 columns with the biggest max.value and bruteforced every possible combination of shifts.

→ Reply

ZenithINA

5 years ago, # |

-8

how to solve B? all i can think is simulating the condition one by one

→ Reply

5 years ago, # ^ |

Yes, exactly.

→ Reply

YashShah

5 years ago, # ^ |

Can you explain, how to simulate Problem B...?

→ Reply

5 years ago, # ^ |

We simply start with the initial configuration and run X trials. In my code, X = 50K, but I think that's overkill, some solutions use as little as 200, but better safe than sorry :) I haven't gotten around to a formal proof, though I'm sure there is one.

Anyway, on a single trial we go through all of the candles and check whether the i-th candle needs to be toggled. It boils down to the following equation:

current_time = a + bk

current_time — a = bk

current_time — a = 0 (mod b)

We check that condition for every candle, and, if it is true, toggle it. On every trial we update the maximum number of lighted candles. After the trials are over, we output the maximum.

→ Reply

gupta_samarth

5 years ago, # ^ |

Would it be correct to argue that, since $$$lcm(2,3,4,5) = 60$$$, every bulb will repeat after $$$60$$$ time steps. So you don't need to check times after $$$60+5$$$. But like you said, I didn't try a small amount to stay on the safe side.

→ Reply

SoulAdor

5 years ago, # ^ |

+14

Same, but lcm (2,4,6,8,10) = 120 and + 5 so I iterated from 0 to 125 exclusive and got accepted. Then tested for 0 to 124 to be sure and got wrong answer. You need twice those numbers because you are looking for a period, and full period is time on + time off, thus multiply by 2.

→ Reply

gupta_samarth

5 years ago, # ^ |

Yeah, I was also thinking that maybe we'll need twice of the lcm. Thanks for clarifying!

→ Reply

Jhin

5 years ago, # |

is D greedy ? I've tried to put the guests that has 2 types others have first but I think I'm missing something

→ Reply

Agnimandur

5 years ago, # ^ |

+12

I used DSU to solve D.

→ Reply

natofp

5 years ago, # ^ |

+22

Create graph, for each connected component with x vertices you can satisfy x-1 guests.

→ Reply

5 years ago, # ^ |

Wow.

I basically did the same thing, but I made that observation only for cycles, so I had to do additional work for non-cycles.

That explains how there were solutions for D for several minutes :)

→ Reply

5 years ago, # ^ |

D is just M — (sum of sizes of connected component — number of connected components)... so yes, if you count any graph traversal to be greedy

→ Reply

ZenithINA

5 years ago, # ^ |

← Rev. 2 →

[my bad]

→ Reply

5 years ago, # ^ |

At this point, no.

→ Reply

gupta_samarth

5 years ago, # ^ |

← Rev. 2 →

Can you help me see what's wrong with simply sorting given food preferences as pair ( also keeping minimum in pair as first ) and greedily calculating answer? I understand how people have done graph approach, but don't (yet) see what's wrong in mine.

→ Reply

bcoskun

5 years ago, # ^ |

← Rev. 2 →

I tried the same first, mine was failing with:

→ Reply

mraron

5 years ago, # |

How to solve F? I had an idea with Dijkstra and then greedy on the shortest path DAG but it's WA on test 10.

→ Reply

Alpha_Q

5 years ago, # ^ |

Did you sort the DAG adjacency lists by the lexicographical order of numbers or by value? The latter is wrong.

→ Reply

mraron

5 years ago, # ^ |

Oh crap, you're right I sorted by value xD Thanks!

→ Reply

lessmeaning

5 years ago, # ^ |

I thought about fast Dijkstra with smth like trie and overloading comparator in set using this trie and binary jumps on it (LCA). But don't have enough time to finish idea and implement

→ Reply

fmota

5 years ago, # ^ |

← Rev. 2 →

I did it, but WA62

UPD: It works, I have made a silly bug

→ Reply

5 years ago, # ^ |

Store numbers in trie lca can be used to compare them.

→ Reply

SHZhang

5 years ago, # ^ |

← Rev. 2 →

If one simply 1) compute minimum number of digits for reaching each node using Dijkstra; and 2) sort adjacency lists by lexicographical order; and 3) perform a greedy DFS on the resulting graph, making sure that the number of digits used is always equal to the minimum, one will get WA on test 47. (https://mirror.codeforces.com/contest/1209/submission/60551210)

For example, if there existed an edge between node 1 and 2 with number 1, between 2 and 3 with number 2, and between 1 and 3 with number 11, this algorithm will choose 1->2->3, not 1->3.

→ Reply

kiyotaka

5 years ago, # ^ |

← Rev. 3 →

+39

First, let's add some fake nodes on every edge separating number written on it by its digits. For example for the edge AB with 123 on it you create two more nodes and connect them like A-1-F1-2-F2-3-B.

After that you can assume that you need to find the shortest path by the number of edges in this graph for each initial vertex, and choose the lexicographically smallest one among all paths with the smallest length, because numbers with bigger length in digits are like bigger). To do so you can run some sort of bfs.

Suppose that you want to maintain all classes of equal by value paths with length x. To add one more edge, you iterate over all nodes in current level of bfs and add an ordered pair of (current class of node, digit on edge to the node in the next level) to current possibilities of going further. After that you need to select the smallest pair lexicographically for each node in the next level and update your classes just like in a suffix array building in O(n log n).

→ Reply

flashmt

5 years ago, # ^ |

+18

If you traverse the edges in ascending order (all 0 edges then all 1 edges and so on) then you only need to care about the first time you visit a node (basically normal BFS).

→ Reply

kiyotaka

5 years ago, # ^ |

← Rev. 2 →

+18

Heh, seems that you got your point~ It's so simple and accurate idea. But at least the suffix array bfs sounds way more cooler)

→ Reply

Holidin

5 years ago, # ^ |

← Rev. 2 →

+10

I'am not sure, but it doesn't seem quite true. If there are two vertex with the same path to them, 0-edge from the second of them is preferable to us than 1-edge from the first, but we will consider them in the reverse order.

→ Reply

flashmt

5 years ago, # ^ |

+10

Egor already mentioned this in his comment:

Suppose that you want to maintain all classes of equal by value paths with length x.

In normal BFS, you pop one node at a time and find new nodes by going from the node you just popped. For this problem, you will have to tweak it such that you will pop all nodes with same distance at a time. You can check my implementation here 60576572.

→ Reply

Holidin

5 years ago, # ^ |

Thanks, I understood, considering the component really fixes it.

→ Reply

roll_no_1

5 years ago, # ^ |

Hi. I saw your code and for the graph like this:

your code would generate a graph like this one:

whereas my code was trying to do something like this:

but it's getting WA. Can you please tell why we cannot reuse existing vertices?

→ Reply

Anadi

5 years ago, # ^ |

I used one vertex multiple times and got accepted.

→ Reply

roll_no_1

5 years ago, # ^ |

Thanks. Then there might be something wrong with my implementation. I'll try to see what's wrong with it.

→ Reply

abhishek945

5 years ago, # |

← Rev. 2 →

-15

[DELETED]

→ Reply

abhishek945

5 years ago, # |

← Rev. 2 →

-14

[DELETED]

→ Reply

nihal_47

5 years ago, # |

-9

Can anyone tell me why the codeforces generate different output for problem C ? It is continuously generating wrong output for pretest 1 which is the given testcase. I tested my code on my local and every online IDE I could find and it was generating same correct output . I request to rejudge my problem C solution . Due to this I ended up submitting my code 4 times which would deduct so many points of mine . It is just unfair as hell . If you want I will post my code you can check for yourself.

→ Reply

VadymKa

5 years ago, # ^ |

UB.

→ Reply

mraron

5 years ago, # ^ |

+11

You should test it in custom invocation tab.

→ Reply

nihal_47

5 years ago, # ^ |

I tested my code in custom invocation tab and its generating wrong output same as before . I tested my code multiple times on online ide and my local machine and its giving correct output. What should I do in this case?

→ Reply

yeputons

5 years ago, # ^ |

Run it locally under Valgrind/Memory Sanitizer/Address Sanitizer/UB Sanitizer. Alternatively, use custom invocation with "Clang++17 Diagnostics".

Also, proofread the code to make sure it does not have undefined behavior (which is typically the reason behind different behavior on different machines).

→ Reply

nihal_47

5 years ago, # ^ |

seems like it was my fault after all . there was a bug in my code where I was trying to access negative index . But it would have been nicer if was my local machine also gave same output as codeforces.

→ Reply

mango_lassi

5 years ago, # |

+95

Bad difficulty distribution again :/ 141 people solved F, while G2 and H were only solved by 5 people each. Problems A-G1 were relatively easy too, so I'm very surprised four LGM-level testers didn't recognize the far-too-high difficulty jump.

Also, G1 gives way too many points for how easy it is. More people solved it than E1, E2 or F, yet it gave more points than E1 and the same amount as E2. Additionally, since it was so much easier than F, the optimal strategy would have been to solve it before writing F. I think this trend of easy subtasks with inflated scores needs to stop, if not getting rid of subtasks altogether.

→ Reply

5 years ago, # ^ |

+21

Agreed, my code for E2 took like an 30-40 minutes of coding+debugging, while I needed <10mins to read, code & submit G1. And I didn't even read G1 until quite late, because I expected it to be more like G-level problem

→ Reply

flashmt

5 years ago, # ^ |

+36

E1 is fine because I can optimize its code for E2. G1 however should not exist.

→ Reply

5 years ago, # ^ |

-10

I believe subtasks are good at differentiating people who 1) cannot solve neither E1 nor E2, 2) those who can solve only E1, 3) those who solve E1 and after an hour come up with a solution for E2, and 4) good programmers who solve E2 in the first place.

→ Reply

5 years ago, # ^ |

G1 took me longer to figure out than E1+E2. I looked at E2, "hmm if $$$N=M$$$ then just subset DP in $$$O(4^N)$$$ and seems like I can sort the columns and take top $$$M$$$", then I checked if the second observation holds, wrote a solution, submitted, done. F killed me, I barely submitted and I'm really not sure if it's going to pass systests.

→ Reply

adamant

5 years ago, # ^ |

+46

Very true, I don't see any point in these subtasks except for wasting participant's time on solving some partial cases of the problem. Yet for some reason they become more and more popular on codeforces. This has to stop.

→ Reply

5 years ago, # ^ |

+36

I would like to understand this topic more to make smart decisions in the future. Why don't you like subtasks?

any point in these subtasks

the goal was obviously to provide an easy problem for beginners and at the same time not waste much time of top participants who can just skip easy version. That's not necessarily true today in this particular contest but you clearly complain about subtasks in general. Right?

→ Reply

riadwaw

5 years ago, # ^ |

+30

I don't like subtasks in general because if part 2 is sufficiently hard, you have to write (usually quite boring) first part to get more optimal points on the problem.

It's less bad in contests where you only care about last submission time such as GCJ.

→ Reply

adamant

5 years ago, # ^ |

+63

To be honest, they simply irritate me in codeforces rounds. I usually don't like solving partial cases of the problem to earn few points as I don't see this points to be "fair".

Subtasks are acceptable in some long rounds (like codechef long) or rounds with really small amount of problems (like ioi and stuff). You have the time to investigate the problem and solving subtasks usually advance you to the solution of the bigger problem or, at least, of some bigger subtasks. In codeforces it's often not the case and when you solve smaller subtask, you basically have to start from scratch in solving harder one (at least, I feel it this way). And you don't have time to investigate the problem, you're under constant pressure of clocks going too fast and round being too short.

Subtasks might be used in codeforces rounds in some exceptional cases, but now it is hard to find recent div. 1 round without subtasks and I clearly don't like it.

→ Reply

Swistakk

5 years ago, # ^ |

+26

"Additionally, since it was so much easier than F, the optimal strategy would have been to solve it before writing F." — and what is wrong with that? Recommended strategy is solve problems in increasing number of points so of course you should try reading and solving G1 before F.

→ Reply

djq_cpp

5 years ago, # ^ |

← Rev. 4 →

+23

And G1 makes it kind of 'unworth' solving G2, as it's much more difficult than F and deserves more points. QwQ

By the way, it leads to a result that solving H offers 4000 points while solving G only results in 2250. Just look at the scoreboard: ABCDEFG1H always ahead of ABCDEFG.

UPD: The problems themselves are quite awesome, though. Just hope a better score distribution.

→ Reply

Implict

5 years ago, # |

How to solve C？ just DFS? i trid,WA on pertest 4，im so weak...

→ Reply

hitch

5 years ago, # ^ |

I'm not sure but maybe finding the longest non-decreasing subsequence and marking all elements in it as 1 and if the rest of the elements aren't in sorted order there's no solution otherwise mark others as 2.

→ Reply

BledDest

5 years ago, # |

Is there an easier way to solve G2 than maintaining 2-edge-connected components?

By the way, very nice problemset! C was really cool.

→ Reply

5 years ago, # ^ |

← Rev. 2 →

-6

Create a sequence X with zeros. For every set of positions of the same value, for the segment between first and last occurrence add +1 in X. Then, we're looking for minima in X and between every two consecutive minima: a number that occurs most times. If for first occurrence of a value you store the number of occurrences of this value then the whole thing can be done with a segment tree.

Marcin_smu did it easier, without any interval operations. I don't know how though.

my code

#include <bits/stdc++.h>
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

struct Node {
	int small, lazy;
	int max_pref, between, max_suf, any_max;
	void merge(Node& L, Node& R) {
		assert(lazy == 0);
		any_max = max(L.any_max, R.any_max);
		if(L.small == R.small) {
			max_pref = L.max_pref;
			between = L.between + max(L.max_suf, R.max_pref) + R.between;
			max_suf = R.max_suf;
		}
		else if(L.small < R.small) {
			max_pref = L.max_pref;
			between = L.between;
			max_suf = max(L.max_suf, R.any_max);
		}
		else { // L.small > R.small
			max_suf = R.max_suf;
			between = R.between;
			max_pref = max(L.any_max, R.max_pref);
		}
		small = min(L.small, R.small);
	}
	void increase(int by) {
		small += by;
		lazy += by;
	}
	void set(int x) {
		// I am leaf
		max_pref = 0;
		between = 0;
		max_suf = x;
		any_max = x;
	}
};
vector<Node> tree;
int BASE;
const int SET = -1, ADD = -2;
void rec(int id, int low, int high, int q_low, int q_high, int type, int x) {
	if(high < q_low || q_high < low) {
		return;
	}
	if(q_low <= low && high <= q_high) {
		if(type == SET) {
			debug() << "set" imie(id) imie(x);
			assert(low == high); // leaf
			tree[id].set(x);
		}
		else if(type == ADD) {
			tree[id].increase(x);
			debug() << "increase" imie(id) imie(x);
		}
		else {
			assert(false); // unknown type
		}
		return;
	}
	for(int c : {2 * id, 2 * id + 1}) {
		tree[c].increase(tree[id].lazy);
	}
	tree[id].lazy = 0;
	int last_left = (low + high) / 2;
	rec(2 * id, low, last_left, q_low, q_high, type, x);
	rec(2 * id + 1, last_left + 1, high, q_low, q_high, type, x);
	tree[id].merge(tree[2*id], tree[2*id+1]);
}

const int nax = 2e5 + 5;
set<int> pos[nax]; // positinos with this value

void turn_off(int value) {
	if(!pos[value].empty()) {
		int L = *pos[value].begin();
		int R = *pos[value].rbegin();
		if(L < R) {
			debug() << "-1 " imie(L + 1) imie(R);
			rec(1, 0, BASE - 1, L + 1, R, ADD, -1);
		}
		debug() << "SET" imie(L) imie(0);
		rec(1, 0, BASE - 1, L, L, SET, 0);
	}
}
void turn_on(int value) {
	if(!pos[value].empty()) {
		int L = *pos[value].begin();
		int R = *pos[value].rbegin();
		if(L < R) {
			debug() << "+1 " imie(L + 1) imie(R);
			rec(1, 0, BASE - 1, L + 1, R, ADD, +1);
		}
		debug() << "SET" imie(L) << pos[value].size();
		rec(1, 0, BASE - 1, L, L, SET, pos[value].size());
	}
}
	
void add(int i, int value) {
	debug();
	debug() << "add" imie(i) imie(value);
	turn_off(value);
	pos[value].insert(i);
	turn_on(value);
}
void rem(int i, int value) {
	turn_off(value);
	pos[value].erase(i);
	turn_on(value);
}


int main() {
	int n, q;
	scanf("%d%d", &n, &q);
	BASE = 1;
	while(BASE < n) {
		BASE *= 2;
	}
	tree.resize(2 * BASE);
	for(int i = 0; i < 2 * BASE; ++i) {
		tree[i].small = 4 * n;
	}
	vector<int> a(n);
	for(int i = 0; i < n; ++i) {
		scanf("%d", &a[i]);
		add(i, a[i]);
	}
	for(int tt = 0; tt <= q; ++tt) {
		if(tt != 0) {
			int i, x;
			scanf("%d%d", &i, &x);
			--i;
			rem(i, a[i]);
			a[i] = x;
			add(i, a[i]);
			
		}
		debug() << imie(tree[1].max_pref) imie(tree[1].between) imie(tree[1].max_suf) imie(tree[1].any_max);
		printf("%d\n", n - (tree[1].max_pref + tree[1].between + tree[1].max_suf));
	}
	debug() << imie(a);
}

→ Reply

ww117755

5 years ago, # |

-11

hahaha

→ Reply

qwertyy123321

5 years ago, # |

+14

Is G1 simply merging the intervals?

→ Reply

ujjwalrox98

5 years ago, # ^ |

A DSU based implementation of G1,
https://mirror.codeforces.com/blog/entry/69791?#comment-542689

→ Reply

antontrygubO_o

5 years ago, # |

+221

→ Reply

5 years ago, # ^ |

← Rev. 2 →

-19

~~This meme suggests that it was good to have subtasks in E and G. Was that intended? ;p~~ (I messed up)

The goal of subtasks for E and G was to make the qualification (for the event) nice and without difficulty gaps. I agree that G1 should be lower-scored or non-existing, sorry about that. I don't think there was any tester that solved all problems to find the difficulty gap between F and G. I asked some of my friends to test G or H, and other testers mainly solved easier problems. There just aren't usually strong people that have enough time to test everything :( and this contest was kind of rushed so we didn't have time for an editorial, sorry for that too.

→ Reply

5 years ago, # ^ |

← Rev. 3 →

+24

You can estimate difficulty by explaining solutions to testers after they've tried all problems they can and letting them give input based on that. When I tested 580, I gave input based on my intuition even for problems I couldn't solve.

This meme suggests that it was good to have subtasks in E and G.

Lurk more on /b/. The usual template is that the guy that gets thrown out of the window offers an obviously good or asked for but not really tried idea while the other two propose stuff nobody asked for or ideas that were tried but didn't work (not bad per se, but considered worse by the author). Example. I'm not counting ironic meme and antimeme variations.

→ Reply

5 years ago, # ^ |

+23

Yup, I agree it needs to be done more often. But here G was quite easy to come up with a solution and only hard to implement. We still realized that it's hard and gave half more points than for F. That's like a jump from 2000 to 3000 points.

→ Reply

5 years ago, # ^ |

Sure. I don't mind the difficulties, G2 probably should have had a greater portion of G's points but it's not a big deal, at least it made difficulty jumps less steep.

→ Reply

5 years ago, # ^ |

-13

Actually, I change my mind. G1 should not be lower-scored. It isn't easier than D and for sure not much easier (enough to make an issue out of it). Obviously, G2 should get more points.

→ Reply

chemthan

5 years ago, # |

← Rev. 3 →

Who suggest subtask for G? Such thing is bullshit. Looking at scoreboard, G2 < F LOL while > 100 people solve F, what is for G2?

→ Reply

5 years ago, # ^ |

+32

I was one of people that agreed for that subtask and explained a reason above. Indeed, the scoring was bad though.

→ Reply

apostoldaniel854

5 years ago, # |

+44

Could you let us see other participants' solutions?

→ Reply

WATATATATATATATA

5 years ago, # |

+22

Codes still closed , reason ?

→ Reply

DC-HITMAN

5 years ago, # |

Still not able to see the test cases

→ Reply

Endagorion

5 years ago, # |

← Rev. 2 →

+17

Low-effort screencast

→ Reply

atlasworld

5 years ago, # ^ |

can't see video.

→ Reply

Endagorion

5 years ago, # ^ |

It is still processing, also the link was wrong in the first edit.

→ Reply

https://mirror.codeforces.com/contest/1209/submission/60576721

5 years ago, # ^ |

Yay, now I can watch you fail F!

→ Reply

Endagorion

5 years ago, # ^ |

+16

Knock yourself out.

→ Reply

Rafaaaaaaaaaaaam

5 years ago, # |

-17

Really good problem set.

→ Reply

mango_lassi

5 years ago, # |

The announcement of the Dasha Code Championship says this about the first round:

The round will be rated, open to all members of the Codeforces community. Top 30 competitors will receive official Dasha t-shirts!

While this blog states

There are Dasha t-shirts for top 30 competitors (not counting later-to-be onsite finalists).

Which of these is correct? Will the top 30 contestants who choose not to attend the onsite-event receive shirts, or will the shirts be given to the top 30 contestants, regardless of whether they participate in the onsite?

→ Reply

swapnilr

5 years ago, # |

How to get a tight upper bound for the simulation in problem B? Also, is there any other approach other than simulation?

→ Reply

realcomplex

5 years ago, # |

Can anyone hack my randomized solution for E1?

→ Reply

John_Cena

5 years ago, # |

← Rev. 2 →

svf

→ Reply

Sudhanshu_Kumar

5 years ago, # ^ |

← Rev. 2 →

→ Reply

webmaster

5 years ago, # |

← Rev. 4 →

+23

G2 accepted by $$$O(m\cdot n^\frac{2}{3})$$$ (sqrt decomposition) and SIMD optimizations of GCC: 60577013

→ Reply

GyojunYoun

5 years ago, # ^ |

What a beautiful time complexity XD

→ Reply

18_Pranjul

5 years ago, # |

First three were easy ones. Naive implementation required only :)

→ Reply

Wild_Hamster

5 years ago, # |

+47

I was debug-submitting my solution for F with incorrect idea and got AC. Although it should have TL and WA.

Hello to problemsetters and testers.

Here is idea of INCORRECT solution:

Let's launch Dijkstra from 1, where weight is equal to the length of value of the path and also build tree of shortest paths simultaneously and support online LCA on it. So now we will update shortest path for vertice $$$to$$$ if we go from vertice $$$v$$$ if length of value of the path is smaller or if length of value of the path is equal and prefix of some length of path from $$$LCA(v, to)$$$ to $$$v$$$ is smaller than prefix of some length of path from $$$LCA(v, to)$$$ to $$$to$$$. In debug submit prefix length is equal to 500 edges. It's possible to find the test with TL and WA.

I wonder why there are no test when there are 2 paths from 1 to $$$v$$$ with same lengths and with LCP of $$$O(n)$$$ length. For me it seems like obvious test.

→ Reply

subash23

5 years ago, # |

Can anyone help me with G1?

→ Reply

John_Cena

5 years ago, # ^ |

-27

NO!! become purple first

→ Reply

subash23

5 years ago, # ^ |

Thanks bro

→ Reply

ujjwalrox98

5 years ago, # ^ |

Check out this explanation using DSU, https://mirror.codeforces.com/blog/entry/69791?#comment-542689

→ Reply

Stecher

5 years ago, # |

-15

Errichto Is there any way to solve problem E1/E2 by max flow?

→ Reply

5 years ago, # ^ |

I'm not aware of any and I didn't think about it. The only thing I did there was to write some randomized approach to break tests.

→ Reply

tokitsukaze

5 years ago, # |

I tried to solve E2 using randomization, and finally I got AC :3

60578430

→ Reply

__Apocalypse__

5 years ago, # |

Could someone help me figure out whats wrong in my solution 60578600. Basic idea was to maintain 2 vectors one and two and both satisfy the condition of maintaining elements in increasing order, at some point of time if I can't place in the 1st array I try to relocate elements by popping from the first and moving into the second until I find a suitable place. If at some point I am not able to do the above I report answer as NO.

→ Reply

anupamshah_

5 years ago, # |

Any proof of D ?

→ Reply

IslamOmar

5 years ago, # |

← Rev. 2 →

Errichto How to choose the upper limit for time in problem B? if they have periods T1, T2,... they would repeat after LCM of T1,T2, ... ,but with a shift I don't know a formula for that!!

I see 1000 would pass the test.

→ Reply

5 years ago, # |

← Rev. 2 →

+20

I am writing this post to say a thank you to Errichto and others who helped him for this contest. I believe preparing 10 problems in a short amount of time is a tough task, and I believe they did a great job . We should be thankful to Codeforces and everyone who made this happen.

I am 31 years old and decided to start practicing competitive programming problems again after being inactive in some years. During the last 3 months, I learned a lot from great problems, and I am always glad to have the chance to practice in such a wonderful platform, i.e. Codeforces.

I am really surprised why some (even some red coders which I suppose to behave more maturely based on their experience in contests) complain about some small things such as 250 points difference between problems G2 and F. In some cases, they question everything, and posts are getting more aggressive. This is not what we expect from this wonderful community.

→ Reply

Ahmed_Nasr

5 years ago, # |

+22

When will the tutorial be published ?

→ Reply

FieryPhoenix

5 years ago, # ^ |

← Rev. 3 →

It is out now! Hope you enjoyed the contest!

Editorial

→ Reply

Roach00

5 years ago, # |

In problem D , How to get hint from the problem that dsu will be used in it ?

→ Reply