sevlll777's blog

Codeforces Round 1004 (Div. 1, Div. 2) Editorial
By sevlll777, 3 hours ago, translation, In English

Thanks for participating!

2067A - Adjacent Digit Sums

Tutorial
Submission

2067B - Two Large Bags

Tutorial
Submission

2067C - Devyatkino

Tutorial
Submission

2067D - Object Identification

Tutorial
Submission

2067E - White Magic

Tutorial
Submission

2067F - Bitwise Slides

Tutorial
Submission

2066D1 - Club of Young Aircraft Builders (easy version)

Tutorial
Submission

2066D2 - Club of Young Aircraft Builders (hard version)

Tutorial
Submission

2066E - Tropical Season

Tutorial
Submission

2066F - Curse

Tutorial
Submission
  • Vote: I like it
  • +56
  • Vote: I do not like it

»
3 hours ago, # |
  Vote: I like it +2 Vote: I do not like it

thank you for the quick editorial, questions were tricky.

I need to understand official approach, hoping to get some proofs of correctness

→ Reply
»
3 hours ago, # |
  Vote: I like it -8 Vote: I do not like it

good contest , bad contest

→ Reply
»
3 hours ago, # |
  Vote: I like it -6 Vote: I do not like it

The best contest i've ever particpated!

→ Reply
»
3 hours ago, # |
  Vote: I like it +9 Vote: I do not like it

please make editorial for problem D in English

→ Reply
»
3 hours ago, # |
← Rev. 4   Vote: I like it +7 Vote: I do not like it

How was it supposed to be deduced for A that 'n' is supposed to be a 'positive integer' only? The problem specified for 'n' to be an 'integer' which allows a larger set of valid pairs. More precisely for each currently accepted (x, y), (y, x) should also be a valid pair.

Or am I missing some detail?

→ Reply
  • »
    »
    3 hours ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    oh yeah, correct, it says integer

    → Reply
  • »
    »
    3 hours ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    There was an announcement stating that n is positive. Apart from that, there is nothing that says n should be positive.

    → Reply
    • »
      »
      »
      3 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      oh man ,

      many people who were solving it assuming negative and missed the announcement because they were looking at their notebook might have spent so much extra time.

      → Reply
    • »
      »
      »
      3 hours ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      Ok thanks, I fortunately read the announcement before submitting. It was just that the announcement seemed to imply that the fact was deducible from the problem statement itself, therefore I was confirming.

      → Reply
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

tricky but insteresting questions!

→ Reply
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

sevlll777 Problem D (Div2) or Problem A (Div1)'s Editorial is in Russian language only.. Please make it available in English !!

→ Reply
  • »
    »
    3 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is translated on Polygon. I guess some time is needed to pull it up from here, should be available soon

    → Reply
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Interesting and exciting.Love it!

→ Reply
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a problem in the interactor of Div. 1 A (Div. 2 D) Object Identification? This submission 305637703 passes the sample locally but gets WA 1.

→ Reply
  • »
    »
    3 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    we are investigating it

    → Reply
    • »
      »
      »
      3 hours ago, # ^ |
      ← Rev. 4   Vote: I like it +4 Vote: I do not like it

      I'd like to mention that I looked for format error for about 20 min due to this submission and the lack of interacting process for the sample.

      → Reply
»
3 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anybody explain why this doesnt work for A?

void solve(){
	ll x,y;
	cin >> x >> y;
	if(x<y){
		if(x==y-1) cout << "YES";
		else cout << "NO";
	}
	else{
		if(x%9==y%9-1) cout << "YES";
		else cout << "NO";
	}
}
→ Reply
  • »
    »
    3 hours ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    There will be cases where $$$y\pmod{9} = 0$$$ and your code would check if $$$x\pmod{9}=-1$$$, when it should be checking if $$$x\pmod{9} = 8$$$. You can replace your code with 

    void solve(){
	ll x,y;
	cin >> x >> y;
	if(x<y){
		if(x==y-1) cout << "YES\n";
		else cout << "NO\n";
	}
	else{
		if(x%9==(y%9+8)%9) cout << "YES\n";
		else cout << "NO\n";
	}
}

    and it should work. Also you aren't printing a new line, which you should.

    → Reply
  • »
    »
    70 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    x=1,y=2; test case is failling. Consider num=100,num+1=101 then x=1 and y=2

    → Reply
  • »
    »
    8 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    See you have a integer number n let say it consist ABCDEF where A,B..F are digits

    Thing about the two case:

    • Case 1: Where unit digit (here F belongs to [0,8]) n+1 make it belongs to [1,9] that mean the whole structure of number n would remains constant except the unit digit F so the sum would increase just by one x = A+B+C+D+E+F y = x + 1

    • Case 2: Where unit digit of n is 9 now n+1 will make unit digit 0 and carry 1 will be forward to E, again thing of two case E belongs to [0,8] or E == 9, if case 1 then simply it will add up 1 and stop other wise make digit E = 0 for n+1 and forward that carry to D.

    so you got a sum x for n, for n+1 you are going to get some zeroes in place contiguous 9 from unit place (let say k no of 0 replacing k 9's) and finally adding 1 to very first non 9 digit.

    so y = x- k.9 + 1

    clearly visible (x + 1- y) must be divisible by 9 by taking care that (...) is >= 0.

    That's it.... I hope it is helpful and easy to understand pardon my bad English

    → Reply
»
3 hours ago, # |
  Vote: I like it +46 Vote: I do not like it

Here's a combinatorial solution for D1.

Let the number of planes launched from $$$i^{\text{th}}$$$ floor be $$$u_i$$$, note that $$$u_{n} = c$$$.

Now corresponding to this case in the original dp recursion solution we get the term $$$\prod_{i=1}^{n-1} \binom{c}{u_i}$$$

So the final answer is just sum over this expresion as $$$u_i$$$ ranges over all possible values constrained by $$$0\le u_i \le c$$$ and $$$\sum_{i=1}^{n-1} u_i = m-c$$$.

Now this is equivalent to a counting problem where we have $$$c(n-1)$$$ distinct objects divided into $$$n-1$$$ types with $$$c$$$ objects of every type and we want to choose a total of $$$m-c$$$ objects. The above expression occurs when we count by first deciding number of objects of each type and then choosing the objects per type. Instead we can directly choose the $$$m-c$$$ objects.

Hence the answer is

$$$\displaystyle\binom{c(n-1)}{m-c}$$$
→ Reply
»
2 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

B was a really good problem. I wasn't able to submit the right code in time, however I still enjoyed taking my time solving the problem.

→ Reply
»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

its awsome, Like your previous competitions, this one also had a lot of mathematics!

→ Reply
»
2 hours ago, # |
  Vote: I like it +5 Vote: I do not like it

div1A >> div1B

→ Reply
»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Rating roll back when ? I want to be expert in problem solving

→ Reply
»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

just curious, who or what is Devyatkino, and how is it related to the 2067C problem?

→ Reply
»
2 hours ago, # |
  Vote: I like it +4 Vote: I do not like it

Problem D was really interesting theory-wise, pretty cool for an interactive problem to actually be accessible for regular users rather than being 2300+ rated

→ Reply
»
62 minutes ago, # |
  Vote: I like it +6 Vote: I do not like it

A YouTube solution got leaked in the last 10 minutes of Problem E. I don't know much of Div. 1 but in Div. 2 more than 10 people in top 20 have been cheated having the same solution and it might get worse lower down in the standings. Some of the solutions are with comments and exactly same, I don't know how they escaped plagiarism but something needs to be done about these cheaters or else the fun of competitive programming will end soon.

→ Reply
  • »
    »
    24 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah completely agreed, Here I try my best to increase my rating and on other side my friend has higher rating because he is cheating.

    → Reply
»
31 minute(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In C, if n = 6, answer is actually 9, not 8, right?

→ Reply
»
17 minutes ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Solved ABC and had some idea about D. The problems were interesting and the observations were not very obvious. Overall a nice contest.

→ Reply