Auto comment: topic has been updated by Acko (previous revision, new revision, compare).

plz check. the register doesn't work.

[Deleted]

why I am able to register in Div1 also ?

is it rated?

ping me if by any chance anybody is interested in teaming up with me
UPD: SORRY BUT I've ALREADY TEAMED UP

How many participants allowed in a team?

Number of problems is secret?

Problems are not sorted by difficulty, right?

Is the order of the questions sorted by difficulty value? (Because this is the icpc rule, I am not sure about this.)

I have a couple of questions.

• What is native Codeforces ACM-ICPC team contest rules? I haven't heard of this rule. I'm particularly concerned about whether it is allowed to copy-paste my library.

• Team members can work on their own computers. Does this mean we can code simultaneously? Or we still shouldn't use multiple computers at the same time?

Get the book "BUGS in Writing: A Guide to Debugging Your Prose", statements are unintuitive (e.g in H) and hard to understand. Also consider adding more formal definition for statements.

I didn't expect 14 questions.

Why the TL for J is so tight?

These are what we sent and received for problem E during the contest:

The input is a floating number while we need to do binary decisions. Are the judge solutions accurate?

Yes

As nothing is mentioned about the number of digits of the input, we believe there exists a case where the judge solution is incorrect.

No comments

How many digits after the decimal point can the input values have?

4 decimal places.

The planned building area is represented as a rectangle with sides width and height. Is it always located at [0, width] \times [0, height]?

Yes

What is the constraints of N? If the only constraint is N Q <= 10^6, then there would be 10^6 * 40 points in the input.

N <= 150000

What do you think, community? I strongly hope that this kind of problem preparation be gone.

How to solve E: guess the statement.

Why does E have such a small amount of constraints? I don't see anything in the statement that guarantees that the input file is smaller than $$$10^{10^{100}}$$$ bytes.

How to solve div2-M ?

I surely misunderstand E but cannot get what I'm missing.

How I understand E: Get the sum of the whole areas of the polygons that intersect with the given circle. But this is too easy, right?

I also don't get what that "planned building area rectangle" has to do with the problem.

Can someone point out what I'm missing here?

J — amazing time limit :)

Wasn't J can be solved by this sequence?

I got WA on test case 3? Can anyone tell me why my solution is wrong on n=10000?

Edit: Got AC when changed precomputation from 1e7 to 1e6.

Problem F.

Well that was awful.

1. Statements are long and unreadable in places. You don't give accurate limitations.

2. 15 problems for 3 hours with this kind of writing?

3. I believe there are some interesting problems underneath but you buried them under (at least) 8 problems "write obvious solution in 200 lines of code"

4. (That's my own butthurt, but) What's the point of giving 5e5 tests in J? What were you trying to cut out? Will the problem be worse with one test? Reading the input takes at least 0.3 sec with scanf wtf

I think the test cases for Problem B are weak . My wrong code was accepted it seems. Link to my submission --> https://mirror.codeforces.com/contest/1424/submission/94787727 Though it got accepted It fails on this test case which I thought

5 9

1 1 1

1 2 2

1 3 3

1 4 4

1 5 5

2 1 6

3 1 7

4 1 8

5 1 9

The answer must be -1 and my code gives the answer as 9 and still got accepted. Please correct me if I am wrong somewhere.

This should have been a 5 hour contest and not 3 hours.

Can someone explain how to do F?

in problem L, tests have T_i == 0...

How did you write validator for problem M ?

I passed M 10 minutes after the game, (it looks like 20 minutes, that's because the codeforces main station seems to be banned by GFW for 10 minutes and i cannot access during the period), If it is a rated contest, I would regret it for a long time...What a sad story...

A neat solution to J:

Think of the answer to query $$$n$$$ as the n-th coefficient in the following polynomial: (where $$$B$$$ is some large number, greater than $$$10^{18}$$$)

After ignoring high order terms, it will be $$$\frac{1}{(1-x)(1-x^2)(1-x^4)}$$$. This is equivalent to complete knapsack problem with item weights $$$1,2,4$$$. A little bit math shows that the n-th coefficient is just $$$\sum\limits_{i=0}^{\lfloor \frac n4\rfloor}\sum\limits_{j=0}^{\lfloor\frac{n-4i}{2}\rfloor}1 = (\lfloor \frac n2 \rfloor - \lfloor \frac n4 \rfloor + 1)(\lfloor \frac n4\rfloor + 1)$$$.

I could be wrong, but I think a lot of people had solutions accepted from problem B which should not have been accepted. The test cases were weak and new ones have been retrospectively added which would have resulted in failures.

Problem K (div1) / J (div2) was also very poor. The entire performance of the algorithm depended on reading the inputs fast enough. That is weak.

How to solve div2-B(valuable paper)? Thanks in advance:)

What's wrong with this test to M?

3 3
2 3 4
4 1 3
5 4 2

http://mirror.codeforces.com/contest/1424/submission/94795249 Could anyone please explain why this is giving TLE??

By when shall we expect the editorials Acko?

Sorry, I'm greedy, uphacks on B, C, M, and N weren't enough for me:

why there is no system testing?? Many group solve the question no B valuable paper using binary search but they actually got wrong ans in test case 21 that i think added after the contest. So if system testing is there then i think they might got why their logic get WA on test case 21. Please pay attention what i have said. Thank you.

The statement in M says: $$$1 \leq n, m \leq 10^6$$$. I looked through the tests and saw that all tests have $$$1 \leq n, m \leq 10^3$$$. Moreover I tried uphacking some solution with tests with $$$n, m = 1001$$$ (https://mirror.codeforces.com/contest/1423/hacks/669698) and it says "FAIL Integer parameter [name=rows] equals to 1001, violates the range [1, 1000]".

Why is that?

I did a weird constant optimization for J.

We can write $$$m_i$$$ as a binary string with length $$$L=60$$$. Let $$$M=8$$$ be the size of coefficient set. We can write a DP solution in $$$O(t \cdot L \cdot M)$$$. However, this approach TLEs.

I decided to divide the string with length $$$L$$$ into blocks of size $$$B$$$. We can precompute the DP transition matrix for all binary strings from $$$0$$$ to $$$2^B-1$$$ in $$$O(B \cdot 2^B \cdot M^3)$$$. Then, for each $$$t$$$ queries we can multiply $$$\lceil \frac{L}{B} \rceil$$$ matrices with the base case matrix in $$$O(\lceil \frac{L}{B} \rceil \cdot M^2)$$$ to get the answer.

Thus the final complexity is $$$O(B \cdot 2^B \cdot M^3 + t \cdot \lceil \frac{L}{B} \rceil \cdot M^2)$$$. Picking $$$B=12$$$ passes the testcases. Submission.

Problem M of Div 2

I wonder what "Unexpected verdict" means?

ps: I found it in Hacks.

thx

Shall we even expect editorials? Acko

How to solve Lonely Numbers — Div1 problem K — Div2 problem J

Editorial ??

Problem E has a lot of issues with hacks.

It's too easy to generate a hack, just print as many integers as you can. In fact, I hacked all but two solutions like this. Also, input validation is bad, it doesn't check whether polygons intersect. In fact, you can just print the same polygon as many times as you want. It's also kind of impossible to do within reasonable time.

My suggestion: remove all hacks, restore testcases to the official ones used for the BC finals, and disable hacks for this problem.

Can somebody tell me why are these two problems having this high rating difference in spite of them being the same problems :
PROBLEM1 -> 2200 rating
PROBLEM2 ->1600 rating
I literally used almost the same solution for both the problems

#include <bits/stdc++.h>
#define ar array 
using namespace std;
const int mxN =101 ;
int n,d[mxN];
vector<int>adj[mxN] ;
signed main() {
	cin >> n ;
	vector<string>s(n) ;
	for(int i=0;i<n;i++)
		cin >> s[i] ;
	for(int i=1;i<n;i++){
		int n1 = s[i-1].size(),n2=s[i].size(),i1=0 ;
		for(;i1<n1||i1<n2;i1++){
			if(i1>=n2&&i1<n1){
				cout << "Impossible" ;
				return 0 ;
			}else if(i1>=n1||i1>=n2)
				break ;
			if(s[i-1][i1]==s[i][i1])
				continue ;
			adj[s[i-1][i1]-'a'].push_back(s[i][i1]-'a') ;
			d[s[i][i1]-'a']++;
			break;
		}
	}	
	queue<int>qu ;
	string ans ;
	for(int i=0;i<26;i++)
		if(!d[i])
			qu.push(i);
	while(qu.size()){
		int u = qu.front() ;
		qu.pop() ;
		for(int x:adj[u]){
			--d[x] ;
			if(!d[x])
				qu.push(x)  ;
		}
		ans+=(char)(u+'a') ;
	}
	cout << (ans.size()==26?ans:"Impossible") ;
}

#include <bits/stdc++.h>
#define ar array 
using namespace std;
const int mxN =1e3+1 ;
int n,d[mxN],k;
vector<int>adj[mxN] ;
vector<string> a[mxN] ;
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >>k;
	for(int i=0,c;i<n;i++){
		cin >> c ;string s1;
		for(int j=0;j<k;j++){
			cin >> s1;a[c].push_back(s1) ;
		}
	}
	vector<string>s;
	for(int i=0;i<n;i++)
		for(int j=0;j<k;j++)
			s.push_back(a[i][j]);
	n*=k ;
	vector<bool>ok(26) ;
	int al=0 ;
	for(string x:s)
		for(char c:x){
			if(!ok[c-'a'])
				++al ,ok[c-'a']=1;
		}
	for(int i=1;i<n;i++){
		int n1 = s[i-1].size(),n2=s[i].size(),i1=0 ;
		for(;i1<n1||i1<n2;i1++){
			if(i1>=n2&&i1<n1){
				cout << "IMPOSSIBLE" ;
				return 0 ;
			}else if(i1>=n1||i1>=n2)
				break ;
			if(s[i-1][i1]==s[i][i1])
				continue ;
			adj[s[i-1][i1]-'a'].push_back(s[i][i1]-'a') ;
			d[s[i][i1]-'a']++;
			break;
		}
	}	
	queue<int>qu ;
	string ans ;
	for(int i=0;i<26;i++)
		if(!d[i] && ok[i])
			qu.push(i);
	while(qu.size()){
		int u = qu.front() ;
		qu.pop() ;
		for(int x:adj[u]){
			--d[x] ;
			if(!d[x])
				qu.push(x)  ;
		}
		ans+=(u+'a') ;
	}
	cout << (ans.size()==al?ans:"IMPOSSIBLE") ;
}

Auto comment: topic has been updated by Acko (previous revision, new revision, compare).

@Acko ： My team's name is "5times187" .

Can anyone give me a hint of how to optimize bitmask dp in Div 1 problem J ?

I tried the problem 1424G many times but its giving wrong and on 7th test case. Can anyone tell the idea behind the question or provide with a solution

Orz Itst pupiI and newbiegcz!

Can someone tell me why am I getting a TLE here https://mirror.codeforces.com/problemset/submission/1423/99648601