Editorial of MindCoding 2015 Test Round

10 - A+B

A+B is one of the most complex problems on this website due to its large variety of solutions.

C

    1 #include<stdio.h>
    2 
    3 int main(void) {
    4 	int a, b;
    5 	scanf("%d%d", &a, &b);
    6 	printf("%d", a + b);
    7 	return 0;
    8 }

C++

    1 #include<iostream>
    2 
    3 int main(void){
    4 	int a, b;
    5 	std::cin >> a >> b;
    6 	std::cout << a + b;
    7 	return 0;
    8 }

D

    1 import std.stdio;
    2 
    3 void main(){
    4     long a, b;
    5     readf("%d %d", &a, &b);
    6     writeln(a+b);
    7 }

Go

    1 package main
    2 import "fmt"
    3 
    4 func main() {
    5 	var a, b int
    6 	fmt.Scanf("%d%d", &a, &b)
    7 	fmt.Print(a + b)
    8 }

GolfScript
    1 ~+

Haskell

    1 import Control.Applicative
    2 
    3 main :: IO ()
    4 main = do
    5         [ a, b ] <- map read . words <$> getLine
    6         print (a + b :: Int)

Java

In Java, the class must be named prog.
    1 public class prog {
    2 	public static void main(final String[] args) {
    3 		java.util.Scanner scan = new java.util.Scanner(System.in);
    4 		System.out.println(scan.nextInt() + scan.nextInt());
    5 	}
    6 }

Oberon

    1 MODULE prog;
    2 
    3 IMPORT In, Out;
    4 
    5 VAR a, b : INTEGER;
    6 
    7 BEGIN
    8   In.Int(a);
    9   In.Int(b);
   10   Out.Int(a + b, 0);
   11   Out.Ln
   12 END prog.

OCaml

    1 let sum a b = a + b
    2 
    3 let _=
    4     Printf.printf "%i\n" ((Scanf.scanf "%i %i" sum))

Pascal

    1 var a,b:integer;
    2 begin
    3 read(a,b);
    4 write(a+b);
    5 end.

Perl

    1 #!/usr/bin/perl
    2 use v5.14;
    3 use warnings;
    4 
    5 my ($x, $y) = split ' ', <>;
    6 say $x + $y;

PHP

    1 <?php
    2 fscanf(STDIN, "%d %d\n", $a, $b);
    3 echo $a+$b . "\n";
    4 ?>

Python

    1 #!/usr/bin/python
    2 print sum(map(int, raw_input().split()))

Python3

    1 #!/usr/bin/python3
    2 print(sum(map(int, input().split())))

Ruby

    1 p gets.split(' ').map(&:to_i).inject 0, :+

Rust

    1 use std::io;
    2 
    3 fn main() {
    4     let mut input = String::new();
    5 
    6     let _ = io::stdin().read_line(&mut input);
    7 
    8     let mut sum: i64 = 0;
    9     for x in input.trim().split(" ").collect::<Vec<&str>>() {
   10         sum += match x.parse::<i64>() {
   11             Ok(val) => val,
   12             _       => 0,
   13         };
   14     }
   15 
   16     println!("{}", sum);
   17 }

SBCL

    1 (format t "~d" (+ (read) (read)))

250 - Frame

500 - Eggs

Solution by Alexandru Velea

Observatie

Aceasta problema este destul de cunoscuta de lumea care are experienta cu problemele de interviu. Am ales aceasta problema pentru a familiariza lumea cu acest tip de probleme si pentru a o face accesibila pentru implementare pe platforma Mindcoding.

Nu toate problemele de interviu pot fi implementate, deoarece multe dintre ele necesita restrictii legate de memorie. memorie O(1) sau O(N) iar acest lucru este destul de greu de controlat iau unele sunt pur si simplu prea populare.

Problema este o extindere a problemei clasice cu 2 oua si un bloc cu N etaje.

Rezolvare pentru problema restransa la ≤ 2 oua

Observatia #1

Daca avem un bloc de N etaje cu un singur ou raspunsul este maxim N - 1.
Suntem obligati sa aruncam oul de la fiecare etaj de la 1 … N - 1.
Daca am aruncat oul de la etajul N - 1, atunci stim ca rezultatul e N.

Observatia #2

Observatia 2 vine de la faptul ca avem la dispozitie 2 oua maxim.

Putem arunca cu primul ou pana se sparge iar mai apoi suntem nevoiti sa aruncam cu al doilea din 1 in 1 dupa cum am spus mai sus.

Astfel, daca alegem sa aruncam oul la pozitiile p[1], p[2], p[3], …, p[x - 1], p[x] si oul se sparge la p[x], atunci am facut x aruncari si trebuie sa aruncam primul ou de la etajul p[x - 1] + 1 si pana la etajul p[x] - 1 maxim.

Astfel, o sa mai facem (p[x] - 1) - (p[x - 1] + 1) + 1 = p[x] - p[x - 1] - 1 pasi cu primul ou + inca x pasi pana am spart cel de-al doilea ou.

Se poate observa ca functia noastra ar trebui sa fie aproximativ sqrt(n). Daca luam fiecare diferenta egala problema se reduce la n / x + x = minim -> x ~= sqrt(n).

Daca se mai fac niste observatii mici se poate ajunge la solutia perfecta, care spune ca diferenta dintre 2 elemente consecutive trebuie sa scada cu 1. Astfel:

x[1] = 10, x[2] = 19, x[3] = 27, etc.

Astfel costul maxim este 19 pe cazul de mai sus pentru oricare pozitie, atata timp cat 10 + 9 + 8 + … + 1 ≥ n.

Rezolvare pentru problema generalizata

Observatia #3

Sa presupunem ca stim ca raspunsul nostru se afla in intervalul [1, n].

Daca noi spunem ca intrebam pe pozitia x, atunci avem 2 rezultate posibile:

oul se sparge
Atunci stim exact ca oul se va sparge de la orice alt etaj din intervalul [x + 1, n]. Astfel putem reduce domeniul de cautare la intervalul [1, x].
oul nu se sparge
Cu siguranta oul nu se va sparge nici daca il aruncam de la orice inaltime din intervalul [1, x]. Astfel putem reduce domeniul de cautare la intervalul [x + 1, n]. Stim ca la etajul x nu s-a spart, astfel putem incepe cautarea in noul interval de la etajul x + 1, nu e neaparat ca intervalul sa il includa pe x.

Observatia #4

Daca la un pas stim ca intervalul nostru de cautare este [y, y], atunci stim cu exactitate ca raspunsul este y.

Observatia #5

Scopul nostru este ca pentru un interval [st, dr] sa alegem o pozitie x astfel incat oricare ar fi raspunsul pentru query x numarul de pasi maxim sa fie minim.

De exemplu daca stim ca daca raspunsul se afla in intervalul [1, 5] putem afla raspunsul in maxim 4 pasi, daca se afla in intervalul [6, 30] in maxim 7 pasi.

Atunci stim ca daca intrebam pe pozitia 5 cand avem intervalul [1, 30] putem afla in maxim 7 pasi, iar acest maxim e dat daca oul nu se sparge.

Dar daca cumva intrebam pe pozita 8? Sa spunem ca putem afla pentru intervalul [1, 8] in 6 pasi, si pentru intervalul [9, 30] tot in 6 pasi.

Atunci daca intrebam ce se intampla la pozitia 8, putem afla raspunsul in maxim 6 pasi in orice caz, chiar daca se sparge sau nu oul.

Astfel putem observa ca pentru intervalul [1, 30] cel mai bine e sa intrebam la pozitia 8, astfel numarul maxim de calcule e minimizat pentru answer x = 8.

Observatia #6

Daca vrem sa aflam cat e raspunsul pentru un interval [st, dr] conteaza doar lungimea lui si numarul de oua pe care le avem.

Nu conteaza efectiv de unde pana unde e intervalul, conteaza doar lungimea sa si numarul de oua.

Observatia #7

Folosind cel mai mult observatiile 5 si 6 se poate deduce o dinamica.

Astfel sa notam D[n][k] = numarul maxim de pasi pe care trebuie sa il facem ca sa aflam unde se afla numarul din intervalul [1, n] avand k oua la dispozitie.

Astfel putem da cu un for locul unde aruncam oul (for (int x = 1; x <= n; ++x)).

Pentru un loc fixat avem cele 2 cazuri:

dp[x][k - 1]
oul s-a spart. Am redus intervalul la [1, x] care are lungime x si avem k - 1 oua ramase nesparte.
dp[n - x][k]
oul nu s-a spart. Am redus intervalul la [x + 1, n] care are lungimea n - x si avem k oua sparte.

Daca am fixat x, acum numarul maxim de pasi este:
int v = max(dp[x][k - 1], dp[n - x][k]) + 1 (numaram si aruncarea de la etajul x)
astfel dp[n][k] = min(dp[n][k], v), unde v este maximul calculat mai sus.

Practic din acest moment problema este rezolvata. Putem sa mai tinem minte care este pozitia x unde am aruncat pentru a afla cazul cel mai bun pentru o configuratie [n][k] -> astfel from[n][k] = x, unde x este valoarea care da minimul considerat mai sus prin dinamica.

La fiecare pas trebuie sa stim care este cea mai din stanga pozitie care stim 100% ca este buna si cat de mult ni se extinde intervalul cautarilor la dreapta.

Astfel la inceput cea mai buna pozitie este 0 si intervalul este de lungime n.
In cazul in care oul nu se sparge se mareste cea mai buna pozitie pana la locul unde am intrebat si se reduce din lungimea intervalului distanta parcursa (newPoz - poz).

Daca oul se sparge doar se micsoreaza intervalul de cautare, asta insemnand o micsorare a lungimii lui.
Intervalul de cautare este dat de [pozitiaMaximBuna + 1, pozitiaMaximBuna + lungimeInterval].

Pentru clarificarea dinamicii si o metoda de implementare draguta a acesteia puteti sa va uitati pe sursele oficiale ale problemei.
De asemenea se gaseste si programul de interactionare a comisiei, cel cu care comunica programul vostru.

Questions?

Sponsors Gold