Блог пользователя thanhchauns2

Solutions for April Fools Day Contest 2023 in one line (Collection)
Автор thanhchauns2, история, 20 месяцев назад, По-английски

Hi, I collected the solutions for the problems of April Fools Day Contest 2023. Before the official editorial being posted, we can discuss about the problems here.

P/s: The editorial was published.

1812A - Are You a Robot?

Solution

1812B - Was it Rated?

Solution

1812C - Digits

Solution

1812D - Trivial Conjecture

Solution

1812E - Not a Geometry Problem

Solution

1812F - Factorization

Solution

1812G - Colour Vision

Solution

1812H - Expected Twist

Solution

1812I - Mountain Climber

Solution

1812J - Unmysterious Language

Solution
  • Проголосовать: нравится
  • +28
  • Проголосовать: не нравится

»
20 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

After about 300 — 400 steps, a positive number will be decreased down to 1.

Where did you get those numbers from? the conjecture asks whether every positive integer will eventually get to 1 by applying the operation however many times you'd like.

The biggest answer allowed (103 digits) will take more than 3,000 operations to reach 1, but it might take millions, or never reach 1 (proving the conjecture false), which means that the [REDACTED] part must be pretty small, or the grader wouldn't be able to evaluate a very large submission definitively.

→ Ответить
  • »
    »
    20 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Here. Or I could remember the wrong number, I watched it a long time ago.

    → Ответить
    • »
      »
      »
      20 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I think it is around $$$350$$$:

      void solve(){
	int mx = 0;
	for (int n1 = 1; n1 < 100000; n1++){
		int steps = 0;
		for (int n = n1; n != 1; steps++){
			if (n & 1) n = 3 * n + 1;
			else n /= 2;
		}
		mx = max(mx, steps);
	}
	cout << mx << '\n';
}
      → Ответить
  • »
    »
    20 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I believe the grader can just simulate $$$10^5$$$ ish steps to check if an answer is valid or not. In testing, the best number I could find was around $$$2.5 \cdot 10^4$$$ steps by just randomly generating $$$1000$$$ digit numbers and running them. In any event, it is probably impossible to find a positive integer that could work on the given constraints, and if you could, you could probably write a paper on it!

    → Ответить