As an experiment the Educational Codeforces Round 33 will be rated for Div. 2. ×

Recent actions

What if someone solved a problem after 1 minute of the server problem and one after 29 minutes ? Are they going to get the same score?

Think about it this way. For your condition tu hold, the value n must within the last K positions. And you can choose the following values in ways, where is length of the suffix starting in value n. Then you have to multiply by the number of good permutations of size . That is, . This is exactly the same as choosing a cycle for element n of size at most K, and then multiplying by the number of good permutations for the remaining elements.

I'm not sure if I understood what you mean by counter test. It's true that the permutation you show should be counted as good for the problem statement, but it does not comply with the condition you mentioned.

That's right. but those could be very better. codeforces is a good and popular site as a result anyone have high expectations.

I hope codeforces be better in the future like always! :)

Wonderful explanation !! Thanks a lot :)

Some Div.2 solutions using regular expressions (in Perl): A32278803, D32280926.

How many participants from this round will be chosen to the final?

Thanks for this but i dont quite understand how the graph is being made. Can you please explain for this input

2
abc

xyz

Thanks! :') Update: I've understood thanks!

I wonder how many contestants solved this problem without OEIS.

I have given up on the contest when there was more than an hour left and almost got to top 100. Suspicious.

Thanks

although there where a lot of technical issues and despite that i spend more time reloading pages than the time i spend on reading problems, it was one of the greatest contests i ever participated in,thank you for your efforts it was totally worth it to participate even though it wasn't rated in the end.

No..Because occurence of k is more than occurence of kas and kad.

In Div1C
I needed to calculate number of permutations p1, p2, ..., pn satisfying .
On Oeis it said that this is equal to the number of permutations where all cycles have size less than or equal to K.
I tried proving both these conditions are equivalent but found a

Counter Test


Does anyone know why these two set of permutations have equal size?

if(rank==good)
    cf="UNRATED";
else
    cf="RATED";

To solve Div1 C, Div2 E

Let's calculate two functions:

dp[i] — How many [i] permutations exists, where last element is i and will return correct maximal value.

dpsum[i] — How many [i] permutations exists, where element i is in one of the last k positions and algorithm returns correct maximal value.

Then we can calculate these functions in linear time:

To calculate dp[i] we simply append i to the end of all the [i-1] permutations, where i - 1 is located in one of the last k positions and algorithm will return correct maximum value.

dp[i] = dpsum[i - 1]

To calculate dpsum[i] we must remove all permutations, where maximum value will be located outside the last k elements of permutation from dpsum[i - 1]. Then append new element to the end of permutation, it must be less than previous maximum value. So multiplying by (i - 1) we add this new element and increase all larger, equal permutation element values by one, so we get [i] permutations, where i is located in range [i - k + 1, i - 1]. Lastly, we must append all permutations which have maximal value i in the last position of [i] permutation, we calculated it in dp[i].

Then we can calculate the number of all good permutations, where correct maximum value is returned by algorithm.

Lets fix position i, where maximum value n will be located. Then first i element prefix of permutation must return correct maximal value and maximal element is in the last position of permutation formed by prefix, so we use dp[i]. We choose order of last n - i elements in (n - i)! ways. Suffix of last (n - i) elements forms a permutation.

Then we must merge these two permutations together by merging all elements except maximal n together. This can be done in ways.

Then the number of bad permutation is count of all [n] permutations minus good permutation count;

answer = n! - good_perm_cnt

Wut, noo, now I can't make round 446 :(

Created or updated the text

I misunderstood the statement and tried solving a slightly different problem-

On visiting a vertex the second time, any integer between [last_visit_time, i) can be written on that vertex.

Rated round:

Unrated round:

You could have seen in the explanation for example 1 they give 1 -> 1 -> 2 as a possible solution.

Actually I had to make a choice : 1) write a lot of true and bad things about the situation, 2) show anger and protest subtly.

Is this that difficult to see that yourself :)

Or you can just not visit the site, instead of unregistering the account altogether. As for receiving mails regarding contest announcements, you can just unsubscribe them. Is this idea that difficult to come up with?

Let's find dp[n]. Obviously, you can place the number n only in the last k spots, otherwise you would have more then k numbers smaller then n after n. Lets say you place number n at position i (so you have i numbers, then n, then n-i-1 numbers) (n-k<=i<=n-1). The first i numbers also have to respect the condition (of no k decreasing consecutive numbers), so there are dp[i] ways of arranging them. Also, there are C(n-1,i) number of ways of choosing the first i numbers out of the n-1 other numbers. We can arrange the last n-i-1 numbers in any way, since n will be bigger then all of them, so there are (n-i-1)! ways. Final formula:

dp[n]=sum(dp[i]*C(n-1,i)*(n-i-1)!)=sum(dp[i]*(n-1)!/i!)=(n-1)!*sum(dp[i]/i!), where i is from n-k to n-1

suppose if the set is ab, ba then i can construct the string abba, in which all the substrings in the set occurs once and all occus exactly same amount of time. Also if it is kas and kad then kaskad is a good string right ?

My story on problem A:

  1. Thought one couldn't stay on one vertex twice.

  2. Got WA

  3. An announcement said something like "1->1->1 is invalid because of t_2 can't be equal to 1". Thought it meant "because you can't stay on one vertex twice".

  4. Never questioned my understanding, found that I couldn't pp, and gave up.

i got a notif that its undated :( Please make it undated but not unrated ;_;

On a more serious note, how to unregister my account? I don't wanna come here anymore...

it hurts when you expect a positive rating and the round ends being un-rated.

Actually it was a good contest except the bad gateway problem. Problem statements very fairly clear and some hacks are always expected in div2A.

Can you please explain this dp? I struggled for the whole contest to find this.

I think your problem might also have overlap issues. Consider the step when n = 10 and k = 1. For the permutation {1,2,4,3,5,6,10,7,8,9} and a=3 your solution would consider false_max=5, whereas the false_max should've clearly been 4.

Indeed, I forgot to mention that as well.

Yeah, you also need to make sure there are no cycles; as an example, the answer for

2 ab ba

is NO

and the answer for

1 aa

is also NO.

Codeforces became one of the most searched today websites on websitedown.info!

I will be expert if this is rated. pls........

Construct a directed forest as follows. Nodes are letters. If one letter right after another in one of the words, then there is an edge from the first letter to the second one. There must be as most one outgoing edge and one ingoing edge on every node, otherwise answer is NO.

Tricky thing: some words have only one letter in it, one should care about that.

Once you have a valid forest, just print the letters in the order given by the forest.

omg. Thanks. sad ;/

Here's how I did it (With the same assumptions as you did): - Put in all the strings in a set S. - If any string has a repeating character, print NO(since this character will have more counts than the entire string). - For every character c in the alphabet, do the following: Make a set of all strings that contain this letter, say T, and while the size of this set is larger than 1, pick two strings from this set, merge them, and insert result in the set S. (Remove the original strings from S and T) If it is not possible to merge any two strings, then print NO (because the final answer has any character appearing atmost once.) To merge any two strings, check the prefix and suffix from c's position in the two strings. - Finally, you have only disjoint strings remaining in the set S. Concatenate them lexicographically and do a final check for repeating characters.

Construct from strings graph symb -  > nextsymb. This graph must be:

1) uncycled;
2) from each vertex there must be at most one edge;
3) to each vertex there must be at most one edge.

So from that graph you must iterate over vertexes that have no one edge points to them and create answer.

Example:

ab
bc
cd
da
Answer is NO since graph a->b->c->d->a is cycled.

kas
kad
Answer is NO since from a there are two edges to s and to d.

Better luck next time!

Try: 2 ab ba

How to solve DIV2 D ?

sm1 hold me, captain obvious is striking so hard

I was wrong, i thought ans for 3 aa bb cc would be aabbcc. but the ans is no.

Hmm okay, provided that they ended up seeing this long comment and figure out my misunderstanding... :< Anyway, thanks, just for having a nice response ;)

  1. I don't know why but i cant see round #445 in the contest page.
  2. System Tests have still not started. Do they usually take this much time or are the setters trying to figure out whether to make the round rated or unrated and if rated then how

How the initial strings look like?

Well, some will find it useful anyway

For example: n = 5, k = 1 You will count this permutation twice: 2 1 4 3 5

I do not care if this contest is rated or unrated. I only wish discovery test case 4 for D.

UPDATE: Got AC with this case.

no

This idea was applied in csacademy round 37

Ouch... sorry then. Should I delete this for now?

such garbage these last 2 contests were. hopefully this is going to be unrated

Thanks for letting me know where I got my number wrong!

Yep, I did both of them but they were'nt very useful :(

Well i couldn't solve Div 2 D but here are some of the things that i had thought of during the contest. If someone has solved with similar assumptions then please help in how to construct a solution from here.

  1. final answer will contain each character once so length <=26
  2. if any of the input string and all its sub strings are disjoint from the other strings or their substrings then we don't have to worry about it and can simply append it to the answer.
  3. (The hard part and from here im blank) I need to find a way such that an input string joins at the either of the ends of another string or merges in the middle. final answer will be this string along with the disjoint strings appended.

Can anyone help me create a solution from here or if my assumptions are wrong then point em out please? Thanks :)

With all due respect that is very nice but he asked about Div1 C

Let's run the system test. For one I'd like to know if I messed up on div. 2 ABCD. For another, I really wanna upload my updated version for problem F just to see if I did it correctly lol

Either rated or unrated, the system test shall run lol

CF server trying return

Says the person who trolled everyone on cf discord that it was rated.

Evidence: https://snag.gy/c7Cj0g.jpg

Situation of the last two contests in Codeforces

Some of us have problem with the round being rated. Because if the server wasn't down, we could have submitted our code early. But as CF was down for approximately half an hour, we got huge penalties :( which will brutally decrease our rating. If we could submit codes just in time, our rating would not be this massacre. So please make the round unrated. :(

I would, but I don't precisely recall the exact contest. I could dig around the previous 100 contests, but that would be painful. I'll just leave my suggestion as is.

There was a solution in my room which checked a[0]+a[4]+a[5]==a[2]+a[3]+a[1]. I hacked it using 1 6 7 9 10 11. Several other hacks are possible.

"temp *= mod_fac(a + k, mod);"

its actually not (a+k)!, since in the first a numbers there must be no k consecutive decreasing values, otherwise you will stop at them and not reach the a+1th value.

to calculate this number, let dp[i] be the number of ways to permute first i numbers such that no k are increasing. dp[i]=(dp[i-1]/(i-1)!+dp[i-2]/(i-2)!+...+dp[i-k]/(i-k)!)*(i-1)! (i is from n-k to n-1)

New version:

171c518f4f0dc2472f1edfb119d6b2c78c439486

I wanna pass ABCD

yep! you are right!

Let's run the system test, if i passed the D the round should be rated.

I just realized that after posting my comment, too. I spent my last 10 minutes trying to Google about nCr % p, but some copy-paste can't save me though...

for who used sum/2 for checking ... 1 1 1 1 1 2

for sorting and then grouping (0,1,5) — (2,3,4) ... 0 1 3 4 7 7

solution will be a forest of linear trees

is there is a solution if a character occurs twice in a string?

I thought of the same thing (you're using the fact that X halves or stays the same at each step)? You can also do something like: "if (a[i] <= a[i + 1]) delete a[i + 1] and increase the coefficient of a[i] by 1" and you get a decreasing array, with some extra coefficients. Still not very useful though:(

one guy in my room checked d+e+f == c+d+e. Hacked.

implementation

Can you point which ones to me?

Lagforces servers be like

Well, they've done it for a few contests in the past and it seemed to meet most people's demands.

Hint : Will the result contain a character more than once ?

How to solve Div2-D (Div1-B) ?

It'd be nice to give hints before the complete solution.

What is the reason of this server break downs? Poor servers, DDOS or smth? Can anyone explain it?

All right, go rated

Many people checked sum/2. It get WA when sum is odd.

Oh wow what a coincidence, we posted the same wrong solution at the same time!

In my opinion, greedy algorithm can be a fine approach. I used an array (I'll name it A): element with index i is used to store the index of the room which was last visited in minute i. (if this room is visited again in the future, the value of this element is changed back to 0).

Then I did a linear check over all numbers in the notebook:

Assume that the number written in minute i is x. If there was a room which was last visited in minute x, we could assume that that room is visited again in minute i (it's the easiest way to handle without adding new rooms). Assign A[x] to A[i], then assign 0 to A[x]. Otherwise, since no room was last visited (until minute i) in minute x, the man must have enter a new room. Increase the room count by 1, and assign the index of the new room to A[i].

Hope this will help. And sorry if my expressions could be complex though...

nah, the rating inflation will be skyrocketing if that were the case.

yeap, sorry =(

In Russia we had this problem too. It was not because of terrible Internet but because of problems on codeforces

it was not bad really . problem were pretty clear and pretests were not too weak . i was busy coding div1 B for almost the whole contest so i didnt get that gateway error at all ! however hacking was almost impossible

That's a good idea. emmm....

Hacks for Div 2 a?

A 9gagger, I see you're a man of culture as well.

How do you solve problem E? I got WA on test case 15 with this formula so I want to know if the formula was wrong or if it was something in my code.

My attempt on E (Div 2.):

We will construct a permutation that has the following structure: Starting with a values, then place the value, namely false_max, that will be the answer of fast_max() procedure, then k values after that, then the rest of the number. Note that the first a + k + 1 elements in this array will be <= false_max. The number of choices can be decomposed into:

  1. Choose (a + k + 1) elements from the set of [1, 2, ..., n-1] -> the answer is combinations(n-1, a + k + 1)

  2. Place the maximum element, false_max, from the above step at array[a + 1].

  3. Re-arrange the remaining numbers of the chosen elements into (a + k) spaces -> the answer is (a + k)!

  4. Re-arrange the remaining not-chosen numbers into (n - a - k - 1) spaces -> the answer is (n - a - k - 1)!

That is for one a. a will be ranged from [0, n - k - 2]. Calculate the sum of all intermediate values gives the final answer.

Here is the pseudocode:


long long answer = 0; long long mod = 1000000009; for(int a = 0; a <= n - k - 2; a++) { long long temp = mod_fac(n - a - k - 1, mod); temp *= mod_fac(a + k, mod); temp %= mod; answer += temp * nCk(n - 1, a + k + 1, mod); answer %= mod; }

I got Wrong answer on pretest 15. Is there anything wrong with my solution, or just that my implementation is so poor that it can't handle the mod part?

1) Brute force it

2) Search for the first two columns on OEIS

3) Find a pattern

4) ???

5) Profit!

I hope they consider making it rated for those with positive rating gains and unrated for those who lose rating (as they've done in the past). This could satisfy everyone?

Edit: I don't understand why a reasonable suggestion is being downvoted.

How to solve E? f(1, x) can be computed in O(log2), I'm not sure it has anything to do with real solution, though. I tried some randomization stuff but couldn't pass pretests.

I was unable to hack in the last 6-7 minutes, but still, let's not make the round unrated. Even the last rated round was unrated. Looks like, system issues are becoming rather common, so this way, who know when we'll have an actual rated round. Please don't make it unrated.